知识卡片
零一背包倒序保住旧容量
把物品维度压成一个容量数组后,从大容量向小容量更新。这样读取较小的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