879. Profitable Schemes


Problem Description

In this LeetCode problem, we are given n, which represents the number of members in a group. We also have a list of crimes, where each crime can generate a certain amount of profit (profit[i]) and requires a specific number of group members (group[i]) to participate. The constraint is that a member cannot participate in more than one crime.

Our goal is to find the number of different "profitable schemes" we can form. A profitable scheme is defined as a subset of these crimes that yields at least a certain minProfit while utilizing n or fewer members in total.

We need to calculate the total number of such subsets of crimes that meet the criteria and return this number modulo 10^9 + 7 to avoid large output values.

Intuition

To tackle this problem, we can consider it as a variation of the classic 0/1 knapsack problem. The two constraints we are dealing with are the total number of members we have (n) and the minimum profit we aim to achieve (minProfit). The twist here is that, unlike the classic knapsack problem where we typically have only one constraint (weight), we have two constraints (group size and profit).

We can approach this problem with either recursion with memoization or dynamic programming. The basic intuition for both methods is to consider each crime and decide whether we include it in our scheme or not. We make this decision based on whether including the crime will keep the total number of participants within n and help us reach at least minProfit.

Recursion with Memoization:

We recursively try to build our solution by defining a function, say dfs(i, j, k), which tells us the number of schemes possible starting from the i-th job while having chosen j members and already accumulated a profit of k. We explore two possibilities at each step: including the current crime or excluding it. To prevent recalculations and improve efficiency, we use memoization to store intermediate results in a three-dimensional array.

Dynamic Programming:

Dynamic Programming (DP) offers a more systematic approach to this problem. Instead of recursively computing the answers, we iteratively build up a problem table f with dimensions representing the number of jobs considered so far, the number of employees used, and the current profit. The recurrence relation updates the table by considering the inclusion or exclusion of each job, much like the recursive approach, but done iteratively.

For the DP solution, we initialize our table with the understanding that, for zero jobs, we can only achieve zero profit with one scheme (doing nothing). We then iterate over each job and update the schemes count for various combinations of members used and profit gained, considering both options of including or excluding the crime.

Finally, whether we choose recursion with memoization or dynamic programming, the common intuition is to try each subset of crimes, enforce our constraints (not exceeding member limit and achieving at least minProfit), and count the number of valid schemes that arise from these choices.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The problem has been approached with two algorithms: recursion with memoization and dynamic programming. Both methods aim to compute the number of ways in which crimes can be combined such that the total number of members used does not exceed n and the profit is at least minProfit. Here's how each approach works:

Recursion with Memoization:

The recursion with memoization approach uses a depth-first search (DFS) function named dfs(i, j, k) that represents number of schemes that can be formed starting from the i-th crime while having engaged j members and amassed a profit of k.

The base case of the recursion is when all crimes have been considered (i == n). If the accumulated profit k is greater than or equal to minProfit at this point, then we have found one valid scheme. If not, the scheme is invalid.

During the recursion, for each crime, we have the choice of either including it or not:

  • If we choose not to include the crime, we simply move onto the next with dfs(i + 1, j, k).
  • If we do include it and have enough members left (j + group[i] <= n), the profit increases by profit[i] (but not exceeding minProfit) and the number of members increases by group[i]. This gives us dfs(i + 1, j + group[i], min(k + profit[i], minProfit)).

Memoization is used to store these results in a three-dimensional array f[i][j][k] to ensure that each unique state is only computed once. This greatly reduces the number of redundant calculations, thus optimizing the function.

Dynamic Programming:

The dynamic programming approach involves iteratively filling out a three-dimensional array f[i][j][k], which holds similar meanings to the parameter of our dfs function. The dimensions i, j, and k respectively represent the number of jobs considered up to this point, the number of members involved, and the current accumulated profit.

Initialization is straightforward: f[0][j][0] = 1, signifying that having zero jobs only allows for a profit of 0, which has one trivial scheme (doing nothing).

From there, for each job i, we enumerate through all possible employee counts j and profit values k to update the DP table based on our choices:

  • If job i is skipped, f[i][j][k] remains the same as f[i - 1][j][k].
  • If job i is included, the count f[i][j][k] is increased by the count f[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]. This addition represents the schemes where job i contributes to the number of members and profit considering the constraints.

The answer to the problem would be the value of f[m][n][minProfit] after populating the table, as it represents the total number of schemes for m jobs with n members achieving at least minProfit.

