贪心算法与动态规划的比较

《贪心算法与动态规划的比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贪心算法与动态规划的比较【摘要】介绍了计算机算法设计的两种常用算法思想：贪心算法与动态规划算法。通过介绍两种算法思想的基本原理，比较两种算法的联系和区别。通过背包问题对比了两种算法的使用特点和使用范围。【关键字】动态规划；贪心算法；背包问题1、引言为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于

2、解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和0/1背包问题进行分析，介绍贪心算法和动态规划算法的区别。2、背包问题的提出给定n种物品(每种物品仅有一件)和一个背包。物品i的重量是wi，其价值为pi，背包的容量为M。问应如何选择物品装入背包，使得装入背包中的物品的总价值最大,每件物品i的装入情况为xi，得到的效益是

3、pi*xi。⑴部分背包问题。在选择物品时，可以将物品分割为部分装入背包，即0≤xi≤1(贪心算法)。⑵0/1背包问题。和部分背包问题相似，但是在选择物品装入时要么不装，要么全装入，即xi=1或0。(动态规划算法)。3、贪心算法3.1贪心算法的基本要素能够使用贪心算法的许多例子都是最优化问题，每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行解；使优化函数取得最佳值的可行解称为最优解。此类所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到(这是贪心算法与动态规划的主要区别)。3

4、.2贪心策略的定义贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。)采用自顶向下的、以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的

5、子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。3、3贪心算法的实际应用例子⑴贪心法的基本思路。从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。⑵该算法存在的问题。①不能保证求得的最后解是最佳的；②不能

6、用来求最大或最小解问题；只能求满足某些约束条件的可行解的范围。⑶实现该算法的过程。从问题的某一初始解出发；当能朝给定总目标前进一步时，求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。⑷背包问题分析实例（部分背包问题）。有一个背包,容量是M=150，有7个物品，物品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。其重量和价值如下。物品ABCDEFG重量35306050401025价值10403050354030其中目标函最大。约束条件是装入的物品总重量不超过背包容量：

7、)根据贪心的策略，每次选取单位容量价值最大的物品,成为解本题的策略。可以证明得到最优解为x=[0，1，0，1，7/8，1，1]总价值为：190.6。3、4贪心算法不适于解0/1背包问题0/1背包问题有好几种贪婪策略，每种贪婪策略都要多个步骤来完成，每一步都利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2，w=[100，10，10]

8、，p=[20，15，15]，c=105。当利用价值贪婪准则时，获得的解为x=[1，0，0]，这种方案的总价值为20。而最优解为[0，1，1]，其总价值为30。另一种方案是重量贪婪准则：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解