知识卡片

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

零一背包每项只来自上一行

理解等级:中级

状态表示前i件物品在容量c内的最大价值;不选当前物品读取上一行同容量,选则读取上一行扣除重量的容量并加价值,取两者较大。过重时只保留不选。

重量应为正、容量非负、重量价值列表等长,结果算术不能溢出;本书无物品/零容量取0依赖这些约定。O(nC)中的C是容量数值,按输入编码长度衡量属于伪多项式,不能当对所有输入都多项式高效。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      最大价值 等于不放入物品 和放入物品 两种方案中价 值更大的那一个 。由此可推导出状态转移方程: [ , ] = max( [ −1, ], [ −1, − [ −1]] + [ − 1]) 需要注意的是,若当前物品重量

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[20511,20621)) - 结论依据:实际0-1状态/两来源/边界,限定正重量和容量规模。 - 原始内容:最大价值 等于不放入物品 和放入物品 两种方案中价 值更大的那一个 。由此可推导出状态转移方程: [ , ] = max( [ −1, ], [ −1, − [ −1]] + [ − 1]) 需要注意的是,若当前物品重量