Both the recursion with memoization and dynamic programming approaches provide a way to systematically traverse the search space of all possible crime scheme combinations, while ensuring the constraints are met, and efficiently count the number of valid schemes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Imagine a scenario where there are n = 2 members in a group and the given list of crimes with their respective profits and group requirements is as follows: profit = [1, 2] and group = [1, 2]. The minimum profit we want to achieve is minProfit = 2.

Let's walk through the dynamic programming approach to see how this problem can be solved.

Initially, we start by creating a 3D array f with dimensions [3][3][3] representing the number of jobs (including a 'zero' job), the number of members (0 through 2), and the profit values (0 through 2), respectively.

We know that no profit can be made without any jobs, so we initialize f[0][j][0] = 1 for 0 <= j <= n. This reflects the fact that there is one way to achieve zero profit with any number of available members by not committing any crimes.

Now, using the DP approach, we iteratively update the array f as follows:

  1. Consider job 1 (crime 1 with profit 1 requiring 1 member): We look at combinations of employee counts and profits, and update the table by considering if we include job 1 or skip it.

    Including job 1 when we have 0 members already used and 0 profit so far would update f[1][1][1], indicating one scheme to achieve at least 1 profit with 1 member. Skipping job 1 would keep values same as previous, that is f[0][0][0] = 1.

  2. Consider job 2 (crime 2 with profit 2 requiring 2 members): Now we proceed to update our array with the second job. This job requires both members to participate and yields the profit we want.

    If we include job 2 with 0 members and 0 profit used so far, we cannot do so because we don't have enough members (as it requires 2 and we only have 0). So, we skip to the entries where we have enough members.

    The entry f[2][2][2] is updated (now has value 1) representing one way to achieve a profit of 2 using both members by including the second job. Entries like f[2][1][1] remain as they were when derived from job 1, representing the available schemes to achieve profit 1 with 1 member, which cannot contribute to achieving profit 2 and so are not altered.

After populating our DP table, we look for f[NUM_JOBS][NUM_MEMBERS][minProfit] to find our answer. Here, f[2][2][2] represents the total number of schemes to achieve a profit of at least 2 while using up to 2 members, which is 1 (only by committing the second crime).

Therefore, the total number of profitable schemes for n=2, profit=[1,2], group=[1,2], and minProfit=2 is 1, indicating there is only one way to achieve the minimum profit without exceeding the number of group members. This solution counts all distinct arrangements that meet our criteria modulo 10^9 + 7.

Not Sure What to Study? Take the 2-min Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Python Solution

1class Solution:
2    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
3        # Define the modulus value as constant
4        MOD = 10**9 + 7
5        # Get the length of the group list which indicates the number of crimes
6        num_crimes = len(group)
7        # Create a 3D DP array with dimensions (num_crimes+1) x (n+1) x (minProfit+1)
8        dp = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(num_crimes + 1)]
9      
10        # Initialize the base case where for 0 crimes there's 1 way to make $0 with any number of people
11        for j in range(n + 1):
12            dp[0][j][0] = 1
13      
14        # Iterate over each crime
15        for i, (members, gain) in enumerate(zip(group, profit), 1):
16            # Loop over the number of people available from 0 to n
17            for j in range(n + 1):
18                # Loop over the range of profits from 0 to minProfit
19                for k in range(minProfit + 1):
20                    # Copy the value from the previous crime plan
21                    dp[i][j][k] = dp[i - 1][j][k]
22                    # Check if the number of members needed for the current crime is less than or equal to the number of people available
23                    if j >= members:
24                        # Update the current state considering taking the current crime
25                        dp[i][j][k] += dp[i - 1][j - members][max(0, k - gain)]       
26                        # Apply modulus to keep the value within the integer range
27                        dp[i][j][k] %= MOD
28      
29        # Return the total number of ways to achieve at least minProfit
30        return dp[num_crimes][n][minProfit]
31

Java Solution

1class Solution {
2    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
3        final int MOD = (int) 1e9 + 7; // Modulo for the final result to prevent overflow
4        int m = group.length; // total number of crimes
5        int[][][] dp = new int[m + 1][n + 1][minProfit + 1]; // dp array to store the results
6      
7        // Initialization: with 0 crimes, there is 1 way to get 0 profit with any number of members
8        for (int j = 0; j <= n; ++j) {
9            dp[0][j][0] = 1;
10        }
11      
12        // Fill the dp table
13        for (int i = 1; i <= m; ++i) { // for each crime
14            for (int j = 0; j <= n; ++j) { // for each possible number of gang members
15                for (int k = 0; k <= minProfit; ++k) { // for each profit from 0 to minProfit
16                    // Counting the number of profitable schemes without the current crime
17                    dp[i][j][k] = dp[i - 1][j][k];
18                    // Counting profitable schemes including the current crime, if possible
19                    if (j >= group[i - 1]) {
20                        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - group[i - 1]][Math.max(0, k - profit[i - 1])]) % MOD;
21                    }
22                }
23            }
24        }
25      
26        // The answer is the number of profitable schemes with ‘m’ crimes, using up to ‘n’ members
27        // and achieving at least 'minProfit' profit.
28        return dp[m][n][minProfit];
29    }
30}
31

