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 Pprofit, 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

0-1背包问题

时间和复杂度O(N*P*G)

状态转移方程：当前任务 dp[i][j][k], 完成第i个任务，收入是j，需要的人数是k，可以选择不做这次任务，那么他至少和第i-1个任务，收入i，需要k个人的个数是一样的，如果选择做这次任务，那么他就是加上在上次任务（i-1）的收入是j-p，需要的人数是k-g，这样加上这次需要的人数是g，收入是p，刚好就是所需要的j和k，这里要注意j 和p，k和g的大小，

class Solution {
    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        int taskNum = profit.length;
        
        int[][][] dp = new int[taskNum+1][P+1][G+1];
        
        dp[0][0][0] = 1;
        int m = 1000000007;
        for(int i = 1; i <=taskNum;i++){
            int p = profit[i-1];
            int g = group[i-1];
            
            for(int j = 0; j <= P; j++){
                for(int k = 0; k <= G; k++){
                // k < g  人手不够，j < p，获利不够
                //如果选择做这次任务，那么就是找上一次任务里，收益是j-p，需要的人数是k-g的，为这次
                //预留
                    dp[i][j][k] = (dp[i-1][j][k] + (k < g ? 0 : dp[i-1][Math.max(0,j - p)][k-g]) ) % m;
                }
            }
        }
        
        int res = 0;
        
        for(int i =0; i < G+1;i++){
            res += dp[taskNum][P][i];
            res  =res % m;
        }
        
        return res ;
    }
    
    
}

降维优化

使用临时数组，时间复杂度 不变 空间复杂度 降了一维o(pg)

class Solution {
public:
  int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {    
    const int kMod = 1000000007;
    const int K = group.size();
    // dp[i][j]:= # of schemes of making profit i with j people.
    vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0));
    dp[0][0] = 1;
    
    for (int k = 1; k <= K; ++k) {
      auto tmp = dp;
      const int p = profit[k - 1];
      const int g = group[k - 1];
      for (int i = 0; i <= P; ++i)    
        for (int j = 0; j <= G; ++j)
          tmp[i][j] = (tmp[i][j] + (j < g ? 0 : dp[max(0, i - p)][j - g])) % kMod;
      dp.swap(tmp);
    }
    return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod;
  }
};