用动态规划法和贪心法解决背包问题

算法与语言

用动态规划法和贪心法解决背包问题

唐

敏１，刘冠蓉１，邓国强

２

（１．武汉理工大学计算机科学与技术学院，湖北武汉４３００７０；

２．武汉理工大学理学院，湖北武汉４３００７０）

摘要：０－１背包问题和背包问题是一类经典的ＮＰ困难问题。采用动态规划法和贪心法对该问题进行求

解，分析和比较这两种算法在求解同一问题时的差异。

关键词：背包问题；０－１背包问题；动态规划法；贪心法中图分类号：ＴＰ３１２

文献标识码：Ａ

文章编号：１６７２－７８００（２００７）０３－０１１１－０３

１０－１背包问题与背包问题

１．１０－１背包问题

给定ｎ个重量为（ｗ１，ｗ２，∧，ｖｎ）价值为（ｖ１，ｖ２，∧，ｖｎ）的物品和一个承重量为Ｗ的背包，求这些物品中最有价值的一个子集，并且要能够装到背包中。

在选择装入背包的物品ｉ时，对每种物品只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。在这里假设所有的重量和背包的承重量都是正整数。

选择物品装入背包时，可以选择物品的一部分，而不一定要全部装入背包。

２ｎ，所以不论生成独立子集的效率有多高，

穷举查找都会导致一个-（２ｎ）的算法。即对于任何输入都非常缺乏效率的算法。这就是所谓的困难问题，目前没有已知的，效率可以用多项式来表示的算法。

表２穷举过程和实例的解子

集

总重量

总价值

１．４背包问题的形式化描述

给定Ｗ＞０，Ｗｉ＞０，ｖｉ＞０，１≤ｉ≤ｎ，要求找出ｎ元０－１向量（ｘ１，ｘ２，∧，ｘｎ），０≤ｘｉ≤１，１≤

ｎ

ｎ

ｉ≤ｎ使得%ｗｉｘｉ≤Ｗ，而且%ｖｉｘｉ≤Ｗ达

ｉ＝１

ｉ＝１

到最大。

２０－１背包问题的一个小规模的实

例

表１

物品

重量

价值

⊙｛１｝｛２｝｛３｝｛４｝｛１，２｝｛１，３｝｛１，４｝｛２，３｝｛２，４｝｛３，４｝｛１，２，３｝｛１，２，４｝｛１，３，４｝｛２，３，４｝｛１，２，３，４｝

大价值为３７美元。

０２１３２３５４４３５６５７６８

０１２１０２０１５２２３２２３０２５３５

不可行

１．２０－１背包问题的形式化描述

给定Ｗ＞０，Ｗｉ＞０，ｖｉ＞０，１≤ｉ≤ｎ，要求找出ｎ元０－１向量（ｘ１，ｘ２，∧，ｘｎ），ｘｉ∈｛０，１｝，

ｎ

ｎ

１２３４

承重量Ｗ＝５

２１３２

１２美元１０美元２０美元１５美元

１≤ｉ≤ｎ使得%ｗｉｘｉ≤Ｗ，而且&ｖｉｘｉ达

ｉ＝１

ｉ＝１

到最大。因此，０－１背包问题是一个特殊的整数规划问题。

ｎ

考虑下面数据给出的实例：

在０－１背包问题中，采用穷举查找需要考虑给定的ｎ个物品集合的所有子集，为了找出可行的子集（也就是说，总重量不超过背包承重能力的子集）。要计算出每个子集的总重量，然后在它们中间找到价值最大的子集。

因为一个ｎ元素集合的子集数量是

ｍａｘ&ｖｉｘｉ

ｉ＝１

(

****)ｉ****+

３７

不可行不可行不可行

&ｗｘ≤Ｗ

＝１

ｉｉ

ｎ

ｘｉ∈｛０，１｝，１≤ｉ≤ｎ

１．３背包问题最优解为｛物品１，物品２，物品４｝，最

与０－１背包问题类似，所不同的是在

