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を1つ定義します

• dp [0、0]：=1

• 初期化k：=0の場合、k <グループのサイズの場合、更新（kを1増やします）、実行-

  • p：=利益[k]、g：=グループ[k]

  • 初期化i：=G-gの場合、i> =0の場合、更新（iを1つ減らす）、実行-

    • 初期化j：=Pの場合、j> =0の場合、更新（jを1つ減らす）、do-

      • dp [i + g、Pとj+pの最小値]

      • dp [i + g、Pとj+pの最小値]

• 初期化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