# 0879. Profitable Schemes
###### tags: `Leetcode` `Hard` `Dynamic Programming` `Knapsack Problem`
Link: https://leetcode.com/problems/profitable-schemes/
## 思路
典型背包问题
但区别在于这里有两个限制条件: profit最少是```minProfit```, 人数要最多是```n```
所以其实是一个3D的背包问题 但是可以压缩成2D
如果按照之前的方法就需要先算出total profit和total people 然后两层回圈遍历```[0:total profit][0:total people]```
但其实仔细观察可以发现我们可以在遍历过程中把大于```minProfit```的方法数全都归在```minProfit```里面 把人数大于```n```的方法直接抛弃掉(之所以这样做是因为在遍历过程中minProfit和people数一定不会减少)

## Code
java

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int totalp = 0;
        int l = group.length;
        int mod = 1000000007;
        for(int i=0; i<l; i++) totalp += group[i];
        long[][] dp = new long[n+1][minProfit+1];
        dp[0][0] = 1;
        for(int i=0; i<l; i++){
            for(int j=n-group[i]; j>=0; j--){
                for(int k=minProfit; k>=0; k--){
                    dp[j+group[i]][Math.min(minProfit, k+profit[i])]+=dp[j][k];
                    dp[j+group[i]][Math.min(minProfit, k+profit[i])] %= mod;
                }
            }
        }
        long ans = 0;
        for(int i=0; i<=n; i++){
            ans = (ans+dp[i][minProfit])%mod;
        }
        return (int)ans;
    }
}

c++

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int l = group.size();
        int mod = 1000000007;
        auto dp = vector<vector<long>>(n+1, vector<long>(minProfit+1));
        dp[0][0] = 1;
        for(int i=1; i<=l; i++){
            int num = group[i-1];
            for(int j=n-num; j>=0; j--){
                for(int k=0; k<=minProfit; k++){
                    dp[j+num][min(k+profit[i-1], minProfit)] += dp[j][k];
                    dp[j+num][min(k+profit[i-1], minProfit)] %= mod;
                }
            }
        }
        long ans = 0;
        for(int i=0; i<=n; i++) ans = (ans+dp[i][minProfit])%mod;
        return (int)ans;
    }
};