作者简介：唐敏（１９８０－），女，广西桂林人，武汉理工大学助教、硕士，研究方向为智能计算；刘冠蓉，男，武汉理工大学教授，主要研究领域为智能计算、数

据挖掘；邓国强（１９７９－），男，武汉理工大学助教、硕士，研究方向为演化计算。

月号１１１

算法与语言

３动态规划法

表４动态规划算法解背包问题实例次大，且能够装入背包，此时背包已满。这时得到的总价值为３５，它是一个次优解。因此，按物品效益值的非递增次序装包不一定能得到最优解。

为什么每一步使目标函数值获得当前最大增值的贪心策略却没有获得最优解呢？原因在于：虽然每一步获得了效益值的极大增长，但背包容量消耗太快。

（２）以容量为度量标准。物品２（承重

３．１动态规划法的基本思想

动态规划法是一种强有力的算法设计技术，它被广泛用于求解组合最优化问题。这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。

３．２递推公式

为了设计一种动态规划算法，需要推导出一个递推关系，用较小实例的解的形式来表示背包问题的实例的解。

解决０－１背包问题的递推式如下：

优子集的一部分。因为Ｖ［２，３］≠Ｖ［１，３］，物品２是最优选择的一部分，这个最优子集用元素Ｖ［１，３－１］来指定余下的组成部分。同样道理，因为Ｖ［１，２］≠Ｖ［０，２］，物品１是最优解｛物品１，物品２，物品４｝的最后一个部分。

该算法的时间效率和空间效率都属于!（ｎＷ）。用来求最优解的具体组成的

（１）

时间效率属于Ｏ（ｎ＋Ｗ）。

量＝１，价值＝１０美元）承重量最小的首先装包，剩下４个承重量，再装入物品４（承重量＝２，价值＝１５美元），此时剩下２个承重量，装入物品１（承重量＝２，价值＝１２美元），背包已满，此时得到的总价值为３７美元。此时得到了该问题的最优解。

（３）贪心法小结。从用贪心法解决０－１背包问题可以看出，采用不同的贪心策略对求解问题的结果也有所不同。所以，当我们在使用贪心法时，必须证明该算法可以导致问题的最优解。

和在动态规划算法的情况中一样，贪心法通常用来求解最优化问题，即量的最大化或最小化。然而，贪心法不像动态规划算法，它通常包含一个用以寻找局部最优解的迭代过程。在某些实例中，这些局部最优解转变成了全局最优解，而在另外一些情况下，则无法找到最优解。

贪心法在少量计算的基础上作出了正确猜想，而不急于考虑以后的情况，这样，它一步步地来构筑解，每一步均是建立在局部最优解的基础之上，而每一步又都扩大了部分解的规模，做出的选择产生最大效益而又保持可行性。因为每一步的工作很少且基于少量信息，所得算法特别有效。

Ｖ［ｉ，ｊ］＝

ｍａｘ｛Ｖ［ｉ－１，ｊ］，ｖｉ＋Ｖ［ｉ－１，ｊ－ｗｉ］｝如果ｊ－ｗｉ≥０

Ｖ［ｉ－１，ｊ］，如果ｊ－ｗｉ＜０

定义初始条件：当时ｊ≥０时，Ｖ［０，ｊ］＝０；当ｉ≥０时，Ｖ［ｉ，０］＝０

（２）

我们的目标是求Ｖ［ｎ，ｗ］，即一个给定

４

４．１

贪心法

贪心法的基本思想

贪心法总是作出在当前看来最好的选择，也就是说贪心法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心法不能对所有的问题都得到整体最优解，但对于许多问题它能产生整体最优解。在一些情况下，即使贪心法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心法是一种最直接的设计技术，它能应用于求解多种问题。这类问题的一般特征是有ｎ个输入以及一组约束条件，满足约束条件的任一输入的子集称为可行解，其可行解由这ｎ个输入的某个子集组成。显然，满足约束条件的子集可能不止一个，因此，可行解是不唯一的。为了衡量可行解的优劣，事先也给出一定的标准。

