0-1背包问题动态讲解

问题描述：给定一组物品，每个物品有重量和价值，如何选择物品放入容量为 W 的背包中，使得背包内物品的总价值最大？每个物品只能使用一次（0-1 选择）。

背包容量 (W)

预设：背包最大承重为 10

物品列表（预设参数）

重量: 2

价值: 6

重量: 3

价值: 5

重量: 5

价值: 8

使用这 3 件物品和容量 10 的背包，演示 0-1 背包动态规划的求解过程。

动态规划过程演示

物品/容量	0	1	2	3	4	5	6	7	8	9	10

演示尚未开始...

最终容量使用：0/10

最终总价值：0

算法原理（0-1 背包动态规划）

状态定义：dp[i][j] 表示「只考虑前 i 个物品，在背包容量为 j 时能取得的最大总价值」。

状态转移方程：

如果第 i 个物品重量为 weight[i]，价值为 value[i]：

1. 如果 j < weight[i]（装不下第 i 个物品）：
dp[i][j] = dp[i-1][j]

2. 如果 j ≥ weight[i]（可以考虑装）：
dp[i][j] = max( dp[i-1][j], dp[i-1][j - weight[i]] + value[i] )

/* 0-1 背包动态规划伪代码 */
function knapsack01(weights, values, capacity) {
    const n = weights.length;
    const dp = new Array(n + 1).fill().map(
        () => new Array(capacity + 1).fill(0)
    );

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= capacity; j++) {
            if (j >= weights[i-1]) {
                dp[i][j] = Math.max(
                    dp[i-1][j],
                    dp[i-1][j - weights[i-1]] + values[i-1]
                );
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    return dp[n][capacity];
}