知识卡片
完全背包正序允许当前项复用
完全背包允许同一物品多次选择,因此选当前物品后的剩余容量仍可从本行状态获得答案。压成单行后按容量递增,读取较小容量时可包含本轮当前物品,符合复用语义。
这与0-1背包倒序正好相反,区别来自转移来源,不是任意编码风格。重量必须为正以保证容量递减,零重量正价值会使目标无界;值比较应保持整数精度和范围。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
仍可以从前 个物品中选择 。 在完全背包问题的规定下,状态 1, ] 的变化分为两种情况。 ‧ 不放入物品 :与0‑1 背包问题相同,转移至[ , − [ − 1]] 。 ‧ 放入物品 :与0‑1 背包问题不同,转移至
参考来源
- 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[24066,24175))
- 结论依据:实际完全背包本行i转移与正序压缩代码,区别0-1。
- 原始内容:仍可以从前 个物品中选择 。 在完全背包问题的规定下,状态 1, ] 的变化分为两种情况。 ‧ 不放入物品 :与0‑1 背包问题相同,转移至[ , − [ − 1]] 。 ‧ 放入物品 :与0‑1 背包问题不同,转移至