背包问题实验室
比较按性价比贪心与动态规划，看看局部选择为何会错过最优解。
口袋最多装 10 kg，洞穴中有 4 件宝物；每件宝物不可拆分，最多选一次。
0/1 背包洞穴里的宝物
贪心按性价比从高到低考虑；并列时按表格顺序。
| 宝物 | 重量 | 价值 | 性价比 价值 / kg |
|---|
表格可左右滑动查看完整参数
国王的古董和皇后的妆盒性价比并列最高，演示时先考虑表格中排在前面的宝物。
背包状态
算法选择的宝物会显示在这里。
0/ 10 kg0价值
尚未放入宝物。点击「下一步」开始演示。
先比较单位重量的价值，再观察剩余容量如何影响选择。
贪心：每次选当前性价比最高的宝物
宝物不可拆分；放不下时跳过，继续检查下一件。
准备开始：算法将从性价比最高的宝物开始逐件检查。
动态规划表：状态定义 dp[i][c]
dp[i][c] 表示：只从宝物表格前 i 件中选取、总重量不超过 c kg 时，能获得的最大价值。i 是已考虑的宝物件数（0–4）；c 是背包容量上限（0–10 kg）。
填每一格时，比较「不选当前宝物」与「选当前宝物」两种情况。
dp[i][c] =
dp[i−1][c]，若 wᵢ > c
max(dp[i−1][c], vᵢ + dp[i−1][c−wᵢ])，否则
表格可左右滑动查看容量 0–10 kg
先从第 1 件宝物开始，逐格填写容量 0 到 10 对应的最优价值。
局部最优不等于全局最优
按性价比贪心留下 1 kg 空间，皇冠放不进去；动态规划找到了价值更高的组合。
性价比贪心175价值点
动态规划最优解191价值点 · 多 16 点
最优组合：国王的古董 + 皇后的妆盒 + 教皇的皇冠（10 kg）