ISSN1009-3044第6卷第35期(2010年12月)与技术ComputerKnowledgeandTechnology电脑知识
Vol.6,No.35,December2010,pp.10061-10062E-mail:[email protected]电脑知识与技术ComputerKnowledgeandTechnologyhttp://www.dnzs.net.cnTel:+86-551-[1**********]964基于贪心算法的0-1背包问题
陈曦
（九江学院，江西九江332005）
摘要：贪心算法是解决问题的一种算法，因其解决问题时具有简单性、直观性和高效性而备受青睐。当待解决的问题具有最优子结构和贪心选择性质时，就可以考虑用贪心算法求解。0-1背包问题是计算机问题中一个普遍的问题，文章中详述了用贪心算法如何解决0-1背包问题。并得出用贪心算法求解此问题能得到最优解。
关键词：0-1背包；贪心算法；动态规划中图分类号：TP312文献标识码：A文章编号：1009-3044(2010)35-10061-02
BasedontheGreedyAlgorithmof0-1KnapsackProblems
CHENXi
(JiujiangUniversity,Jiujiang332005,China)
Abstract:Thegreedyalgorithmisthesolutiontotheproblemofanalgorithm,becauseofitssolvingproblemswithsimplicity,intuitiveandtheefficiencyisfavour.Whenun-solvedproblemsthathavethemostYouZistructureandmoment-thegreedy-choiceproperties,cancon-sidertousegreedyalgorithm.0-1knapsackproblemsincomputerproblemsisacommonprobleminthetext,wasdescribedbythegreedyalgorithmtosolve0-1knapsackproblems.Andobtainedbygreedyalgorithmforsolvingthisproblemcanobtainoptimalsolutions.Keywords:0-1knapsack;greedyalgorithm;dynamicprogramming
1算法设计与分析是一门集应用性、创造性、实践性为一体的综合性极强的课程[1-2]
一个高效的程序不仅需要“编程技巧”，更需要合理的数据组织和清晰高效的算法。当一个问题具有最优子结构时，根据其具体情况可以用动态规划算法或者贪心算法来求解，但是问题同时具有贪心选择性质时，选择贪心算法更优，贪心算法通常会给出一个简单、直观和高效的解法[3]。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。
作为一种算法设计技术，贪心法是一种简单的方法。与动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。这种局部最优选择并不能保证总能获得全局最优解，但是通常能得到较好的近似最优解。例如，平时购物找钱时，为使找回的零钱的硬币数量最少，从最大面值的币种开始，按递减的顺考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小的面值的币种。这就是在采用贪心算法。这种方法在这里总是最优，因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1,5,和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币，但是最优的解答应是3个5单位面值的硬币。
1.1贪心算法解题思路
贪心算法[4]是经常用到的一种解题方法，往往在解决最优问题时都可以用贪心算法求解。其解题思路为：
1）建立数学模型来描述问题。
2）把求解的问题分成若干子问题。
3）对每一对问题求解，得到子问题的局部最优解。
4）把子问题的解局部最优解合成原来解问题的一个解。
实现该算法的过程：
从问题的某一初始解出发；
while能朝给定总目标前进do
求出可行解的一个元素；
由所有解元素组合成问题的一个可行解。
虽然贪心算法有时并不能得到最优解，但是经过证明贪心算法能提高问题的解决效率。
收稿日期：2010-10-15
作者简介：陈曦（1982-），女，江西九江人，讲师，硕士，主要研究方向为计算机应用。
本栏目责任编辑：谢媛媛软件设计开发10061
ComputerKnowledgeandTechnology电脑知识与技术第6卷第35期(2010年12月)20-1背包问题
0_1背包问题[5-7]是指给定n件物品和一个背包，物品的重量为wi,其价值为ci,背包的容量为W,求从这n件物品中选取一部分物品且对每件物品，要么选，要么不选，要求满足被放入背包的物品重量不超过背包的容量。所有物品的重量之和小于背包的容量。如果所有物品的重量之和小于背包的容量，显然此时的利益为所有物品的价值之和，但实际问题一般是背包的容量小于物品的重量和，这就要求选取适当的背包放入使得利益最大化且物品的总重量不超过背包容量。可以把某个物品装入或者不装入，拥xi表示第i个物品，此时xi=0或xi=1；也可以只装入某个物品的一部分，此时0
假设现在有6个物品，n=6，W=90，表1给出了物品的重
量，价值和单位重量的价值。
为了得到最优解，必须把背包的容量装到最大值，即表1W=90,用贪心策略求解此问题，首先选择一个度量的标准，
即在每次选择的时候按照什么样的标准来选择。经过分析，
此问题可分别按照最大价值、最小重量，单位重量价值最大
的标准。分析如下：
1）按照最大价值优先放的度量标准
即每次在剩余的科选物品中首先选择价值对大的，即首先选择物品3，重量为40，小于背包的总容量，按照此种策略，依次再放物品1和2，最后背包的总容量是40+10+30=80，总价值为60+50+45=155。在剩余的物品中物品6的价值最大，但是其容量为20，大于10，所以不能放入。对应的解空间为{1,1,1,0,0,0}。
2）按照最小重量优先放的标准
即每次在剩余的可选物品中首先选择重量最小的物品，依次选择。即先选择物品1，重量为10，小于背包的总容量90，依次选择物品5、4、6、2，选择物品的总重量为10+10+20+20+30=90,总价值为50+30+20+40+45=185,对应的解空间为{1,1,0,1,1,1}。经过对比，按照最小重量的标准选择物品所得到的价值总量比按照最大价值的标准来选择物品所得到的价值总量要大。即重量标准优于价值标准。
3）按照最大单位价值优先放的标准
即每次在剩余的可选物品中首先选择单位价值最大的物品，依次选择。经过分析，依次选择物品的顺序为1、5、6、2，此时背包的容量为10+10+20+30=70，不足背包的总容量90，还可以放物品3的一半，总重量达到90，此时背包的总价值量为50+30+40+45+30=195，经过比较，此种方法最优。
所以0-1背包问题的选择策略，按照最大单位价值优先选择物品，依次贪心的选择在可选的物品中单位价值最大的物品。为了解决问题，首先对n个物品按照单位价值量排序，然后对排序以后的物品按照单位价值量最大的原则优先选择。算法如下：
GeedyKnapsack(C,W,w,,x,,n)
x=0
v=W
fori=1ton
doifw[i]
thenx[i]=1
v=v-w[i]
ifi
thenx[i]=v/w[i]
returnx
3结论
通过分析，贪心算法解决问题效率高，时间复杂度低，有些问题用贪心算法来求解时间复杂度是线性的，同时，这种算法符合人们的常规思维方式，而被广泛应用与推广。在实际应用中比如活动选择问题，多机调度问题都可以用此算法求解。但是如果不能每次放入物品的一部分，而必须是完整的物体，那么用贪心算法就得不到问题的最优解，此时可考虑用动态规划算法。动态规划算法[8]依据动态规划最优化准则,“作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略”.也就是说,不论前面的状态和策略如何,以后的最优策略只取决于由最初策略所决定的当前状态,最优决策序列中的任何子序列都是最优的动态规划算法基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于动态规划算法求解的问题，经分解得到的子问题往往不是独立的。用一个表来记录所有已解决的子问题的答案。不管子该子问题以后是否用到，只要它被计算过，就将其结果填入表中，这就是动态规划法的基本思路。参考文献：
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]吴哲辉,崔焕庆.算法设计[M].北京:机械工业出版社,2008.王素立,白首华.算法分析与设计教学方法[J].湘潭师范学院学报,2005(9).王晓东.计算机算法设计与分析[M].3版.北京:电子工业出版社,2007.肖衡.浅析贪心算法[J].办公自动化,2009(18).黄娟.0-1背包问题的遗传算法求解及其改进[J].河西学院学报,2010,26(2).黄波,蔡之华.0-1背包问题及其解法研究[J].电脑知识与技术,2007(7).李艳秋,李成城.基于动态规划算法单字估价值的中文自动分词研究[J].内蒙古师范大学学报,2010,39(2).同甲佳.0-1背包问题及贪心算法应用[J].科技信息
,2010(20).
软件设计开发本栏目责任编辑：谢媛媛10062
ISSN1009-3044第6卷第35期(2010年12月)与技术ComputerKnowledgeandTechnology电脑知识
Vol.6,No.35,December2010,pp.10061-10062E-mail:[email protected]电脑知识与技术ComputerKnowledgeandTechnologyhttp://www.dnzs.net.cnTel:+86-551-[1**********]964基于贪心算法的0-1背包问题
陈曦
（九江学院，江西九江332005）
摘要：贪心算法是解决问题的一种算法，因其解决问题时具有简单性、直观性和高效性而备受青睐。当待解决的问题具有最优子结构和贪心选择性质时，就可以考虑用贪心算法求解。0-1背包问题是计算机问题中一个普遍的问题，文章中详述了用贪心算法如何解决0-1背包问题。并得出用贪心算法求解此问题能得到最优解。
关键词：0-1背包；贪心算法；动态规划中图分类号：TP312文献标识码：A文章编号：1009-3044(2010)35-10061-02
BasedontheGreedyAlgorithmof0-1KnapsackProblems
CHENXi
(JiujiangUniversity,Jiujiang332005,China)
Abstract:Thegreedyalgorithmisthesolutiontotheproblemofanalgorithm,becauseofitssolvingproblemswithsimplicity,intuitiveandtheefficiencyisfavour.Whenun-solvedproblemsthathavethemostYouZistructureandmoment-thegreedy-choiceproperties,cancon-sidertousegreedyalgorithm.0-1knapsackproblemsincomputerproblemsisacommonprobleminthetext,wasdescribedbythegreedyalgorithmtosolve0-1knapsackproblems.Andobtainedbygreedyalgorithmforsolvingthisproblemcanobtainoptimalsolutions.Keywords:0-1knapsack;greedyalgorithm;dynamicprogramming
1算法设计与分析是一门集应用性、创造性、实践性为一体的综合性极强的课程[1-2]
一个高效的程序不仅需要“编程技巧”，更需要合理的数据组织和清晰高效的算法。当一个问题具有最优子结构时，根据其具体情况可以用动态规划算法或者贪心算法来求解，但是问题同时具有贪心选择性质时，选择贪心算法更优，贪心算法通常会给出一个简单、直观和高效的解法[3]。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。
作为一种算法设计技术，贪心法是一种简单的方法。与动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。这种局部最优选择并不能保证总能获得全局最优解，但是通常能得到较好的近似最优解。例如，平时购物找钱时，为使找回的零钱的硬币数量最少，从最大面值的币种开始，按递减的顺考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小的面值的币种。这就是在采用贪心算法。这种方法在这里总是最优，因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1,5,和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币，但是最优的解答应是3个5单位面值的硬币。
1.1贪心算法解题思路
贪心算法[4]是经常用到的一种解题方法，往往在解决最优问题时都可以用贪心算法求解。其解题思路为：
1）建立数学模型来描述问题。
2）把求解的问题分成若干子问题。
3）对每一对问题求解，得到子问题的局部最优解。
4）把子问题的解局部最优解合成原来解问题的一个解。
实现该算法的过程：
从问题的某一初始解出发；
while能朝给定总目标前进do
求出可行解的一个元素；
由所有解元素组合成问题的一个可行解。
虽然贪心算法有时并不能得到最优解，但是经过证明贪心算法能提高问题的解决效率。
收稿日期：2010-10-15
作者简介：陈曦（1982-），女，江西九江人，讲师，硕士，主要研究方向为计算机应用。
本栏目责任编辑：谢媛媛软件设计开发10061
ComputerKnowledgeandTechnology电脑知识与技术第6卷第35期(2010年12月)20-1背包问题
0_1背包问题[5-7]是指给定n件物品和一个背包，物品的重量为wi,其价值为ci,背包的容量为W,求从这n件物品中选取一部分物品且对每件物品，要么选，要么不选，要求满足被放入背包的物品重量不超过背包的容量。所有物品的重量之和小于背包的容量。如果所有物品的重量之和小于背包的容量，显然此时的利益为所有物品的价值之和，但实际问题一般是背包的容量小于物品的重量和，这就要求选取适当的背包放入使得利益最大化且物品的总重量不超过背包容量。可以把某个物品装入或者不装入，拥xi表示第i个物品，此时xi=0或xi=1；也可以只装入某个物品的一部分，此时0
假设现在有6个物品，n=6，W=90，表1给出了物品的重
量，价值和单位重量的价值。
为了得到最优解，必须把背包的容量装到最大值，即表1W=90,用贪心策略求解此问题，首先选择一个度量的标准，
即在每次选择的时候按照什么样的标准来选择。经过分析，
此问题可分别按照最大价值、最小重量，单位重量价值最大
的标准。分析如下：
1）按照最大价值优先放的度量标准
即每次在剩余的科选物品中首先选择价值对大的，即首先选择物品3，重量为40，小于背包的总容量，按照此种策略，依次再放物品1和2，最后背包的总容量是40+10+30=80，总价值为60+50+45=155。在剩余的物品中物品6的价值最大，但是其容量为20，大于10，所以不能放入。对应的解空间为{1,1,1,0,0,0}。
2）按照最小重量优先放的标准
即每次在剩余的可选物品中首先选择重量最小的物品，依次选择。即先选择物品1，重量为10，小于背包的总容量90，依次选择物品5、4、6、2，选择物品的总重量为10+10+20+20+30=90,总价值为50+30+20+40+45=185,对应的解空间为{1,1,0,1,1,1}。经过对比，按照最小重量的标准选择物品所得到的价值总量比按照最大价值的标准来选择物品所得到的价值总量要大。即重量标准优于价值标准。
3）按照最大单位价值优先放的标准
即每次在剩余的可选物品中首先选择单位价值最大的物品，依次选择。经过分析，依次选择物品的顺序为1、5、6、2，此时背包的容量为10+10+20+30=70，不足背包的总容量90，还可以放物品3的一半，总重量达到90，此时背包的总价值量为50+30+40+45+30=195，经过比较，此种方法最优。
所以0-1背包问题的选择策略，按照最大单位价值优先选择物品，依次贪心的选择在可选的物品中单位价值最大的物品。为了解决问题，首先对n个物品按照单位价值量排序，然后对排序以后的物品按照单位价值量最大的原则优先选择。算法如下：
GeedyKnapsack(C,W,w,,x,,n)
x=0
v=W
fori=1ton
doifw[i]
thenx[i]=1
v=v-w[i]
ifi
thenx[i]=v/w[i]
returnx
3结论
通过分析，贪心算法解决问题效率高，时间复杂度低，有些问题用贪心算法来求解时间复杂度是线性的，同时，这种算法符合人们的常规思维方式，而被广泛应用与推广。在实际应用中比如活动选择问题，多机调度问题都可以用此算法求解。但是如果不能每次放入物品的一部分，而必须是完整的物体，那么用贪心算法就得不到问题的最优解，此时可考虑用动态规划算法。动态规划算法[8]依据动态规划最优化准则,“作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略”.也就是说,不论前面的状态和策略如何,以后的最优策略只取决于由最初策略所决定的当前状态,最优决策序列中的任何子序列都是最优的动态规划算法基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于动态规划算法求解的问题，经分解得到的子问题往往不是独立的。用一个表来记录所有已解决的子问题的答案。不管子该子问题以后是否用到，只要它被计算过，就将其结果填入表中，这就是动态规划法的基本思路。参考文献：
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]吴哲辉,崔焕庆.算法设计[M].北京:机械工业出版社,2008.王素立,白首华.算法分析与设计教学方法[J].湘潭师范学院学报,2005(9).王晓东.计算机算法设计与分析[M].3版.北京:电子工业出版社,2007.肖衡.浅析贪心算法[J].办公自动化,2009(18).黄娟.0-1背包问题的遗传算法求解及其改进[J].河西学院学报,2010,26(2).黄波,蔡之华.0-1背包问题及其解法研究[J].电脑知识与技术,2007(7).李艳秋,李成城.基于动态规划算法单字估价值的中文自动分词研究[J].内蒙古师范大学学报,2010,39(2).同甲佳.0-1背包问题及贪心算法应用[J].科技信息
,2010(20).
软件设计开发本栏目责任编辑：谢媛媛10062