Leetcode 879. Profitable Schemes

Problem Explanation

The problem is asking for the number of different schemes or groups, the gang members can participate to achieve a minimum profit. Each gang member can participate in only one scheme. And each scheme requires a certain number of gang members and can generate a particular profit.

Let's take an example, where we have 5 gang members G=5 and we want to achieve at least 3 profit P=3. The group array [2,2] represents the number of gang members required in each scheme, and the profit array [2,3] represents the profit of each scheme. Now, the gang can commit crimes 0 and 1 (group[0] and group[1]), using 4 gang members in total and generating 5 profit. Alternatively, the gang can just commit crime 1 (group[1]), using 2 gang members and generating 3 profit. So, there are 2 possible schemes in this case.

Now, coming on to the solution, we approach this problem using dynamic programming (DP). DP is a very efficient way to solve problems which have overlapping sub-problems. In this case, the sub-problem will be finding the number of schemes with the first 'k' crimes, 'i' members and at least 'j' profits. We will keep track of these sub solutions in our DP table, dp[k][i][j].

Now in the base case, we know that for zero crimes, we will have zero profits, irrespective of the number of members. So, we initialize dp[0][i][0] as 1 for all 'i' from 0 to 'n'.

Then, we iterate over the group array and for each crime, we see if the group of crimes can be formed or not. If the number of members 'i' is less than the number of members required for that crime 'g', then we just move on to the next crime, i.e., dp[k][i][j] = dp[k - 1][i][j]. But if 'i' is greater than or equal to 'g', then we can form a group. In this case, we add the current group with the groups that can be formed using the remaining members, i.e., dp[k][i][j] = dp[k - 1][i][j] + dp[k - 1][i - g][max(0, j - p)].

Thus, finally after iterating over all the crimes and all the members, the answer will be stored in dp[group.size()][n][minProfit].

Python Solution

1
2python
3class Solution:
4    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
5        dp = [[[0]*(minProfit+1) for _ in range(n+1)] for _ in range(len(group)+1)]
6        mod = 10**9 + 7
7
8        # No crimes, no profits and any # of members
9        for i in range(n+1):
10            dp[0][i][0] = 1
11
12        for k in range(1, len(group)+1):
13            g = group[k-1]
14            p = profit[k-1]
15            for i in range(n+1):
16                for j in range(minProfit+1):
17                    if i < g:
18                        dp[k][i][j] = dp[k-1][i][j]
19                    else:
20                        dp[k][i][j] = (dp[k-1][i][j] + dp[k-1][i-g][max(0, j-p)]) % mod
21
22        return dp[len(group)][n][minProfit]

Java Solution

1
2java
3class Solution {
4    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
5        int mod = (int)1e9 + 7;
6        int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
7        for (int i=0;i <= n; i++) {
8            dp[0][i][0] = 1; // No crimes, no profits, and any # of members
9        }
10        for (int k=1;k <= group.length; k++){
11            int g = group[k-1], p = profit[k-1];
12            for (int i=0; i <=n ; i++){
13                for (int j=minProfit; j >= 0; j--){
14                    if (i < g){
15                        dp[k][i][j] = dp[k-1][i][j];
16                    } else{
17                        dp[k][i][j] = (dp[k-1][i][j] + dp[k-1][i-g][Math.max(0,j-p)]) % mod;
18                    }
19                }
20            }
21        }
22        return dp[group.length][n][minProfit];
23    }
24}

JavaScript Solution

1
2javascript
3var profitableSchemes = function(n, minProfit, group, profit) {
4    const mod = 10**9 + 7;
5    const dp = Array.from({ length: group.length + 1 },
6                          () => Array.from({ length: n + 1 },
7                                           () => Array(minProfit + 1).fill(0)));
8    dp[0].forEach(d => d[0] = 1);
9    for (let k = 1; k <= group.length; k++) {
10        const g = group[k-1], p = profit[k-1];
11        for (let i = 0; i <= n; i++) {
12            for (let j = 0; j <= minProfit; j++) {
13                dp[k][i][j] = i < g ? dp[k-1][i][j] : (dp[k-1][i][j] + dp[k-1][i - g][Math.max(0, j - p)]) % mod;
14            }
15        }
16    }
17    return dp[group.length][n][minProfit];
18};

C++ Solution

1
2c++
3class Solution {
4public:
5    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
6        int mod = 1e9 + 7;
7        vector<vector<vector<int>>> dp(group.size() + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
8        
9        for(int i=0; i<=n; i++){ // No crimes, no profits, and any # of members
10            dp[0][i][0] = 1;
11        }
12        
13        for(int k=1; k<=group.size(); k++){
14            int g = group[k-1], p = profit[k-1];
15            for(int i=0; i<=n; i++){
16                for(int j=0; j<=minProfit; j++){
17                    if(i < g){
18                        dp[k][i][j] = dp[k-1][i][j];
19                    }
20                    else{
21                        dp[k][i][j] = (dp[k-1][i][j] + dp[k-1][i-g][max(0, j-p)]) % mod;
22                    }
23                }
24            }
25        }
26        
27        return dp[group.size()][n][minProfit];
28    }
29};

C# Solution

1
2csharp
3public class Solution {
4    public int ProfitableSchemes(int n, int minProfit, int[] group, int[] profit) {
5        int mod = (int)1e9 + 7;
6        int[][][] dp = new int[group.Length + 1][][];
7        for (int i = 0; i < dp.Length; i++){
8            dp[i] = new int[n + 1][];
9            for (int j = 0; j < dp[i].Length; j++){
10                dp[i][j] = new int[minProfit + 1];
11            }
12        }
13        for (int i = 0; i <= n; i++){
14            dp[0][i][0] = 1; // No crimes, no profits, and any # of members
15        }
16        for (int k = 1; k <= group.Length; k++){
17            int g = group[k-1], p = profit[k-1];
18            for (int i = 0; i <= n; i++){
19                for (int j = 0; j <= minProfit; j++){
20                    if (i < g){
21                        dp[k][i][j] = dp[k-1][i][j];
22                    }
23                    else{
24                        dp[k][i][j] = (dp[k-1][i][j] + dp[k-1][i-g][Math.Max(0,j-p)]) % mod;
25                    }
26                }
27            }
28        }
29        return dp[group.Length][n][minProfit];
30    }
31}

In conclusion, the solution to this problem involves dynamic programming. We create a 3-dimensional DP table where each entry corresponds to the number of ways to meet a specific profit requirement with a specific number of members and using a specific number of crimes. We then iterate through this table, keeping track of the best solution we've found so far. While this problem may seem complex at first, it becomes much more manageable once you break it down into its smaller sub-problems.

Each time we consider a new crime, we have two options: commit it or not. If we have enough members to commit the crime, then we could potentially make more profit. This profit could either be enough on its own, or it could put us over the minimum required when combined with the profit from other crimes. If we don't have enough members or the crime wouldn't increase our profit enough, we simply move on to the next crime. By considering all potential combinations in this way, our dynamic programming approach enables us to find the maximum number of profitable schemes.

The solutions provided in Python, Java, JavaScript, C++ and C# all use a similar structure and approach, but with differences related to the specific syntax and features of each language. These examples illustrate how this type of problem can be solved in a variety of popular programming languages.