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

使用动态规划和贪婪方法解决背包问题

算法和语言

使用动态规划和贪婪方法解决背包问题

唐

敏1、刘关荣1、邓国强

２

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

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

摘要：0-1背包问题与背包问题是一类经典的NP难问题，采用动态规划和贪心法求解该问题。

解答，分析比较两种算法在解决同一问题时的区别。

关键词：背包问题；0-1背包问题；动态规划；贪心方法

文档识别码：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 使得 %vixi≤W，且 %vixi≤W 达到

我=1

我=1

到最大限度。

20-1背包问题的小规模实现

例子

表格1

事物

重量

价值

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

最高价值为 37 美元。

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

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

不可行

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

２１３２

12 美元 10 美元 20 美元 15 美元

１≤i≤n 使得 %wiｘi≤Ｗ, 且 &vixi 达到

我=1

我=1

因此0-1背包问题是一个特殊的整数规划问题。

n

考虑以下数据给出的示例：

在 0-1 背包问题中，穷举搜索需要考虑给定的 n 个物品集合的所有子集。为了找到一个可行子集（即总重量不超过背包承载能力的子集），必须计算每个子集的总重量，然后从中找到重量最大的子集。

由于 n 个元素的集合的子集数量为

麦克斯和维西

我=1

****）我****+

３７

不可行 不可行 不可行

&wｘ≤Ｗ

=1

二

n

xi∈{０，１}，１≤i≤n

1.3 背包问题的最优解是{物品1贪心法与动态规划方法的异点，物品2，物品4}。

与 0-1 背包问题类似，不同之处在于

作者简介：汤敏(1980-)，女，广西桂林人，武汉理工大学助理教授、硕士，研究方向为智能计算；刘关荣，男，武汉理工大学教授，主要研究领域为智能计算、计算机科学等。

据挖掘；邓国强（1979-），男，武汉理工大学助理教授，硕士，研究方向为进化计算。

月份编号 111

算法和语言

3.动态规划

表4 动态规划算法解决背包问题示例 第二大项和 可以放入背包，背包已满。此时得到的总价值为35，为次优解。因此，按物品收益值非递增顺序装箱不一定能得到最优解。

为什么每一步都最大化目标函数值的贪婪策略无法得到最优解呢?原因是虽然每一步收益值都有很大的提高，但是背包容量消耗得太快了。

（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]=

如果 j-wi≥0，则 max{V[i-1,j],vi+V[i-1,j-wi]}

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加上上一行左列的单元格进行比较，取两者的较大值。此表可以逐行填写，也可以逐列填写。

表3 动态规划表

５

5.1

动态规划与贪婪方法分析

动态规划的设计原理

考虑表1给出的例子，表4给出了填写公式（1）和（2）的动态规划表。

这些准则通常以函数的形式给出，称为目标函数。能使目标函数达到极值（最大值或最小值）的可行解称为最优解。对于其中一些问题，可以用贪婪法来解决。

动态规划是一种递归技术，而递归算法通常具有非常简单的归纳证明。算法设计中一个非常重要的原则称为最优化原则：给定一个最优决策序列，每个子序列本身必须是一个最优决策序列。

在动态规划算法中，每一步的选择往往取决于相关子问题的解，因此只有在相关子问题得到解决后才能做出选择。

动态规划通常以自下而上的方式进行。

3.4 最优解与最优子集

因此，最大总价值为V[4,5] = 37美元。通过追溯该表单元的计算过程，可以找到最优子集的组成部分。

4.2 用贪心法解决0-1背包问题（仍参考表格

1' 示例）

（1）以目标函数为度量进行打包。首先打包收益最大的商品 3（重量 = 3，价值 = 20 美元），然后打包剩余 2 个重量的商品 4（重量 = 2，价值 = 15 美元）。

≠Ｖ［３，５］，物品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背包问题具有最优子结构的性质，贪心法通常以自上而下的方式进行。对于0-1背包问题，设A为容量为W的背包。实际上，动态规划算法确实是以迭代的方式进行逐次贪心选择，每次做出一组有价值的物品，则Aj=A-{j}为n-1个物品，这样可以有效解决0-1背包问题。

贪婪选择将问题简化为具有较小模型的子问题。动态规划方法与贪婪方法的基本区别在于模型较小。

背包中价值最大的物品集合。对于一个具体问题，判断其是否存在背包问题，同样，若其最优拆包规划方法可能产生很多判断序列，但根据贪心选择性质，必须证明每一步都包含物品j，那么最优原则取出最优解中包含的物品，包括非局部最优的部分序列，最终得到问题的整体最优解。物品j部分的权重w，剩下的将是肯定不是最优的n-1个结果，因此不予考虑。首先考察问题的整体最优解，证明物品1，2，∧，j-1，j+1，∧，n的原始权重和wj-

设计贪婪方法的难点在于证明这个最优解可以被修改，使得贪婪选择为w的物品j可以装入容量为Ww的背包中。

该算法确实解决了它应该解决的问题。

经过贪婪选择之后，原问题简化为选择规模最大、价值最大的项。

参考：

然后利用数学归纳法，虽然两个问题很相似，但背包问题证明，通过在每一步做出贪婪的选择，最终问题可以用贪婪的方法解决，而0-1背包问题不能用贪婪的方法解决[1]王晓东.算法设计与分析[M].北京:清华大学

得到了问题的全局最优解。其中，证明了贪婪选择不能用贪婪方法解决。用贪婪方法解决背包问题，中国科学院出版社，2003。

将后选择问题简化为类似较小规模的子问题的基本步骤是:首先计算出各个项目的单位权重[２]宋文,吴胜,杜亚军.算法设计与分析[M].

重庆:重庆大学出版社,2002.

该问题的关键在于利用问题的最优子结构量vi/wi的值，然后根据贪婪选择策略，[3] Anany .算法设计与分析基础[M]。

自然。

尽量包装单位重量价值最高的物品。北京：清华大学出版社，2004年。

5.2.2 最优子结构性质

如果把这些物品全部放入背包，[4]陆开程.计算机算法导论-设计与分析[M].

当问题的最优解包含其子问题时

若背包内物品总重量不超过W，则选择单个北京：清华大学出版社，2003。

当找到最优解时，该问题被认为具有最优子结构

放置下一个最有价值的物品，并尽可能多地打包。