C++의 수익성 있는 계획

<시간/>

G 사람들과 그들이 저지를 수 있는 다양한 범죄 목록이 있는 갱단이 있다고 가정합니다. i 번째 범죄는 이익 가치 이익[i]을 생성하고 그룹[i] 갱단 구성원이 참여해야 합니다.

갱단원이 한 범죄에 가담하면 다른 범죄에 가담할 수 없습니다. 이제 P 이상의 수익을 창출하는 이러한 범죄의 하위 집합을 정의하고 해당 범죄 하위 집합에 참여하는 구성원의 총 수는 G 이하인 수익성 있는 계획을 정의합니다.

얼마나 많은 계획을 선택할 수 있는지 찾아야 합니까? 대답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 G =5, P =3 및 그룹 =[2,2], 이익 =[2,3]인 경우 출력은 2

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

렛 :=0
(G + 1) x (P + 1) 크기의 2D 배열 dp 하나 정의
dp[0, 0] :=1
초기화 k :=0의 경우 k <그룹 크기일 때 업데이트(k를 1만큼 증가), -
- p :=이익[k], g :=그룹[k]
- initialize 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의 최소값]
initialize i :=0의 경우, i <=G일 때 업데이트(i를 1만큼 증가), −
- 렛 :=렛 + dp[i, P]
- ret :=ret 모드 m
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]