用动态规划法和贪心法解决背包问题
“第二空间”通过精心收集，向本站投稿了3篇用动态规划法和贪心法解决背包问题，下面是小编精心整理后的用动态规划法和贪心法解决背包问题，希望能够帮助到大家。
篇1：用动态规划法和贪心法解决背包问题
唐
敏1，刘冠蓉1，邓国强
2
（1．武汉理工大学计算机科学与技术学院，湖北武汉430070；
2．武汉理工大学理学院，湖北武汉430070）
摘要：0－1背包问题和背包问题是一类经典的NP困难问题。采用动态规划法和贪心法对该问题进行求
解，分析和比较这两种算法在求解同一问题时的差异。
关键词：背包问题；0－1背包问题；动态规划法；贪心法中图分类号：TP312
文献标识码：A
文章编号：1672－7800（2007）03－0111－03
10－1背包问题与背包问题
1．10－1背包问题
给定n个重量为（w1，w2，∧，vn）价值为（v1，v2，∧，vn）的物品和一个承重量为W的背包，求这些物品中最有价值的一个子集，并且要能够装到背包中。
在选择装入背包的物品i时，对每种物品只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。在这里假设所有的重量和背包的承重量都是正整数。
选择物品装入背包时，可以选择物品的一部分，而不一定要全部装入背包。
2n，所以不论生成独立子集的效率有多高，
穷举查找都会导致一个-（2n）的算法。即对于任何输入都非常缺乏效率的算法。这就是所谓的困难问题，目前没有已知的，效率可以用多项式来表示的算法。
表2穷举过程和实例的解子
集
总重量
总价值
1．4背包问题的形式化描述
给定W＞0，Wi＞0，vi＞0，1≤i≤n，要求找出n元0－1向量（x1，x2，∧，xn），0≤xi≤1，1≤
n
n
i≤n使得%wixi≤W，而且%vixi≤W达
i＝1
i＝1
到最大。
20－1背包问题的一个小规模的实
例
表1
物品
重量
价值
⊙｛1｝｛2｝｛3｝｛4｝｛1，2｝｛1，3｝｛1，4｝｛2，3｝｛2，4｝｛3，4｝｛1，2，3｝｛1，2，4｝｛1，3，4｝｛2，3，4｝｛1，2，3，4｝
大价值为37美元。
0213235443565768
01210201522322302535
不可行
1．20－1背包问题的形式化描述
给定W＞0，Wi＞0，vi＞0，1≤i≤n，要求找出n元0－1向量（x1，x2，∧，xn），xi∈｛0，1｝，
n
n
1234
承重量W＝5
2132
12美元10美元20美元15美元
1≤i≤n使得%wixi≤W，而且&vixi达
i＝1
i＝1
到最大。因此，0－1背包问题是一个特殊的整数规划问题。
n
考虑下面数据给出的实例：
在0－1背包问题中，采用穷举查找需要考虑给定的n个物品集合的所有子集，为了找出可行的子集（也就是说，总重量不超过背包承重能力的子集）。要计算出每个子集的总重量，然后在它们中间找到价值最大的子集。
因为一个n元素集合的子集数量是
max&vixi
i＝1
(
****)i****+
37
不可行不可行不可行
&wx≤W
＝1
ii
n
xi∈｛0，1｝，1≤i≤n
1．3背包问题最优解为｛物品1，物品2，物品4｝，最
与0－1背包问题类似，所不同的是在
作者简介：唐敏（1980－），女，广西桂林人，武汉理工大学助教、硕士，研究方向为智能计算；刘冠蓉，男，武汉理工大学教授，主要研究领域为智能计算、数
据挖掘；邓国强（1979－），男，武汉理工大学助教、硕士，研究方向为演化计算。
月号111
算法与语言
3动态规划法
表4动态规划算法解背包问题实例次大，且能够装入背包，此时背包已满。这时得到的总价值为35，它是一个次优解。因此，按物品效益值的非递增次序装包不一定能得到最优解。
为什么每一步使目标函数值获得当前最大增值的贪心策略却没有获得最优解呢？原因在于：虽然每一步获得了效益值的极大增长，但背包容量消耗太快。
（2）以容量为度量标准。物品2（承重
3．1动态规划法的基本思想
动态规划法是一种强有力的算法设计技术，它被广泛用于求解组合最优化问题。这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。
3．2递推公式
为了设计一种动态规划算法，需要推导出一个递推关系，用较小实例的解的形式来表示背包问题的实例的解。
解决0－1背包问题的递推式如下：
优子集的一部分。因为V［2，3］≠V［1，3］，物品2是最优选择的一部分，这个最优子集用元素V［1，3－1］来指定余下的组成部分。同样道理，因为V［1，2］≠V［0，2］，物品1是最优解｛物品1，物品2，物品4｝的最后一个部分。
该算法的时间效率和空间效率都属于!（nW）。用来求最优解的具体组成的
（1）
时间效率属于O（n＋W）。
量＝1，价值＝10美元）承重量最小的首先装包，剩下4个承重量，再装入物品4（承重量＝2，价值＝15美元），此时剩下2个承重量，装入物品1（承重量＝2，价值＝12美元），背包已满，此时得到的总价值为37美元。此时得到了该问题的最优解。
（3）贪心法小结。从用贪心法解决0－1背包问题可以看出，采用不同的贪心策略对求解问题的结果也有所不同。所以，当我们在使用贪心法时，必须证明该算法可以导致问题的最优解。
和在动态规划算法的情况中一样，贪心法通常用来求解最优化问题，即量的最大化或最小化。然而，贪心法不像动态规划算法，它通常包含一个用以寻找局部最优解的迭代过程。在某些实例中，这些局部最优解转变成了全局最优解，而在另外一些情况下，则无法找到最优解。
贪心法在少量计算的基础上作出了正确猜想，而不急于考虑以后的情况，这样，它一步步地来构筑解，每一步均是建立在局部最优解的基础之上，而每一步又都扩大了部分解的规模，做出的选择产生最大效益而又保持可行性。因为每一步的工作很少且基于少量信息，所得算法特别有效。
V［i，j］＝
max｛V［i－1，j］，vi＋V［i－1，j－wi］｝如果j－wi≥0
V［i－1，j］，如果j－wi＜0
定义初始条件：当时j≥0时，V［0，j］＝0；当i≥0时，V［i，0］＝0
（2）
我们的目标是求V［n，w］，即一个给定
4
4．1
贪心法
贪心法的基本思想
贪心法总是作出在当前看来最好的选择，也就是说贪心法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心法不能对所有的问题都得到整体最优解，但对于许多问题它能产生整体最优解。在一些情况下，即使贪心法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心法是一种最直接的设计技术，它能应用于求解多种问题。这类问题的一般特征是有n个输入以及一组约束条件，满足约束条件的任一输入的子集称为可行解，其可行解由这n个输入的某个子集组成。显然，满足约束条件的子集可能不止一个，因此，可行解是不唯一的。为了衡量可行解的优劣，事先也给出一定的标准。
物品中能够放进承重量为W的背包的子集的最大总价值，以及最优子集本身。
3．3动态规划表的设计
当i，j＞0时，为了计算第i行第j列的单元格V［i，j］，我们拿前一行同一列的单元格与vi加上前一行左边wi列的单元格的和作比较，计算出两者的较大值。这个表格可以一行一行地填，也可以一列一列地填。
表3动态规划表
5
5．1
篇2：用动态规划法和贪心法解决背包问题
动态规划法的设计原理
考虑表1给出的实例，表4给出了用公式（1）（2）填写的动态规划表。
这些标准一般以函数的形式给出，这些函数称为目标函数。可使目标函数达到极值（极大或者极小）的可行解，称为最优解。对于其中的某些问题，可用贪心法求解。
动态规划是基于递归的技术，递归算法通常拥有十分简单的归纳证明。算法设计中一个十分重要的原理，称为最优化原理：给定一个最优的决策序列，每个子系列自身必须是最优的决策序列。
在动态规划算法中，每步所做出的选择往往依赖于相关子问题的解。因而，只有在解出相关子问题后，才能作出选择。
动态规划法通常以自底向上的方式
3．4最优解和最优子集
因此，最大总价值为V［4，5］＝37美元。可以通过回溯这个表格单元的计算过程来求得最优子集的组成元素。因为V［4，5］
4．2用贪心法解0－1背包问题（仍引用表
1的实例）
（1）以目标函数为度量标准进行装包。物品3（承重量＝3，价值＝20美元）效益最大的首先装包，剩下2个承重量，再装入物品4（承重量＝2，价值＝15美元）效益
≠V［3，5］，物品4以及填满背包余下5－2＝3个单位承重量的一个最优子集都包括
在最优解中。而后者是由元素V［3，3］来表示的。因为V［3，3］＝V［2，3］，物品3不是最
算法与语言
解各个子问题。质。问题的最优子结构性质是该问题可用入背包。依此策略一直进行下去，直到背5．2贪心法的基本要素
动态规划算法或贪心法求解的关键特征。
包装满为止。
5．2．1贪心选择性质
5．3动态规划法与贪心法的差异
对于0－1背包问题，贪心选择之所以所谓贪心选择性质是指所求问题的
动态规划法和贪心法都要求问题具不能得到最优解是因为在这种情况下，它整体最优解可以通过一系列局部最优的有最优子结构性质，这是两类算法的一个无法保证最终能将背包装满，部分闲置的选择，即贪心选择来达到。这是贪心法可共同点。但是，对于具有最优子结构的问背包空间使每单位背包空间的价值降低行的.第一个基本要素，也是贪心法与动态题应该选用动态规划法还是贪心法求解？了。事实上，在考虑0－1背包问题时，应比规划算法的主要区别。
是否能用动态规划算法求解的问题也能较选择该物品和不选择该物品所导致的贪心法所做出的贪心选择可以依赖用贪心法求解？
最终方案，然后再做出最好选择。由此就于以往所做过的选择，但决不依赖于将来0－1背包问题与背包问题这两类问
导出许多互相重叠的子问题。这正是该问所做的选择，也不依赖于子问题的解。
题都具有最优子结构性质。对于0－1背包题可用动态规划算法求解的另一重要特贪心法通常以自顶向下的方式进行，问题，设A是能够装入容量为W的背包征。实际上也是如此，动态规划算法的确以迭代的方式做出相继的贪心选择，每做价值的物品集合，则Aj＝A－｛j｝是n－1个物可以有效地解0－1背包问题。
出一次贪心选择就将所求问题简化为规品1，2，∧，j－1，j＋1，∧，n可装入容量为W－wj动态规划法和贪心法的基本区别在模更小的子问题。
的背包的具有最大价值的物品集合。对于于，贪心法仅产生一个判定序列，而动态对于一个具体问题，要确定它是否具背包问题，类似地，若它的一个最优解包规划法可能产生许多判定序列，但是按照有贪心选择性质，必须证明每一步所作出含物品j，则从该最优解中拿出所含的物最优原理，包含非局部最优的部分序列的的贪心选择最终导致问题的整体最优解。品j的那部分重量w，剩下的将是n－1个结果肯定不可能是最优的，所以不予考首先考察问题的一个整体最优解，并证明原重物品1，2，∧，j－1，j＋1，∧，n以及重为wj－
虑。设计贪心法的困难部分就是要证明该可修改这个最优解，使其以贪心选择开w的物品j中可装入容量为W－w的背包
算法确实是求解了它所需要解决的问题。
始。做出贪心选择后，原问题简化为规模且具有最大价值的物品。
参考文献：
更小的类似子问题。然后，用数学归纳法虽然这两个问题极为相似，但背包问证明，通过每一步做贪心选择，最终可得题可以用贪心法求解，而0－1背包问题却［1］王晓东．算法设计与分析［M］．北京：清华大
到问题的整体最优解。其中，证明贪心选不能用贪心法求解。用贪心法解背包问题学出版社，2003．
择后的问题简化为规模更小的类似子问的基本步骤是：首先计算每种物品单位重［2］宋文，吴晟，杜亚军．算法设计与分析［M］．
重庆：重庆大学出版社，2002．
题的关键在于利用该问题的最优子结构量的价值vi／wi，然后，依贪心选择策略，将［3］AnanyLevitin．算法设计与分析基础［M］．北
性质。
尽可能多的单位重量价值最高的物品装京：清华大学出版社，2004．
5．2．2最优子结构性质
入背包。若将这种物品全部装入背包后，［4］卢开澄．计算机算法导引―设计与分析［M］．
当一个问题的最优解包含其子问题
背包内的物品总重量未超过W，则选择单北京：清华大学出版社，2003．
的最优解时，称此问题具有最优子结构性
位重量价值次高的物品并尽可能多地装
（责任编辑：曙光）
Solving0－1KnapsackProblemsbyDynamicProgrammingMethodandGreedyMethod
TANGMin，LIUGuan－rong1，DENGGuo－qiang2
（1．SchoolofComputerScienceandTechnology，WuhanUniversityofTechnology，Wuhan430070，China；
2．SchoolofNatureScience，WuhanUniversityofTechndogy，Wuhan430070，China）
Abstract：0－1knapsackproblemsandknapsackproblemsareaclassicalNPhardproblems．Thispaperadoptsdynamicprogrammingmethodandgreedymethodtosolvesuchproblems，thenanalyzesandcomparesthedifferencesoftwoalgo－rithms．
Keywords：0－1knapsackproblems；knapsackproblems；dynamicprogrammingmethod；greedymethod
月号113
篇3：用动态规划法与回溯法实现0-1背包问题的比较
用动态规划法与回溯法实现0-1背包问题的比较
1背包问题0-1背包问题：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。问应如何选择装入背包中物品，使得装入背包中物品的总价值最大？
对于一个实例：物品种类N=4，背包容量C=10，物品重量数组W={3，5，2，1}，相应价值数组V={9，10，7，4}。找一个n元0-1向量（x1，x2，x3….xn）xi∈{0,1},1≤i≤n.使得
，
达到最大。下面分别以动态规划法和回溯法来解决这个实例。
2动态规划法
动态规划法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。用一个表来保存记录所有已解决的子问题的答案，在需要的时候再找出已求得的答案，避免重复的计算。
动态规划法适用于解最优化问题。通常可按以下4个步骤：
(1)找出最优解的性质并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时到得的信息，构造最优解。
对于所给0-1背包问题的子问题：
，
的最优值为m（i，j），即m（i，j）是背包容量为j，可悬着物品为i,i+1,….,n时0-1背包问题的最优值。由于0-1背包问题的最优子结构性质，可以建立计算m（i，j）的如下递归式：
（1.1）
（1.2）
从上面算法的执行过程中可以看出假设有Q（n）个子问题,每一个子问题最多需要m次决策,则计算的频率为nm,回溯的频率为n，那么整个过程的算法的时间复杂度为T（n）=nm+n，即为Q（nm）。
3回溯法。
回溯法在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。回溯算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。简单地说就是确定解空间,建立解空间树,用深度优先搜索算法递归搜索解空间树,并同时注意剪枝。
用回溯法解题的步骤：
(1)针对所给问题定义问题的解空间；
(2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效的搜索。
根据上述0-1背包问题的数学描述解向量可以表示成X={X,X,...X|X=0或=1}若X=0,表示第i个物品不装入背包，X=1，表示将第i个物品装入背包。
可以用树的形式将解空间表达出来。树中从第i层到第i+1层的边上的值表示解向量中X的取值，并假定第i层的左子树描述第i个物品被装入背包的情况，右子树描述第i个物品被拒绝的情况。则该0-1背包问题的状态空间树就表示为一棵高度为n的完全二叉树。若n=3时则此0-1背包问题的解空间的结构如图1-1所示。从根结点到叶子结点的.任一路径就对应解空间中的一个解向量
图1-1n=3时，0-1背包问题的解空间树
用回溯法求解0-1背包问题时，可以按照物品的单位价值从大到小排序。计算当前节点的上界,搜索左子树。只有当右子树包含可行解时才搜索右子树。剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时,不需搜索右子树,可将右子树剪去。回溯法用一定的剪枝进行优化,算法的时间复杂度为O(n*2n),n为物品个数。
4总结
动态规划算法：动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解,而且约束条件越多,决策的搜索范围越小,求解也越容易。但是对于规模较大的问题它并不是一个理想的算法。最重要的原因就是它的维数障碍。即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系，这样惊人的增长速度是计算机难以承受的。这就使得直接的动态规划方法求解规划较大的背包问题发生了困难，且目前尚没有好的解决办法。
回溯法：回溯法需要为问题定义一个解空间,这个解空间必须至少包含问题的一个解(可能是最优的)。使用递归回溯法解决背包问题的优点在于它算法思想简单,而且它能完全遍历搜索空间,肯定能找到问题的最优解。但是由于此问题解的总组合数有2个,因此,随着物件数n的增大,其解的空间将以2级增长,当n大到一定程度上,用此算法解决背包问题将是不现实的。
用此两种方法都能得到问题的最优解，从其时间复杂度来看，两者的速度都较慢。
【用动态规划法和贪心法解决背包问题】相关文章：
文档为doc格式
