← 返回卡片

原书出处

智能算法导论

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

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

而是选择物品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