知识卡片
单位价值贪心不解零一背包
容量为50、三件物品重量为10、20、30,价值为60、100、120时,单位重量价值最高的第一件会先被选中,但最优解是第二、三件,价值220。
整件约束使局部选择妨碍装满。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第15章 贪心算法 · 查看原书依据
The optimal subset includes items 2 and 3. Any solution with item 1 is suboptimal, even though item 1 has the greatest value per pound.
参考来源
- 位置:《算法导论(第4版)》第15章《贪心算法》(OEBPS/chapter015.xhtml,文本字符[30000,35000))。
- 结论依据:15.2 节图15.3 的 50 磅零一背包反例:物品1单位价值最高,但物品2和3合取价值220更优;整件约束破坏该局部选择。
- 原始内容:The optimal subset includes items 2 and 3. Any solution with item 1 is suboptimal, even though item 1 has the greatest value per pound.