知识卡片
零一背包每项只来自上一行
状态表示前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]) 需要注意的是,若当前物品重量