? 问题描述
有一个容量为 W = 10 的背包， 现有 n = 5 个物品， 每个物品有对应的重量和价值。求在不超过背包容量的情况下，如何选择物品使得总价值最大。
物品清单
背包状态
0 / 10
已用容量
T DP 状态表
dp[i][w] 表示前 i 个物品在容量 w 下的最大价值
状态转移方程
if w < weight[i]:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
! 步骤讲解
点击播放按钮开始演示背包问题的动态规划求解过程。
演示将展示：
- 如何逐行填充 DP 表格
- 每个单元格的计算过程
- 状态转移方程的应用
- 最终最优解的回溯