> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linkedin/profitable-schemes.md).

# 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 `P`profit, 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`

{% embed url="<https://www.youtube.com/watch?v=MjOIR61txFc>" %}

`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的大小，

```java
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)

```cpp
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;
  }
};
```