物品中能够放进承重量为Ｗ的背包的子集的最大总价值，以及最优子集本身。

３．３动态规划表的设计

当ｉ，ｊ＞０时，为了计算第ｉ行第ｊ列的单元格Ｖ［ｉ，ｊ］，我们拿前一行同一列的单元格与ｖｉ加上前一行左边ｗｉ列的单元格的和作比较，计算出两者的较大值。这个表格可以一行一行地填，也可以一列一列地填。

表３动态规划表

５

５．１

动态规划法和贪心法的分析

动态规划法的设计原理

考虑表１给出的实例，表４给出了用公式（１）（２）填写的动态规划表。

这些标准一般以函数的形式给出，这些函数称为目标函数。可使目标函数达到极值（极大或者极小）的可行解，称为最优解。对于其中的某些问题，可用贪心法求解。

动态规划是基于递归的技术，递归算法通常拥有十分简单的归纳证明。算法设计中一个十分重要的原理，称为最优化原理：给定一个最优的决策序列，每个子系列自身必须是最优的决策序列。

在动态规划算法中，每步所做出的选择往往依赖于相关子问题的解。因而，只有在解出相关子问题后，才能作出选择。

动态规划法通常以自底向上的方式

３．４最优解和最优子集

因此，最大总价值为Ｖ［４，５］＝３７美元。可以通过回溯这个表格单元的计算过程来求得最优子集的组成元素。因为Ｖ［４，５］

４．２用贪心法解０－１背包问题（仍引用表

１的实例）

（１）以目标函数为度量标准进行装包。物品３（承重量＝３，价值＝２０美元）效益最大的首先装包，剩下２个承重量，再装入物品４（承重量＝２，价值＝１５美元）效益

≠Ｖ［３，５］，物品４以及填满背包余下５－２＝３个单位承重量的一个最优子集都包括

在最优解中。而后者是由元素Ｖ［３，３］来表示的。因为Ｖ［３，３］＝Ｖ［２，３］，物品３不是最

算法与语言

解各个子问题。质。问题的最优子结构性质是该问题可用入背包。依此策略一直进行下去，直到背５．２贪心法的基本要素

动态规划算法或贪心法求解的关键特征。

包装满为止。

５．２．１贪心选择性质

５．３动态规划法与贪心法的差异

对于０－１背包问题，贪心选择之所以所谓贪心选择性质是指所求问题的

动态规划法和贪心法都要求问题具不能得到最优解是因为在这种情况下，它整体最优解可以通过一系列局部最优的有最优子结构性质，这是两类算法的一个无法保证最终能将背包装满，部分闲置的选择，即贪心选择来达到。这是贪心法可共同点。但是，对于具有最优子结构的问背包空间使每单位背包空间的价值降低行的第一个基本要素，也是贪心法与动态题应该选用动态规划法还是贪心法求解？了。事实上，在考虑０－１背包问题时，应比规划算法的主要区别。

是否能用动态规划算法求解的问题也能较选择该物品和不选择该物品所导致的贪心法所做出的贪心选择可以依赖用贪心法求解？

最终方案，然后再做出最好选择。由此就于以往所做过的选择，但决不依赖于将来０－１背包问题与背包问题这两类问

导出许多互相重叠的子问题。这正是该问所做的选择，也不依赖于子问题的解。

题都具有最优子结构性质。对于０－１背包题可用动态规划算法求解的另一重要特贪心法通常以自顶向下的方式进行，问题，设Ａ是能够装入容量为Ｗ的背包征。实际上也是如此，动态规划算法的确以迭代的方式做出相继的贪心选择，每做价值的物品集合，则Ａｊ＝Ａ－｛ｊ｝是ｎ－１个物可以有效地解０－１背包问题。

出一次贪心选择就将所求问题简化为规品１，２，∧，ｊ－１，ｊ＋１，∧，ｎ可装入容量为Ｗ－ｗｊ动态规划法和贪心法的基本区别在模更小的子问题。

