知识卡片

普通读书笔记卡 · 5654.c.3.b.3.a.1.a.2

完全背包正序允许当前项复用

理解等级:中级

完全背包允许同一物品多次选择,因此选当前物品后的剩余容量仍可从本行状态获得答案。压成单行后按容量递增,读取较小容量时可包含本轮当前物品,符合复用语义。

这与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 背包问题不同,转移至