知识卡片

普通读书笔记卡 · 3624.a.3.a

单位价值贪心不解零一背包

理解等级:高级

容量为50、三件物品重量为10、20、30,价值为60、100、120时,单位重量价值最高的第一件会先被选中,但最优解是第二、三件,价值220。

整件约束使局部选择妨碍装满。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.