知识卡片
分数背包按价值密度装填
一般(分数)背包问题有 n 件物品,第 i 件价值 vᵢ、重量 wᵢ,背包容量 C;每件可只装一部分,装入比例 xᵢ 取 0 到 1,要在 Σwᵢxᵢ ≤ C 下使总价值 Σvᵢxᵢ 最大。
贪心规则是按单位重量价值(价值密度)vᵢ/wᵢ 从高到低取物:密度最高者能装多少装多少,装完仍有空间就换密度次高者,最后一件只装到恰好填满,可得到最大价值。若尚未排序,按密度排序主导计算量,书中给出 O(n log n);排序后的顺序装填只需逐件扫描。这个规则依赖“物品可取一部分”;若必须整件选取,最高密度不保证 0-1 背包最优,反例如 [[价值密度贪心可能输给0-1组合]]。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 2 . 3 . 1 基 于 贪 心 算 法 的 背 包 问 题 · 查看原书依据
112233 对于0-1背包问题,贪心算法之所以不能得到最优解,是因为在物品不可分割的前提条件下,贪心选择无法保证最终能装满背包,可能存在的闲置空间降低了背包中单位空间的价值。
参考来源
- 位置:《智能算法导论》第 122 项《12.1 从背包问题了解贪心算法》、第 126 项《12.3.1 基于贪心算法的背包问题》(源文件:`_epub-src/EPUB/xhtml/chapter12_0002.xhtml`、`_epub-src/EPUB/xhtml/chapter12_0006.xhtml`)
- 结论依据:第 122 项明确允许一般背包装入物品的一部分并按价值密度装填;第 126 项说明未排序物品先按单位重量价值降序排序,主要计算量在排序,复杂度为 O(n log n);其图 12.1 展示密度排序在不可分割背包中可能不是最优。
- 原始内容:在将物品放入背包时,可以选择放入物品的一部分,而不必全部放入背包。对于0-1背包问题,贪心算法之所以不能得到最优解,是因为在物品不可分割的前提条件下,贪心选择无法保证最终能装满背包。