TTKIT 在线工具
背包问题
用动态动画理解经典背包问题的求解过程
无需安装打开即用
当前关卡
周末登山
空间有限，每样装备都很想带
问题规模
4 件 · 10 格
需要判断 40 个状态
学习目标
看懂每次取舍
从状态转移到最优回溯
空格 播放/暂停 · → 单步 · R 重置
动态规划控制台
等待开始
观察算法如何比较“拿”与“不拿”
推演进度0 / 40 · 0%
流畅
准备好看算法做选择了吗？
点击“开始推演”，当前物品、比较来源和写入结果会同步高亮。
DP 状态地图
行代表已考虑的物品，列代表可用容量
当前格不放来源放入来源最优路径
| 物品 \ 容量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 空背包 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 指南针 | 0 | · | · | · | · | · | · | · | · | · | · |
| 饮用水 | 0 | · | · | · | · | · | · | · | · | · | · |
| 相机 | 0 | · | · | · | · | · | · | · | · | · | · |
| 帐篷 | 0 | · | · | · | · | · | · | · | · | · | · |
核心转移：dp[i][w] = max（不放第 i 件，放入第 i 件）。结束后，绿色格子会连成最优解的回溯路径。
60 秒理解算法
为什么叫 0-1 背包？
每件物品只有两种选择：拿（1）或不拿（0），不能只拿一半。
- STEP 01
定义状态
dp[i][w] 表示前 i 件物品、容量 w 时的最大价值。
- STEP 02
比较两条路
比较不拿当前物品，与拿下它之后的总价值。
- STEP 03
回溯答案
从右下角倒推，找出真正进入最优组合的物品。