C ++中有利可图的方案
假设有一个与G人的团伙，以及他们可能犯下的各种罪行。第i次犯罪会产生利润值利润[i]，并要求团伙[i]帮派成员参与。
如果帮派成员参与一项犯罪，则他不能参与另一项犯罪。现在，让我们定义有利可图的方案，这些犯罪的任何子集至少产生P利润，并且参与该犯罪子集的成员总数最多为G。
我们必须找出可以选择多少个方案？答案可能非常大，因此以10^9+7为模返回。
因此，如果输入像G=5，P=3并且组=[2,2]，利润=[2,3]，那么输出将为2
为了解决这个问题，我们将遵循以下步骤-
ret：=0
定义一个尺寸为（G+1）x（P+1）的2D数组dp
dp[0，0]：=1
对于初始化k：=0，当k<组大小时，更新（将k增加1），-
对于初始化j：=P，当j>=0时，更新（将j减1），执行-
dp[i+g，P和j+p的最小值]
dp[i+g，P和j+p的最小值]
p：=利润[k]，g：=小组[k]
对于初始化i：=G-g，当i>=0时，更新（将i减1），-
对于初始化i：=0，当i<=G时，更新（将i增加1），执行-
ret：=ret+dp[i，P]
ret：=retmodm
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
int profitableSchemes(int G, int P, vector<int> &group, vector<int> &lprofit) {
int ret = 0;
vector<vector<int>> dp(G + 1, vector<int>(P + 1));
dp[0][0] = 1;
for (int k = 0; k < group.size(); k++) {
int p = profit[k];
int g = group[k];
for (int i = G - g; i >= 0; i--) {
for (int j = P; j >= 0; j--) {
dp[i + g][min(P, j + p)] += dp[i][j];
dp[i + g][min(P, j + p)] %= m;
}
}
}
for (int i = 0; i <= G; i++) {
ret += dp[i][P];
ret %= m;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,2}, v1 = {2,3};
cout << (ob.profitableSchemes(5,3,v, v1));
}输入值
5, 3, [2,2], [2,3]
输出结果
2