动态规划 背包问题总结

目录 

• 01背包 二维写法
• 01背包 一维写法
• 完全背包 二维 带枚举写法
• 完全背包 二维 普通写法
• 完全背包 一维写法
• 多重背包 二维写法
• 多重背包 二进制优化

1.  01背包 二维写法

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])

        // 填写动态规划表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= C; j++) {
                if (j < w[i - 1]) {
                    // 第i种物品的重量大于当前背包的剩余容量，不能放入
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 第i种物品的重量小于等于当前背包的剩余容量，可以选择放入或不放入
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                }
            }
        }

2.   01背包 一维写法

 dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1])  注：j逆序

        // 遍历每一种物品
        for (int i = 1; i <= n; i++) {
            // 遍历每一个单位容量，从后往前更新
            for (int j = C; j >= w[i - 1]; j--) {
                // 更新dp[j]的值
                dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
            }
        }

3.   完全背包 二维 带枚举写法

dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i - 1]] + k * w[i - 1])

        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j]; // 不装第i种物品
                for (int k = 0; k * v[i - 1] <= j; k++) { // 枚举装k个第i种物品
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i - 1]] + k * w[i - 1]); // 比较不装和装第i种物品的最大价值
                }
            }
        }

4.  完全背包 二维 普通写法

5.  完全背包 一维写法

 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1])  注：j 顺序

         // 状态转移
         for (int i = 1; i <= n; i++) {
             for (int j = 1; j <= V; j++) { // 正序遍历容量
                 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1]); // 比较不装和装第i种物品的最大价值
             }
         }

6.   多重背包 二维写法

dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i])

        for (int i = 1; i <= N; i++) { // 遍历物品
            for (int j = 0; j <= V; j++) { // 遍历背包容量
                for (int k = 0; k <= s[i] && k * v[i] <= j; k++) { // 遍历物品数量
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]); // 状态转移
                }
            }
        }

7.  多重背包 二进制优化

        for (int i = 1; i <= N; i++) { // 遍历物品
            int k = 1; // 拆分因子
            while (k <= s[i]) { // 拆分数量不超过原数量
                for (int j = V; j >= k * v[i]; j--) { // 遍历背包容量
                    dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]); // 状态转移
                }
                s[i] -= k; // 减去已拆分的数量
                k <<= 1; // 拆分因子翻倍
            }
            if (s[i] > 0) { // 如果还有剩余数量
                for (int j = V; j >= s[i] * v[i]; j--) { // 遍历背包容量
                    dp[j] = Math.max(dp[j], dp[j - s[i] * v[i]] + s[i] * w[i]); // 状态转移
                }
            }
        }