879. 盈利计划 (opens new window)

1.动规+多维背包

分析：问题求解的是满足利润的方案数，所以如果按照完全背包那样将动规数组设置成dp[n][weight]，求解能够到达的利润数，最后方案数则没法统计，因为每一个利润结果可能包含多个子问题的方案。有两种思路：

• 思路一：开辟一个三维数组dp[n][weight][value]，保存考虑前i种物品，当前背包重量为weight，利润为value时下的方案数量。dp[n]的结果包含两部分，一部分是dp[n-1]前n-1种物品已经能达到状态方案数，另一部分是选择第i个物品后到达的状态方案数。结果只需统计dp[n]下所有满足利润的方案数之和。
• 思路二：开辟二维数组dp[weight][value]，相当于直接在前n-1种状态的结果上累加(省略了上面第一部分)。但注意每种商品只能选择一次，因此需要“倒序更新”。最后统计数组中满足利润的方案数之和。

方案数可能会爆，所以每次更新都需要取模。这里给出思路二的代码实现：

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int profitSum=0;
        for(int i=0;i<profit.length;i++)profitSum+=profit[i];
        int[][] dp=new int[n+1][profitSum+1];
        for(int i=0;i<group.length;i++){
            dp[0][0]=1;
            for(int j=n;j>=0;j--){
                for(int k=profitSum;k>=0;k--){
                    if(j-group[i]>=0&&k-profit[i]>=0)dp[j][k]=(dp[j][k]+dp[j-group[i]][k-profit[i]])%1000000007;
                }
            }
        }
        int res=0;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=profitSum;j++){
                if(j>=minProfit) res=(res+dp[i][j])%1000000007;
            }
        }
        return res;
    }
}