# 879. Profitable Schemes

There are G people in a gang, and a list of various crimes they could commit.

The `i`-th crime generates a `profit[i]` and requires `group[i]` gang members to participate.

If a gang member participates in one crime, that member can’t participate in another crime.

Let’s call a  profitable scheme  any subset of these crimes that generates at least `P` profit, and the total number of gang members participating in that subset of crimes is at most G.

How many schemes can be chosen?  Since the answer may be very large, return it modulo `10^9 + 7`.

Example 1:

``````Input: G = 5, P = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation:
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.
``````

Example 2:

``````Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation:
To make a profit of at least 5, the gang could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).
``````

Note:

1. `1 <= G <= 100`
2. `0 <= P <= 100`
3. `1 <= group[i] <= 100`
4. `0 <= profit[i] <= 100`
5. `1 <= group.length = profit.length <= 100`

``````class Solution {
public:
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
int n = group.size(), res = 0, M = 1e9 + 7;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(G + 1, vector<int>(P + 1)));
dp[0][0][0] = 1;
for (int k = 1; k <= n; ++k) {
int g = group[k - 1], p = profit[k - 1];
for (int i = 0; i <= G; ++i) {
for (int j = 0; j <= P; ++j) {
dp[k][i][j] = dp[k - 1][i][j];
if (i >= g) {
dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i - g][max(0, j - p)]) % M;
}
}
}
}
for (int i = 0; i <= G; ++i) {
res = (res + dp[n][i][P]) % M;
}
return res;
}
};
``````

``````class Solution {
public:
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
int n = group.size(), res = 0, M = 1e9 + 7;
vector<vector<int>> dp(G + 1, vector<int>(P + 1));
dp[0][0] = 1;
for (int k = 1; k <= n; ++k) {
int g = group[k - 1], p = profit[k - 1];
for (int i = G; i >= g; --i) {
for (int j = P; j >= 0; --j) {
dp[i][j] = (dp[i][j] + dp[i - g][max(0, j - p)]) % M;
}
}
}
for (int i = 0; i <= G; ++i) {
res = (res + dp[i][P]) % M;
}
return res;
}
};
``````

``````class Solution {
public:
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
vector<vector<vector<int>>> memo(group.size() + 1, vector<vector<int>>(G + 1, vector<int>(P + 1, INT_MIN)));
return helper(group.size(), G, P, group, profit, memo);
}
int helper(int k, int i, int j, vector<int>& group, vector<int>& profit, vector<vector<vector<int>>>& memo) {
if (k == 0) return j <= 0;
if (j < 0) j = 0;
if (memo[k][i][j] != INT_MIN) return memo[k][i][j];
int g = group[k - 1], p = profit[k - 1], M = 1e9 + 7;
int res = helper(k - 1, i, j, group, profit, memo);
if (i >= group[k - 1]) {
res = (res + helper(k - 1, i - g, j - p, group, profit, memo)) % M;
}
return memo[k][i][j] = res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/879

https://leetcode.com/problems/profitable-schemes/

https://leetcode.com/problems/profitable-schemes/discuss/154617/C%2B%2BJavaPython-DP

https://leetcode.com/problems/profitable-schemes/discuss/157099/Java-original-3d-to-2d-DP-solution

https://leetcode.com/problems/profitable-schemes/discuss/154636/C%2B%2B-O(PGn)-top-down-DP-solution

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation