背包问题的多种解法

admin管理员组

文章数量:1612719

2024年5月1日发(作者：)

一、 问题描述

0/1背包问题:

现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W

i

，价值为正整数V

i

，

背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物

品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，

不允许只取一部分）

二、 算法分析

根据问题描述，可以将其转化为如下的约束条件和目标函数：



n





w

i

x

i

W

(1)



i1



x{0,1}(1in)



i

max



v

i

x

i

(2)

i1

n

于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的

解向量

X

(

x

1

,

x

2

,

x

3

,......,

x

n

)

。

首先说明一下0-1背包问题拥有最优解。

假设

(

x

1

,

x

2

,

x

3

,......,

x

n

)

是所给的问题的一个最优解，则

(x

2

,x

3

,......,x

n

)

是下面问题的



n

n





w

i

x

i

Ww

1

x

1

max



v

i

x

i

。如果不是的话，设

(

y

2

,

y

3

,......,

y

n

)

是这

一个最优解：



i2

i2



x{0,1}(2in)



i

个问题的一个最优解，则



vy



vx

ii

i2i2

nn

ii

，且

w

1

x

1





wy

i

i2

n

i

W

。因此，

v

1

x

1





v

i

y

i

v

1

x

1





v

i

x

i





v

i

x

i

，这说明

(

x

1

,

y

2

,

y

3

,........,

y

n

)

是所给的0-1背包问

i2i2i1

nnn

题比

(

x

1

,

x

2

,

x

3

,........,

x

n

)

更优的解，从而与假设矛盾。

穷举法：

用穷举法解决0-1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能

的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价

值最大的子集。由于程序过于简单，在这里就不再给出，用实例说明求解过程。下面给出

了4个物品和一个容量为10的背包，下图就是用穷举法求解0-1背包问题的过程。

10

W1=7

V1=12

W2=3

V2=12

背包物品1物品2

W3=4

V3=40

W4=5

V4=25

物品3物品4

（a） 四个物品和一个容量为10的背包

序号

1

2

3

4

5

6

7

子集

空集

{1}

{2}

{3}

{4}

{1，2}

{1，3}

总重量

0

7

3

4

5

10

11

总价值

0

42

12

40

25

54

不可行

序号

9

10

11

12

13

14

15

子集

{2，3}

{2，4}

{3，4}

{1,2,3}

{1,2,4}

{1,3,4}

{2,3,4}

总重量

7

8

9

14

15

16

12

总价值

52

37

65

不可行

不可行

不可行

不可行

8 {1，4} 12 不可行 16 {1,2,3,4} 19 不可行

（b）用回溯法求解0-1背包问题的过程

递归法：

在利用递归法解决0-1背包问题时，我们可以先从第n个物品看起。每次的递归调用

都会判断两种情况：

（1） 背包可以放下第n个物品，则x[n]=1，并继续递归调用物品重量为W-w[n],

物品数目为n-1的递归函数，并返回此递归函数值与v[n]的和作为背包问题的

最优解；

（2） 背包放不下第n个物品，则x[n]=0，并继续递归调用背包容量为W，物品数

目为n-1的递归函数，并返回此递归函数值最为背包问题的最优解。

递归调用的终结条件是背包的容量为0或物品的数量为0.此时就得到了0-1背包问题

的最优解。

用递归法解0-1背包问题可以归结为下函数：

KnapSack(n,m)



没有选择物品n



KnapSack(n1,m)

KnapSack(n1,mw[n])v[n]

选择了物品n



第一个式子表示选择物品n后得到价值

KnapSack(n1,mw[n])v[n]

比不选择

物品n情况下得到的价值

KnapSack(n1,m)

小，所以最终还是不选择物品n;第二个式

子刚好相反，选择物品n后的价值

KnapSack(n1,mw[n])v[n]

不小于不选择物品n

情况下得到了价值

KnapSack(n1,m)

，所以最终选择物品n。

在递归调用的过程中可以顺便求出所选择的物品。下面是标记物品被选情况的数组

x[n]求解的具体函数表示：

KnapSack(n,m)KnapSack(n1,m)



0

x[n]



KnapSack(n,m)KnapSack(n1,mw[n])v[n]

1



在函数中，递归调用的主体函数为KnapSack，m表示背包的容量，n表示物品的数

量，x[n]表示是否选择了第n个物品（1—选，0—不选）。每个物品的重量和价值信息分

别存放在数组w[n]和v[n]中。具体的代码见《递归法》文件夹。

贪心法：

0-1背包问题与背包问题类似，所不同的是在选择物品

i(1in)

装入背包时，可以

选择一部分，而不一定要全部装入背包。这两类问题都具有最优子结构性质，相当相似。但

是背包问题可以用贪心法求解，而0-1背包问题却不能用贪心法求解。贪心法之所以得不

到最优解，是由于物品不允许分割，因此，无法保证最终能将背包装满，部分闲置的背包容

量使背包单位重量的价值降低了。事实上，在考虑0-1背包问题时，应比较选择物品和不

选择物品所导致的方案，然后做出最优解。由此导出了许多相互重叠的子问题，所以，0-1

