原书出处
智能算法导论
122 1 2 . 1 从 背 包 问 题 了 解 贪 心 算 法
的选择来达到。这是贪心算法可行的第一个基本要素。贪心策略通常是从顶向下进行选择,将问题转换成一个相似的、规模更小的问题。
对于一个具体问题,要确定它是否具有贪心选择的性质,必须证明每一步所做的贪心选择最终能得到问题的最优解。首先,证明问题的一个整体最优解是从贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的类似子问题。然后,用数学归纳法证明,通过每一步贪心选择,最终可得到问题的一个整体最优解[1]。
贪心选择可能依赖于已经做出的选择,但不依赖将要进行的选择或子问题的解。从求解的全过程来看,每一次选择都将当前问题归纳为规
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/智能算法导论/_epub-src/EPUB/xhtml/chapter12_0002.xhtml
EPUB SHA-256:18e2691ea1badb55bab48f10fe7172f9d6a95bc5207bb2e234686cbbaff3641d