知识卡片

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

零一背包倒序保住旧容量

理解等级:中级

把物品维度压成一个容量数组后,从大容量向小容量更新。这样读取较小的c-weight时,该位置还属于上一件物品的结果,当前物品不会在同一轮被重复计入。

若改为正序,较小容量可能已经含当前物品,语义就变成允许重复选。压缩从O(nC)空间到O©,不是原书泛写的n平方到n;记忆化版本还需缓存过重分支,不能只因有mem数组就断言所有状态只算一次。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      如果采取倒序遍历,则不会发生覆盖问题,状态转移可以正确进行。 图14‑21 展示了在单个数组下从第 行转换至第 行的过程。请思考正序遍历和倒序遍历的区别。 第14 章 动态规划 hello‑algo.com 332 图1

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[23180,23290)) - 结论依据:实际knapsackDPComp倒序与两方向对比,保留记忆化漏缓存边界。 - 原始内容:如果采取倒序遍历,则不会发生覆盖问题,状态转移可以正确进行。 图14‑21 展示了在单个数组下从第 行转换至第 行的过程。请思考正序遍历和倒序遍历的区别。 第14 章 动态规划 hello‑algo.com 332 图1