![](https://csdnimg.cn/release/download_crawler_static/85312046/bg1.jpg)
【摘 要】介绍了计算机算法设计的两种常用算法思想: 贪心算法与动态规划算法。通过
介绍两种算法思想的基本原理,比较两种算法的联系和区别。通过背包问题对比了两种算法
的使用特点和使用范围。
为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了
飞速的发展,线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学
中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不
像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使
用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,
必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,
这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和0/ 1 背包问题进行分
析,介绍贪心算法和动态规划算法的区别。
给定 n 种物品( 每种物品仅有一件) 和一个背包。物品 i 的重量是 w ,其价值为 p ,
背包的容量为 M。问应如何选择物品装入背包,使得装入背包中的物品的总价值最大,每件
物品 i 的装入情况为 x ,得到的效益是 p *x 。
⑴部分背包问题。在选择物品时,可以将物品分割为部分装入背包,即0≤ x ≤1 ( 贪心
⑵ 0/ 1 背包问题。和部分背包问题相似,但是在选择物品装入时要么不装,要么全装
入,即 x = 1 或 0。( 动态规划算法) 。
能够使用贪心算法的许多例子都是最优化问题,每个最优化问题都包含一组限制条件和
一个优化函数,符合限制条件的问题求解方案称为可行解;使优化函数取得最佳值的可行解
称为最优解。此类所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达
到(这是贪心算法与动态规划的主要区别) 。
贪心策略是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值( 或较优解)
的一种解题方法。贪心策略总是做出在当前看来是最优的选择,也就是说贪心策略并不是从
整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解,而许多问题自身的特性
决定了该问题运用贪心策略可以得到最优解或较优解。(注:贪心算法不是对所有问题都能