动态规划二维费用的背包问题系列一＞盈利计划

用户11305962

发布于 2025-04-02 08:34:20

1300

文章被收录于专栏：学习学习

题目解析：

链接: link

状态表示：

状态转移方程：

初始化：

填表顺序：

根据状态转移方程，i 从小到大即可

返回值：

返回：dp[len][n][minProfit]

代码呈现：

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int MOD = (int)1e9 + 7;
        int[][][] dp = new int[len+1][n+1][minProfit+1];

        for(int i = 0; i <= n; i++) dp[0][i][0] = 1;

        for(int i = 1; i <= len; i++)
            for(int j = 0; j <= n; j++)
                for(int k = 0; k <= minProfit; k++){
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= group[i-1]){
                        dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
                        dp[i][j][k] %= MOD;
                    }
                }

        return dp[len][n][minProfit];        
    }
}

空间优化版本：

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int MOD = (int)1e9 + 7;
        int[][] dp = new int[n+1][minProfit+1];

        for(int i = 0; i <= n; i++) dp[i][0] = 1;

        for(int i = 1; i <= len; i++)
            for(int j = n; j >= group[i-1]; j--)
                for(int k = minProfit; k >= 0; k--){
                    dp[j][k] = dp[j][k] + dp[j-group[i-1]][Math.max(0,k-profit[i-1])];
                    dp[j][k] %= MOD;
                }

        return dp[n][minProfit];        
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-04-01，如有侵权请联系 cloudcommunity@tencent.com 删除