准备开始
欢迎来到背包问题讲解
即将自动开始播放……
背包容量: W = 8
在有限容量下选择物品，使总价值最大
📋 可选物品
🤔 决策比较
不放物品 i
-
VS
放入物品 i
-
📊 动态规划表 (DP Table)
🎉 最优解
0
最大价值
💻 算法伪代码
function knapsack(W, items):
n = items.length
// 初始化 dp 表，全部填 0
dp = new Array[n+1][W+1] = 0
for i = 1 to n: // 遍历每个物品
for j = 0 to W: // 遍历每个容量
if w[i] > j: // 放不下
dp[i][j] = dp[i-1][j]
else: // 放得下，取最大值
dp[i][j] = max(dp[i-1][j],
dp[i-1][j-w[i]] + v[i])
return dp[n][W] // 返回最优解
📊 当前状态
-
物品 i
-
容量 j
-
当前值
0
最优值
📝 讲解大纲
- 1问题介绍
- 2认识物品
- 3定义状态
- 4转移方程
- 5初始化表格
- 6填表：物品1
- 7填表：物品2
- 8填表：物品3
- 9填表：物品4
- 10回溯方案
- 11得出结果
ℹ️ 小贴士
0/1背包是最经典的动态规划问题之一，每个物品只有"选"或"不选"两种状态。