知识卡片
分数背包按单位价值填容量
物品允许任意分割且价值随重量线性变化时,先按单位重量价值降序,尽量拿价值密度更高的物品,最后不足一整件时只取剩余容量所需部分。
若一个方案拿了低密度部分而没拿完更高密度部分,可用等重高密度替换使价值不下降,得到包含贪心选择的最优方案。要求正重量、通常非负价值和可分性;单位价值相同只保证不下降,不是严格增加,0-1不可分背包不能套用。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
我们可以对物品任意地进行切分,并按照重量 比例来计算相应价值。 −1]/ [ − 1] 1. 对于物品 ,它在单位重量下的价值为 −1]/ [ − 1] ,简称单位价值。 2. 假设放入一部分物品 ,重量为 ,则背包增加
参考来源
- 位置:《Hello 算法--Go版本》第15章《贪心》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/8.html;spine 7,归一字符[6517,6627))
- 结论依据:实际分数定义/排序/部分填充和交换论证,修正密度相等的严格大于。
- 原始内容:我们可以对物品任意地进行切分,并按照重量 比例来计算相应价值。 −1]/ [ − 1] 1. 对于物品 ,它在单位重量下的价值为 −1]/ [ − 1] ,简称单位价值。 2. 假设放入一部分物品 ,重量为 ,则背包增加