知识卡片
价值密度贪心可能输给0-1组合
容量为 50 时,三件物品的“重量/价值”是 (10,60)、(20,100)、(30,120),价值密度依次为 6、5、4。不可拆分时,按密度先选前两件只能得 160;选后两件恰好装满,得 220。分数背包可把第三件取 20/30,得 240。可拆分性决定密度贪心是否可靠。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 2 . 3 . 1 基 于 贪 心 算 法 的 背 包 问 题 · 查看原书依据
根据贪心策略,应该首先选择物品1装入背包,然而,从图12.1(b)中可以看出,最优的选择方案并不是首选物品1的两种情况,而是选择物品2和物品3放入背包。若此问题转化为一般背包问题,则贪心算法可以求得最优解,选择方案如图12.1(c)所示。 112233 对于0-1背包问题,贪心算法之所以不能得到最优解,是因为在物品不可分割的前提条件下,贪心选择无法保证最终能装满背包,可能存在的闲置空间降低了背包中单位空间的价值。
参考来源
- 位置:《智能算法导论》第 126 项《12.3.1 基于贪心算法的背包问题》(源文件:`_epub-src/EPUB/xhtml/chapter12_0006.xhtml`;图 12.1、式 12-1、12-2)
- 结论依据:原文给出三个物品的重量、价值和密度,并用图 12.1 对照 0-1 方案与一般背包的部分装填;按这些数值可得 0-1 的 160/220 取舍与分数背包 240。
- 原始内容:根据贪心策略,应该首先选择物品1装入背包,然而,从图12.1(b)中可以看出,最优的选择方案并不是首选物品1的两种情况,而是选择物品2和物品3放入背包。若此问题转化为一般背包问题,则贪心算法可以求得最优解,选择方案如图12.1(c)所示。