C++ Solution

1class Solution {
2public:
3    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
4        // m is the number of crimes
5        int m = group.size();
6        // Initializing the 3D dynamic programming array with dimensions
7        // m + 1 (for number of crimes), G + 1 (for gang members), and P + 1 (for minimum profit)
8        int dp[m + 1][G + 1][P + 1];
9        memset(dp, 0, sizeof(dp)); // Zero-initialize the dp array
10
11        // Base case: for zero crimes, we have one way to achieve zero profit, irrespective of the number of members
12        for (int j = 0; j <= G; ++j) {
13            dp[0][j][0] = 1;
14        }
15        // Modulo for large numbers to avoid integer overflow
16        const int MOD = 1e9 + 7;
17
18        // Dynamic Programming to fill the dp array
19        for (int i = 1; i <= m; ++i) {
20            for (int j = 0; j <= G; ++j) {
21                for (int k = 0; k <= P; ++k) {
22                    // Case where we don't commit the i-th crime
23                    dp[i][j][k] = dp[i - 1][j][k];
24                    // Case where we commit the i-th crime, if there are enough gang members
25                    if (j >= group[i - 1]) {
26                        // We use max(0, k - profit[i - 1]) to ensure non-negative index when profit is higher than k
27                        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]) % MOD;
28                    }
29                }
30            }
31        }
32        // Returning the total number of profitable schemes with at most G members and at least P profit
33        return dp[m][G][P];
34    }
35};
36

Typescript Solution

1// Define a constant for modulo as per the problem statement
2const MOD = 1e9 + 7;
3
4function profitableSchemes(G: number, P: number, group: number[], profit: number[]): number {
5  
6    // m represents the number of possible crimes
7    const m = group.length;
8
9    // Initialize a 3D dynamic programming array
10    const dp: number[][][] = [...Array(m + 1)].map(() =>
11        [...Array(G + 1)].map(() => Array(P + 1).fill(0))
12    );
13  
14    // Base case: for zero crimes, there is one way to achieve zero profit
15    for (let j = 0; j <= G; ++j) {
16        dp[0][j][0] = 1;
17    }
18
19    // Main Dynamic Programming loop to populate dp array
20    for (let i = 1; i <= m; ++i) {
21        for (let j = 0; j <= G; ++j) {
22            for (let k = 0; k <= P; ++k) {
23                // Case where the i-th crime is not committed
24                dp[i][j][k] = dp[i - 1][j][k];
25                // Case where the i-th crime is committed, if enough gang members are available
26                if (j >= group[i - 1]) {
27                    // Calculating the new profit index, but ensuring non-negative index
28                    const newProfit = Math.max(0, k - profit[i - 1]);
29                    // Adding this scheme's count to the total
30                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - group[i - 1]][newProfit]) % MOD;
31                }
32            }
33        }
34    }
35
36    // Return the total count of schemes that can achieve at least P profit with at most G members
37    return dp[m][G][P];
38}
39
40// Example usage of the function
41// const G = 10; // Number of gang members
42// const P = 5;  // Minimum profit required
43// const group = [2, 3, 5]; // Group sizes required for each crime
44// const profit = [6, 7, 8]; // Profit of each crime
45// console.log(profitableSchemes(G, P, group, profit)); // Outputs the result
46
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Time and Space Complexity

The time complexity of the provided code is O(m * n * minProfit), where m represents the number of jobs, n represents the number of workers, and minProfit is the target minimum profit. This stems from the triple nested loops where the outermost loop runs for m jobs, the middle loop for n + 1 workers (from 0 to n), and the innermost loop for minProfit + 1 different profit targets (from 0 to minProfit).

The space complexity of the code is also O(m * n * minProfit). This is due to the 3-dimensional array f that is being created to store results for subproblems. The dimensions of this array are (m + 1) * (n + 1) * (minProfit + 1), corresponding to the number of jobs, workers plus one (to include the case of 0 workers), and minimum profit targets plus one (to include the case of 0 profit), respectively.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