知识卡片

普通读书笔记卡 · 5626.g.1.b

分数背包按单位价值填容量

理解等级:中级

物品允许任意分割且价值随重量线性变化时,先按单位重量价值降序,尽量拿价值密度更高的物品,最后不足一整件时只取剩余容量所需部分。

若一个方案拿了低密度部分而没拿完更高密度部分,可用等重高密度替换使价值不下降,得到包含贪心选择的最优方案。要求正重量、通常非负价值和可分性;单位价值相同只保证不下降,不是严格增加,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. 假设放入一部分物品 ,重量为 ,则背包增加