← 返回卡片

原书出处

智能算法导论

126 1 2 . 3 . 1 基 于 贪 心 算 法 的 背 包 问 题

核验版本的摘录快照 · 导入于 2026-10-23T08:14:02.885Z

元;物品3的重量w=30kg,价值v=120元。因此,物品1每千克价值6元,物品2每千克价值5元,物品3每千克价值4元。

根据贪心策略,应该首先选择物品1装入背包,然而,从图12.1(b)中可以看出,最优的选择方案并不是首选物品1的两种情况,而是选择物品2和物品3放入背包。若此问题转化为一般背包问题,则贪心算法可以求得最优解,选择方案如图12.1(c)所示。 112233 对于0-1背包问题,贪心算法之所以不能得到最优解,是因为在物品不可分割的前提条件下,贪心选择无法保证最终能装满背包,可能存在的闲置空间降低了背包中单位空间的价值。

因此,在求解0-1背包问题时,应该比较物品选择与不选择所导致的结果,然后做出最合适的选择。 图12.1 背包问题的例子

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/智能算法导论/_epub-src/EPUB/xhtml/chapter12_0006.xhtml

EPUB SHA-256:18e2691ea1badb55bab48f10fe7172f9d6a95bc5207bb2e234686cbbaff3641d