背包问题可以用动态规划法得到最优解。在这里就不再用贪心法解0-1背包问题了。

动态规划法分析：

0-1背包问题可以看作是寻找一个序列

(

x

1

,

x

2

,

x

3

,........,

x

n

)

，对任一个变量

x

i

的判断

是决定

x

i

=1还是

x

i

=0.在判断完

x

i1

之后，已经确定了

(x

1

,x

2

,x

3

,........,x

i1

)

，在判断

x

i

时，会有两种情况：

（1）

背包容量不足以装入物品i，则

x

i

=0，背包的价值不增加；

（2）

背包的容量可以装下物品i，则

x

i

=1，背包的价值增加

v

i

。

这两种情况下背包的总价值的最大者应该是对

x

i

判断后的价值。令

C(i,j)

表示在前

i

(1in)

个物品中能够装入容量为j

(1jW)

的背包的物品的总价值，则可以得到如

C(i,0)C(0,j)0(1)

下的动态规划函数：



C(i1,j)jw

i

C(i,j)



(2)



max{C(i1,j),C(i1,jw

i

)v

i

}jw

i

式（1）说明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，

得到的价值均为0.式（2）第一个式子说明：如果第i个物品的重量大于背包的容量，则装

入第i个物品得到的最大价值和装入第i-1个物品得到的最大价值是相同的，即物品i不能

装入背包中；第二个式子说明：如果第i个物品的重量小于背包的容量，则会有两种情况：

（1）如果把第i个物品装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为

jw

i

的背包中的价值加上第i个物品的价值

v

i

；（2）如果第i个物品没有装入背包，则背

包中物品的价值就是等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二

者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。

我们可以一步一步的解出我们所需要的解。第一步，只装入第一个物品，确定在各种

情况下背包能得到的最大价值；第二步，只装入前两个物品，确定在各种情况下的背包能

够得到的最大价值；一次类推，到了第n步就得到我们所需要的最优解了。最后，

C(n,W)

便是在容量为W的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物

品，从

C(n,W)

的值向前寻找，如果

C(n,W)

>

C(n1,W)

,说明第n个物品被装入了背包

中，前n-1个物品被装入容量为

Ww

n

的背包中；否则，第n个物品没有装入背包中，

前n-1个物品被装入容量为W的背包中。依此类推，直到确定第一个物品是否被装入背

包为止。由此，我们可以得到如下的函数：

x

i







0C(i,j)C(i1,j)

.



1,jjw

i

C(i,j)C(i1,j)

根据动态规划函数，用一个

(n1)(W1)

的二维数组C存放中间变量，

C[i][j]

表

示把前i个物品装入容量为j的背包中获得的最大价值。

设物品的重量存放在数组w[n]中，价值存放在数组v[n]中，背包的容量为W，数组

C[n1][W1]

存放迭代的结果，数组x[n]存放装入背包的物品，动态规划解0-1背包问

题的源代码在文件夹《动态规划法》中。

回溯法分析：

用回溯法解0_1背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子

结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树

搜索，否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前

最优价值。当cp+r≤bestp时，可剪去右子树。计算右子树中解的上界可以用的方法是将

剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一

部分而装满背包。由此得到的价值是右子树中解的上界，用此值来剪枝。

为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考察各

物品即可。在实现时，由MaxBoundary函数计算当前结点处的上界。它是类Knap的私

有成员。Knap的其他成员记录了解空间树种的节点信息，以减少函数参数的传递以及递

归调用时所需要的栈空间。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上

界函数MaxBoundary，以判断是否可以将右子树减去。进入左子树时不需要计算上界，

因为其上界与父结点的上界相同。

在调用函数Knapsack之前，需要先将各物品依其单位重量价值从达到小排序。为此目

的，我们定义了类Objiect。其中，



运算符与通常的定义相反，其目的是为了方便调用

已有的排序算法。在通常情况下，排序算法将待排序元素从小到大排序。

在搜索状态空间树时，由函数Backtrack控制。在函数中是利用递归调用的方法实现了

空间树的搜索。具体的代码见《回溯法》文件夹。

限界分支法：

在解0-1背包问题的优先队列式界限分支法中，活结点优先队列中结点元素N的优先

级由该结点的上界函数MaxBoundary计算出的值uprofit给出。该上界函数在0-1背包

问题的回溯法总已经说明过了。子集树中以结点N为根的子树中任一个结点的价值不超过

。因此我们用一个最大堆来实现活结点优先队列。堆中元素类型为HeapNode,

其私有成员有uprofit,profit,weight,level,和ptr。对于任意一个活结点N，是

活结点N所相应的重量；是N所相应的价值；t是结点N的价值上界，

最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。

在分支限界法中用到的类Knap与0-1背包问题的回溯法中用到的类Knap很相似。

他们的区别是新的类中没有了成员变量bestp，而增加了新的成员bestx。Bestx[i]=1,当

且仅当最优解含有物品i。

在类Knap中有四个函数：

（1） 上界函数MaxBoundary(),计算节点所对应价值的上界；

（2） 函数AddLiveNode()是将一个新的活结点插入到子集树和优先队列中；

