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：= ret mod m

• 返回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