的背包的具有最大价值的物品集合。对于于，贪心法仅产生一个判定序列，而动态对于一个具体问题，要确定它是否具背包问题，类似地，若它的一个最优解包规划法可能产生许多判定序列，但是按照有贪心选择性质，必须证明每一步所作出含物品ｊ，则从该最优解中拿出所含的物最优原理，包含非局部最优的部分序列的的贪心选择最终导致问题的整体最优解。品ｊ的那部分重量ｗ，剩下的将是ｎ－１个结果肯定不可能是最优的，所以不予考首先考察问题的一个整体最优解，并证明原重物品１，２，∧，ｊ－１，ｊ＋１，∧，ｎ以及重为ｗｊ－

虑。设计贪心法的困难部分就是要证明该可修改这个最优解，使其以贪心选择开ｗ的物品ｊ中可装入容量为Ｗ－ｗ的背包

算法确实是求解了它所需要解决的问题。

始。做出贪心选择后，原问题简化为规模且具有最大价值的物品。

参考文献：

更小的类似子问题。然后，用数学归纳法虽然这两个问题极为相似，但背包问证明，通过每一步做贪心选择，最终可得题可以用贪心法求解，而０－１背包问题却［１］王晓东．算法设计与分析［Ｍ］．北京：清华大

到问题的整体最优解。其中，证明贪心选不能用贪心法求解。用贪心法解背包问题学出版社，２００３．

择后的问题简化为规模更小的类似子问的基本步骤是：首先计算每种物品单位重［２］宋文，吴晟，杜亚军．算法设计与分析［Ｍ］．

重庆：重庆大学出版社，２００２．

题的关键在于利用该问题的最优子结构量的价值ｖｉ／ｗｉ，然后，依贪心选择策略，将［３］ＡｎａｎｙＬｅｖｉｔｉｎ．算法设计与分析基础［Ｍ］．北

性质。

尽可能多的单位重量价值最高的物品装京：清华大学出版社，２００４．

５．２．２最优子结构性质

入背包。若将这种物品全部装入背包后，［４］卢开澄．计算机算法导引—设计与分析［Ｍ］．

当一个问题的最优解包含其子问题

背包内的物品总重量未超过Ｗ，则选择单北京：清华大学出版社，２００３．

的最优解时，称此问题具有最优子结构性

位重量价值次高的物品并尽可能多地装

（责任编辑：曙光）

Ｓｏｌｖｉｎｇ０－１ＫｎａｐｓａｃｋＰｒｏｂｌｅｍｓｂｙＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇＭｅｔｈｏｄａｎｄＧｒｅｅｄｙＭｅｔｈｏｄ

ＴＡＮＧＭｉｎ，ＬＩＵＧｕａｎ－ｒｏｎｇ１，ＤＥＮＧＧｕｏ－ｑｉａｎｇ２

（１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７０，Ｃｈｉｎａ；

２．ＳｃｈｏｏｌｏｆＮａｔｕｒｅＳｃｉｅｎｃｅ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｄｏｇｙ，Ｗｕｈａｎ４３００７０，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：０－１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓａｎｄｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓａｒｅａｃｌａｓｓｉｃａｌＮＰｈａｒｄｐｒｏｂｌｅｍｓ．Ｔｈｉｓｐａｐｅｒａｄｏｐｔｓｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄａｎｄｇｒｅｅｄｙｍｅｔｈｏｄｔｏｓｏｌｖｅｓｕｃｈｐｒｏｂｌｅｍｓ，ｔｈｅｎａｎａｌｙｚｅｓａｎｄｃｏｍｐａｒｅｓｔｈｅｄｉｆｆｅｒｅｎｃｅｓｏｆｔｗｏａｌｇｏ－ｒｉｔｈｍｓ．

Ｋｅｙｗｏｒｄｓ：０－１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓ；ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄ；ｇｒｅｅｄｙｍｅｔｈｏｄ

月号１１３