对于第i件物品（从1开始计数），有两个选择：
1. 不选第i件：dp[i][j] = dp[i-1][j]（问题缩小为前i-1件）
2. 选第i件（前提：j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]

取两者最大值：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])  when j >= w[i]
dp[i][j] = dp[i-1][j]                                 when j < w[i]

2.3 完整实现（二维 + 空间优化一维）

package com.laozhang.dp;

import java.util.Arrays;

/**
 * 背包问题完整解法
 * 0-1背包：二维DP + 一维空间优化
 * 完全背包：完整实现
 * 二维约束背包：重量+体积双限制
 */
public class KnapsackProblems {

    /**
     * 0-1背包：二维DP版本（便于理解）
     *
     * @param weights 各物品重量，weights[i]是第i件物品的重量（从下标0开始）
     * @param values  各物品价值
     * @param W       背包最大容量
     * @return 最大价值
     */
    public static int zeroOneBag2D(int[] weights, int[] values, int W) {
        int n = weights.length;
        // dp[i][j]：考虑前i件物品，容量j的最大价值
        // 注意：i从1开始，dp[0][...]=0（没有物品，价值为0）
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            int w = weights[i - 1]; // 第i件物品的重量（数组下标从0开始）
            int v = values[i - 1];  // 第i件物品的价值

            for (int j = 0; j <= W; j++) {
                dp[i][j] = dp[i - 1][j]; // 默认：不选第i件
                if (j >= w) {
                    // 选第i件：前提是背包还有w的空间
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w] + v);
                }
            }
        }
        return dp[n][W];
    }

    /**
     * 0-1背包：一维空间优化版本（O(W)空间）
     *
     * 观察二维DP：dp[i][j]只依赖dp[i-1][...]（上一行）
     * 所以可以只用一维数组，每次更新代表"当前物品处理后的状态"
     *
     * 关键！！为什么要倒序遍历j？
     * 如果正序遍历：当处理dp[j]时，dp[j-w]已经被当前轮次更新了
     * （意味着第i件物品已经被选过一次了），这样变成了完全背包！
     * 倒序遍历：处理dp[j]时，dp[j-w]还是上一轮的值（第i件还没被选过）
     */
    public static int zeroOneBag1D(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1]; // dp[j] = 容量j时的最大价值

        for (int i = 0; i < n; i++) {
            int w = weights[i], v = values[i];
            // 必须倒序！！保证每件物品只被选一次
            for (int j = W; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
        return dp[W];
    }

    /**
     * 0-1背包路径还原：找出选了哪些物品
     */
    public static int[] zeroOneBagWithItems(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            int w = weights[i - 1], v = values[i - 1];
            for (int j = 0; j <= W; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= w) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w] + v);
            }
        }

        // 逆向追踪：从dp[n][W]往回找，判断每件物品是否被选中
        int[] selected = new int[n];
        int j = W;
        for (int i = n; i >= 1; i--) {
            if (dp[i][j] != dp[i - 1][j]) {
                // dp值变化说明第i件物品被选了
                selected[i - 1] = 1;
                j -= weights[i - 1]; // 容量减少
            }
        }
        return selected;
    }

    /**
     * 完全背包：每件物品可以选无限次
     *
     * 和0-1背包的区别只有一行！一维版本改为正序遍历j
     *
     * 为什么正序？
     * 正序时，处理dp[j]时，dp[j-w]已经是本轮更新的值
     * 即第i件物品已经可以在j-w时被选过，再选一次变成"选了2件"
     * 这正好符合完全背包的语义（可以选多次）
     */
    public static int completeBag(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1];

        for (int i = 0; i < n; i++) {
            int w = weights[i], v = values[i];
            // 正序遍历：允许重复选择同一件物品
            for (int j = w; j <= W; j++) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
        return dp[W];
    }

    /**
     * 零钱兑换（完全背包的变种，LeetCode 322）
     * coins[]数组中选硬币（可重复），凑成amount的最少硬币数
     *
     * 和完全背包的区别：求最小值而不是最大值
     */
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 初始化为不可能的大值（类似无穷大）
        dp[0] = 0; // 凑成0需要0枚硬币

        for (int coin : coins) {
            // 完全背包：正序遍历
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

2.4 二维约束背包（重量+体积双限制）

package com.laozhang.dp;

/**
 * 二维约束背包：物品有重量w和体积v两个约束，背包有重量上限W和体积上限V
 *
 * 状态定义扩展为三维：dp[i][j][k] = 前i件物品，重量≤j，体积≤k的最大价值
 * 空间优化：用二维数组dp[j][k]，每件物品倒序更新
 */
public class TwoDimKnapsack {

    /**
     * 二维约束0-1背包（空间优化版本）
     *
     * @param weights  各物品重量
     * @param volumes  各物品体积
     * @param values   各物品价值
     * @param maxW     背包重量上限
     * @param maxV     背包体积上限
     */
    public static int twoDimKnapsack(int[] weights, int[] volumes, int[] values,
                                      int maxW, int maxV) {
        int n = weights.length;
        // dp[j][k] = 重量≤j、体积≤k时的最大价值
        int[][] dp = new int[maxW + 1][maxV + 1];

        for (int i = 0; i < n; i++) {
            int w = weights[i], vol = volumes[i], val = values[i];
            // 两个维度都要倒序遍历（0-1背包，每件物品只选一次）
            for (int j = maxW; j >= w; j--) {
                for (int k = maxV; k >= vol; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - w][k - vol] + val);
                }
            }
        }
        return dp[maxW][maxV];
    }

    /**
     * 实际案例：LeetCode 474 - 0和1（二维0-1背包）
     * strs数组里每个字符串由0和1组成，m个0和n个1，最多能选多少个字符串？
     */
    public static int findMaxForm(String[] strs, int m, int n) {
        // 转化：每件"物品"是一个字符串，"重量"是0的数量，"体积"是1的数量，"价值"是1
        // 背包约束：最多m个0，最多n个1
        // 求能装入的最多"物品"数（最大价值）
        int[][] dp = new int[m + 1][n + 1];

        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            // 0-1背包：倒序遍历
            for (int j = m; j >= zeros; j--) {
                for (int k = n; k >= ones; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 测试与性能数据
     */
    public static void main(String[] args) {
        // 0-1背包测试
        int[] weights = {2, 3, 4, 5};
        int[] values  = {3, 4, 5, 6};
        int W = 8;

        System.out.println("0-1背包（二维）: " +
            KnapsackProblems.zeroOneBag2D(weights, values, W)); // 10
        System.out.println("0-1背包（一维）: " +
            KnapsackProblems.zeroOneBag1D(weights, values, W)); // 10

        int[] selected = KnapsackProblems.zeroOneBagWithItems(weights, values, W);
        System.out.print("选择的物品: ");
        for (int i = 0; i < selected.length; i++) {
            if (selected[i] == 1) System.out.print("物品" + (i+1) + "(w=" + weights[i] + ",v=" + values[i] + ") ");
        }
        System.out.println();

        // 完全背包测试
        int[] cWeights = {2, 3, 4};
        int[] cValues  = {3, 4, 5};
        System.out.println("完全背包: " +
            KnapsackProblems.completeBag(cWeights, cValues, W)); // 12（选4个重量2的物品）

        // 零钱兑换
        System.out.println("零钱兑换[1,5,6,9]凑11: " +
            KnapsackProblems.coinChange(new int[]{1,5,6,9}, 11)); // 2（5+6）

        // 二维约束
        int[] w2 = {1, 2, 3};
        int[] v2 = {2, 1, 2};
        int[] val2 = {4, 3, 5};
        System.out.println("二维约束背包(maxW=4,maxV=3): " +
            TwoDimKnapsack.twoDimKnapsack(w2, v2, val2, 4, 3)); // 7

        // 性能测试（据我JDK17实测）
        int N = 1000, bigW = 5000;
        int[] bigWeights = new int[N], bigValues = new int[N];
        java.util.Random rnd = new java.util.Random(42);
        for (int i = 0; i < N; i++) {
            bigWeights[i] = rnd.nextInt(100) + 1;
            bigValues[i] = rnd.nextInt(200) + 1;
        }

        long start = System.currentTimeMillis();
        int result = KnapsackProblems.zeroOneBag1D(bigWeights, bigValues, bigW);
        System.out.printf("1000件物品, 容量5000的0-1背包: 耗时%dms, 最大价值=%d%n",
            System.currentTimeMillis() - start, result);
        // 据我测试：约8ms（一维DP，数组操作极快）
    }
}

四、踩坑实录

坑1：0-1背包写成了完全背包（正序倒序搞混了）

报错现象：0-1背包得出的结果比预期大，相当于每件物品被无限次选择。

根本原因：一维DP时用了正序遍历，导致同一件物品可以在同一轮内被多次选择。

具体解法：

// 0-1背包：必须倒序
for (int j = W; j >= w; j--) { // 倒序！
    dp[j] = Math.max(dp[j], dp[j-w] + v);
}

// 完全背包：正序
for (int j = w; j <= W; j++) { // 正序！
    dp[j] = Math.max(dp[j], dp[j-w] + v);
}
// 记忆口诀：0-1背包要保护"上一件物品的状态"，所以倒序
// 完全背包"欢迎再次选择"，所以正序

坑2：状态定义不精确，导致转移方程出错

报错现象：dp数组填完了，但从哪里读答案想不清楚，或者答案是错的。

根本原因：状态定义模糊。比如dp[i]定义为"选了i件物品的价值"（没有容量维度），这样无法表达"容量约束"，导致转移方程无从下手。

具体解法：

// 状态定义要精确到能写出转移方程
// 好的状态定义：dp[i][j] = "考虑前i件物品，在容量j的约束下，能获得的最大价值"
// 这个定义包含了所有需要的信息：i（已处理的范围），j（约束条件），值（目标）

// 状态定义检查方法：
// 1. 知道dp[i][j]后，能否推出dp[i+1][j]？（能往前推）
// 2. 边界dp[0][j]和dp[i][0]是否有明确含义？（边界清晰）
// 3. 答案是dp[n][W]还是max(dp[i][j])？（答案位置明确）

坑3：数组越界——忘记处理j < w的情况

报错现象：ArrayIndexOutOfBoundsException: Index -1 out of bounds，指向dp[j-w]的访问。

根本原因：一维DP的循环起点写错了，从j=0开始而不是从j=w开始。

具体解法：

// 错误：j从0开始，j-w可能为负数
for (int j = 0; j <= W; j++) {         // 错！j=0时dp[j-w]=dp[-w]越界
    dp[j] = Math.max(dp[j], dp[j-w] + v);
}

// 正确：j从w开始，保证j-w >= 0
for (int j = W; j >= w; j--) {          // 倒序，j从W到w
    dp[j] = Math.max(dp[j], dp[j-w] + v);
}
// 当j < w时，dp[j]保持不变（容量不够，无法选第i件物品）
// 一维DP中，j < w的格子在这轮循环里不会被更新，保留上一轮的值，这是正确的

五、总结与延伸

背包问题的核心不是记公式，是理解"状态"的本质。 dp[i][j]的定义决定了一切：转移方程、初始化、答案位置全部都由状态定义推导出来。花80%的时间想清楚状态定义，剩下的代码几乎是机械推导。
0-1背包和完全背包的区别就是一维DP时的遍历方向。 倒序=保护上一件物品的状态=每件只选一次（0-1）；正序=允许本轮再次选择=可重复选（完全背包）。这个规律在多维背包中同样适用。
背包问题是一类问题的基础抽象，不只是"装背包"。 零钱兑换是完全背包，分割等和子集（LeetCode 416）是0-1背包，单词拆分（LeetCode 139）是完全背包。看到"从一组东西中选若干，满足某个总量约束，求最优解"，就往背包方向想。