（3） 函数MaxKnapsack()实施对子集树的优先队列式分支界限搜索。其中假定物

品依其单位价值从大到小已经排好序。相应的排序过程会在算法的预处理部分

完成。算法中E是当前扩展结点；cw是该结点的重量；cp是该结点的价值；

up是价值上界。算法的while循环不断扩展结点，直到子集树的一个叶结点

成为扩展结点为止。此时优先队列中所有活结点的价值上界均不超过该叶结点

的价值。因此该叶结点相应的解为问题的最优解。

在while循环内部，算法首先检查当前扩展结点的左儿子结点的可行性。如果

该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩

展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它

加入子集树和活结点优先队列。

（4） 函数Knapsack()完成对输入数据的处理。其主要任务是将各物品依其单位重

量价值从达到小排好序。然后调用函数MaxKnapsack()完成对子集树的优先

队列式分支限界搜索。

具体的实现代码在文件夹《分支限界法》中。

三、 时空效率分析

穷举法：

对于一个有n个元素的集合，其子集数量为

2

，所以，不论生成子集的算法效率有

多高，穷举法都会导致一个

O

(2)

的算法。

n

n

递归法：

在递归法的算法体中有一个if判断中出现了两次递归调用比较大小所以它们之间的递

归关系式可以大体表示为：

T(n)2T(n1)C

，其中

T(n)

表示递归法的时间复杂度，

C是常数。求解递归方程可以知道

T(n)

的量级为

O

(2)

。所以递归法解0-1背包问题的

n

时间复杂度为

O

(2)

。递归法是耗费空间最多的算法，每次递归调用都需要压栈，导致

n

栈的使用很频繁。

动态规划法：

由于函数Knapsack中有一个两重for循环，所以时间复杂度为O[(n+1)x(m+1)].

空间复复杂度也是O[(n+1)x(m+1)]，即O（nm）.

回溯法：

由于计算上界的函数MaxBoundary需要O(n)时间，在最坏情况下有

O

(2)

个右儿

n

子结点需要计算上界，所以解0-1背包问题的回溯法算法BackTrack所需要的计算时

间为

O

(

n

2)

.

n

限界分支法：

在使用限界分治法时，就是使用更好的限界剪枝函数使得不必要的解被剔除，但是在

最坏情况下的解仍然是和回溯法是相同的。本算法中也是用到了计算上界的函数

MaxBoundary需要O(n)的时间，而且在最坏情况下有

O

(2)

个结点需要计算上界，所

n

以在最坏情况下的时间复杂度仍然为

O

(

n

2)

。

n

四、 运行结果

递归法输出结果：

动态规划法输出结果：

回溯法输出结果：

分枝限界法输出结果：

五、 分析输出结果

上面测试的是每种算法在两种输入情况下得到的0-1背包问题的解。两种测试数据为：

第一组：背包容量：18； 物品数目：7；

每个物品重量为：11 2 4 8 9 6 10；

每个物品价值为：7 8 8 12 13 4 14。

第二组：背包容量：50； 物品数目：10；

每个物品重量为： 8 12 24 16 6 9 35 21 18 19；

每个物品价值为： 34 32 56 67 54 32 45 56 46 70。

四种实现的算法中，只有回溯法没能够得到预期的最优解。（但是可能是算法设计时的问

题，其实回溯法是穷举法的变形，肯定能够得到最优解的，这里是我设计函数的问题。从递

归法的输出可知，它的结果就是我们想要的最优解）。从时间复杂度和空间复杂度分析可知，

动态规划法的时间复杂度是最小的，但是同时它的空间复杂度又是最大的。这里就可以看出

在设计算法的过程中要考虑它们的平衡问题。在时间要求比较快的情况下，我们就可以选择

动态规划法；在空间要求比较高时，我们就可以使用穷举法或是分枝限界法等其他改进的穷

举法。

各种算法在解背包问题时的比较如下表所示：

算法名称

穷举法

递归法

动态规划法

贪心法

时间复杂度 优点

最优解

最优解

最优解

不一定是最优解

缺点

速度慢

空间消耗大

速度慢

速度快

改进

剪枝

用数组存

递归方程求解

可以作为启发

O

(2

n

)

O

(2

n

)

O(nm)

O

(

n

log

2

n

)

回溯法

分枝限界法

O

(

n

2

n

)

O

(

n

2

n

)

最优解

最优解

速度慢

速度慢

改进剪枝

优化限界函数

从计算复杂性理论看，背包问题是NP完全问题。半个多世纪以来，该问题一直是算法

与复杂性研究的热门话题。通过对0-1背包问题的算法研究可以看出，回溯法和分枝限界

法等可以得到问题的最优解，可是计算时间太慢；动态规划法也可以得到最优解，当

m2

n

n

时，算法需要

O

(

n

2)

的计算时间，这与回溯法存在一样的缺点——计算速度慢；采用贪心

算法，虽然耗费上优于前者，但是不一定是最优解。目前，以上几种方法中回溯法、动态规

划法、贪心法都广泛地应用到不同的实际问题中，并在应用中不断地改进。

本文标签： 物品背包问题