0-1 背包问题（动态规划）演示 | 信息技术教学工具

输入数据

背包容量 V（1~12）

物品重量（逗号分隔，最多 8 个）

物品价值（逗号分隔）

物品列表

动态规划表 dp[i][w]

dp 值不选：dp[i-1][w] 选：dp[i-1][w-Ci]

点击“开始演示”启动 0-1 背包动态规划过程。

操作控制

动画速度: 400ms

0

比较次数

0

更新次数

核心代码

V = 10
N = 4
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
dp = [[0] * (V + 1) for i in range(N + 1)]
for i in range(1, N + 1):
    for w in range(1, V + 1):
        if weights[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
        else:
            dp[i][w] = dp[i-1][w]
print(dp[N][V])
 
# 回溯：找出被选中的物品
i, w = N, V
selected = []
while i > 0:
    if dp[i][w] != dp[i-1][w]:
        selected.append(i)
        w -= weights[i-1]
    i -= 1
print(selected)

思路说明：dp[i][w] 表示从前 i 个物品中选择，放入容量为 w 的背包能获得的最大价值。对于每个物品，只有“选”或“不选”两种选择：不选时价值等于 dp[i-1][w]；选时价值等于 dp[i-1][w-weights[i-1]] + values[i-1]（前提容量足够）。取两者较大值填入表格。最后从 dp[N][V] 倒推，如果 dp[i][w] 与 dp[i-1][w] 不同，说明第 i 个物品被选中。