文档介绍：1第五章贪婪算法 2第五章贪心算法顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。 贪心算法的基本要素 ,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。 贪心算法的基本要素 ,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本要素 ,这是 2类算法的一个共同点。但是,对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究 2个经典的组合优化问题,并以此说明贪心算法与动态规划算法的主要差别。 贪心算法的基本要素?0-1 背包问题: 给定 n种物品和一个背包。物品 i的重量是 Wi, 其价值为 Vi,背包的容量为 C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品 i只有 2种选择,即装入背包或不装入背包。不能将物品 i装入背包多次,也不能只装入部分的物品 i。 贪心算法的基本要素?背包问题: 与0-1 背包问题类似,所不同的是在选择物品 i装入背包时, 可以选择物品 i的一部分,而不一定要全部装入背包, 1≤i≤n。这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而 0-1 背包问题却不能用贪心算法求解。 贪心算法的基本要素用贪心算法解背包问题的基本步骤: 首先计算每种物品单位重量的价值 Vi/ Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过 C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。具体算法可描述如下页: 贪心算法的基本要素对于 0-1 背包问题,贪心选择之所以不能得到最优解是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。事实上,在考虑 0-1 背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此,动态规划算法的确可以有效地解 0-1 背包问题。 最优装载有一批集装箱要装上一艘载重量为 c的轮船。其中集装箱 i的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。 。采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解。具体算法描述如下页。