原书出处
智能算法导论
126 1 2 . 3 . 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