第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
论文研究-解0-1背包问题的动态规划算法及其两次改进 .pdf
中国科技论文在线
解 0-1 背包问题的动态规划算法及其两次
http://www.paper.edu.cn
改进
许薇，周继鹏**
（暨南大学信息科学技术学院，广州 510632）
摘要：给出了用动态规划算法解决 0-1 背包问题的证明，分析了动态规划算法解决 0-1 背包
问题的不足和性能。然后，针对用该动态规划算法解决 0-1 背包问题的不足，对它进行改进，
改进后的算法称之为 IKP 算法。为了降低 IKP 的空间复杂度，在 IKP 上运用分治策略，得到
的算法称之为 DKnapsack 算法。分析表明，DKnapsack 比起 IKP 在运行时间和资源耗费上都
有很大的优势。而且，相比其它解 0-1 背包问题的算法，DKnapsack 也具有很好的时间复杂
度。最后，用实验论证了理论的正确性。
关键词：0-1 背包问题；动态规划；分治策略；改进
中图分类号：TP311
Using Dynamic Programming To 0-1 Knapsack Problem
Xu Wei, Zhou Ji Peng
(College of Information Science and Technology, JiNan University, GuangZhou 510632)
Abstract: This paper gave proof for using dynamic programming algorithm to solve 0-1 knapsack
problem, analyzed drawback and the performance of this algorithm. Then, based on the feature of
0-1 knapsack problem, this paper improved the algorithm. It was called Algorithm IKP. Finally, in
order
this paper adopted
divided-and-conquered strategy, called Algorithm DKnapsack. Analysis shows that Algorithm
DKnapsack has a great advantage over Algorithm IKP in running time and resource cost.
Keywords: 0-1 knapsack problem; Dynamic programming; Divided-and-conquered; Improvement
spatial complexity of Algorithm One,
reduce
the
to
5
10
15
20
25
0 引言
经典的 0-1 背包问题描述如下：给定具有 n 个物品的物品集和具有容量 c 的背包，其中
每个物品具有价值 jp 和重量 jw ，要求选取物品集的一个子集，使得它们的总价值达到最大
并且重量之和小于等于背包容量 c。我们引进二元变量 jx ，如果选取了物品 j 则 jx = 1，否
30
则 jx = 0 。 用 数 学 表 达 式 描 述 这 个 问 题 ： maximize
z
n
∑
j
1
=
w x
j
j
≤
c
，其中
jx ∈
{0,1}
,
j
∈
n
{1,2,..., }
n
= ∑
j
1
=
p x
j
j
， 且 满 足 约 束 ：
动态规划是解决组合优化最古老的方法之一，尤其是在背包类型的问题上。被忽略了一
段时间以后，这个领域上又出现了若干解决背包问题的新颖方法，见参考文献[1, 2, 3]。在
这里，我们首先介绍用动态规划方法解决背包问题，然后基于 0-1 背包问题的特点，给出一
个改进方法。最后，为了减少程序使用的内存空间的考虑，我们再对这个改进方法做进一步
改进。
35
作者简介：许薇，(1987-)，女，学生，主要研究方向:无线网络。
通信联系人：周继鹏，(1962-)，男，教授，主要研究方向:无线网络。E-mail: tjpzhou@jnu.edu.cn
- 1 -
中国科技论文在线
1 背包问题的动态规划算法
1.1 最优子结构
0-1 背包问题具有最优子结构性质。设 1
（
x
x x
,
2
是下面相应子问题的一个最优解：
则 2,...,
（
x
)n
,...,
http://www.paper.edu.cn
x
)n
是所给 0-1 背包问题的一个最有解，
maximize
z
′ = ∑ ，且
p x
i
i
n
i
=
2
i
w x
≤ −
i
{0,1}, 2
c w x
1 1
i
≤ ≤
n
⎧
∑⎪
i
2
=
⎨ ∈
x
⎪
i
⎩
n
z
若不然，设 2
(
,
z
3
z 是上述子问题的一个最有解，而 2,...,
)n
（
x
不是它的最优解。
由 此 可 知 ，
<∑
x p
i
i
∑ 且 1 1
w x
z p
i
i
n
i
=
2
+
n
∑
i
=
2
w z
i
i
≤
c
。 因
p x
1 1
w x
1 1
+
c
n
w z
i
i
≤∑
x z
,
=
2
i
2
(
这说明 1
,...,
最优解。此为矛盾。
1.2 递推方程
z 是所给 0-1 背包问题的最优解，从而 1
(
)n
x x
,
2
,...,
x 不是所给问题的
)n
,...,
n
i
=
2
x
)n
n
>∑
p z
i
i
+
i
=
2
n
∑ ，
p x
i
i
i
1
=
40
45
设所给 0-1 背包问题的子问题
max
∑ ，且
p x
t
t
n
t
=
i
i
t
n
=
⎧
⎪∑⎪
⎨
⎪
⎪⎩
x
t
w x
t
t
≤
j
∈
{0,1},
i
≤ ≤
t
n
50
的最优值为 f(i, j), 即 f(i, j)是背包容量为 j，可选物品为 i, i+1,…,n 时 0-1 背包问题的最
优值。由 0-1 背包的最优子结构性质，可以建立计算 f(i, j)的递推方程如下：
f i
j
( , )
=
{max{ (
f i
(
+
f i
j
1, ),
+
j
1, )
0 ≤ <
f i
(
j w
i
+
1,
j w
−
i
)
+
p j w
i
i
}
≥
(1)
迭代初始条件为：
f n j
( , )
=
1.3 算法时空复杂度分析
{
p j w
≥
n
n
j w
0 0
≤ <
n
55
60
直接利用这个递推方程编写程序，必须要求物品的重量为整数。在这种情况下，我们可
)ncΟ
)ncΟ
)ncΟ
，空间复杂度为 (
以得到该算法的时间复杂度为 (
，通过仔细地编程我们可以将
空间复杂度降到 (
。表面上该算法是多项式计算时间，其实这是一个伪多项式算法[4]。
当背包容量很大时，计算时间开销是比较大的。例如，当 c > 2^n 时，该动态规划算法需要
Ω
方法，叫做 Combo。这个算法取得了不错的效果。虽然 Combo 的时间复杂度还是 (
但是就平均而言，它几乎避免了最坏情形的出现。由于紧致上下界的约束，大部分案例可以
计算时间。Martello, Pisinger 和 Toth[5]提出一种动态规划算法结合紧致上下界的
，
n
n
( 2 ^ )
)ncΟ
在合理的时间内得到解决。下面的优化没有涉及界限的概念，而是从上面给出的问题特点进
行优化。
- 2 -
中国科技论文在线
2 第一次优化
http://www.paper.edu.cn
事实上，注意到计算 f(i, j)的递推式在变量 j 是连续变量，即背包容量是实数时仍成立。
该 函 数 是 关 于 变量 j 的 阶 梯 状 单调 不 减 函 数,即对 于 有 限 个
= < <…< ， 满 足
j
j
,0
1
f
i
i x
( ,
( , )
=
f
。跳跃点是这一类函数的描述特征。在一般情况下，函数 f(i,
f i j
( ,
)
<
1
f
i x
( , )
j)由其全部跳跃点唯一确定。如图 1 所示。
f i j
( ,
)k
x
j
≤ <
t
f i j
( ,
)
2
f
i
( ,
=
...
< <
j
)(
t
= −∞ <
，
j +
t
1
i x
( , )
j
k
≤
j
2
j
)(
，
和
j
1
x
x
(
)
)
)
f
j
k
k
f(i, j)
(x, f(i, x))
x
c
j
i
S
{(
使用有序集合
=
X
二元组（X,Y）其中
S
,
i
算 1
+
1
=
X Y X w Y p
i
i
( ,
=
}
1
+
− ∈
f
j
,
t
j Y
,
t
S
)
i
图 1 函数 f(i, j)
k
t
}
j ， iS 的每一个元素是一个有序
i
f
j
≤ ≤ 表示 ( ,
)t
)) | 0
t
nS + =
i
j
f
，可以从 1iS + 计算 iS ,首先计
)
( ,
{0,0}
t
。注意到 1
65
70
75
85
i
−
{( , )|(
=
iS + 计算 iS 。注意，如果 1iS + 包含的两个有
现在，可以通过合并有序二元组集合 1iS + 和 1
1
X≥ ，那么根据函数 ( , )
j 非减性，可以删
X Y 和 2
X Y ，这个点叫做受控跳跃点[6]。下面我们通过一个例子说明这种方法。
X Y ，满足 1
Y
Y≤ 且 1
X
(
(
)
)
,
,
(
)
f
i
,
2
2
1
2
序元组 1
除元组 1
1
设 n=3，背包重量 w 向量（2，3，4），对应价值 p 向量（1，2，5），背包容量 c=6。
80
那么根据上面算法可以得到：
3
4
1
2
=
S
4
1
S
2
1
=
=
=
=
{(3, 2),(5,3)}
{(2,1)}
S
3
1
{(4,5),(6,6),(7,7),(9,8)}
{(0,0)};
=
{(0, 0),(2,1)};
{(0,0),(2,1),(3,2),(5,3)};
=
{(0,0),(2,1),(3, 2),(4,5), (6,6)}
S
S
S
S
注意，我们要清除受控跳跃点和那些 X 大于背包容量 c 的元组。如果将生成元组按 X
有序插入，那么最后一个生成的集合里面 X 最大的元组即是所要答案。通过回溯，可以得
到所选物品。伪代码描述如下：
(1)Algorithm IKP (p, w, n, c)
(2){
(3) for (i = n; i >= 2; i--) {
(4)
iS + = {(X, Y)|(X – iw , Y – ip ) ∈
1iS + and X ≤ c};
1nS + = {(0,0)};
1
1
(5)
iS = MergeSet (
1iS + ,
1
iS + );
1
- 3 -
90
95
100
105
110
115
120
中国科技论文在线
http://www.paper.edu.cn
2S ;
(6) }
(7) (XL, YL) = last pair in
(8) search reversely in
(9) if ( YL > YM)
(10) else
x =
1 1
(
(11) TraceBack
x =
0
1
x x
,
2
3
...,
x
)n
2S , pick up a pair (
X Y′
,
)
′ , if
X w c
′ +
≤ , then YM =
1
Y
′ +
p
1
2.1 第一次优化时空复杂度分析
1
i
(|
|)
x
i
n
)
x 做
n
)
iS +
1
iS + 需要
1
iS + =
1
1
算 1
)
|)
iS 表示对 ,...,
上 述 算 法 的 主 要 计 算 量 在 于 计 算 有 序 二 元 组 集 合 iS (1
≤ ≤ 。 由 于
iw p 相加。故计
1iS + ⊕ (
iw p 。运算符“⊕ ”表示集合 1iS + 的有序二元组分别和(
,
,
i
i
。从 iS
iS +
(|
1
Ο
Ο
计算时间。合并和并清除受控跳跃点也需要计算时间
2n i− + 次判定以后到的所有可能状态，状态表示成有
的定义可以看出，
序二元组（X, Y）,其中 X 是背包所有物品的重量，Y 是对应的价值。为了得到 1iS − ， 1ix − 的
可能取值为 0 或者 1，如果取 0，结果状态与 iS 相同，如果取 1，在 iS 每个状态上增加
w p−
iS 得到 1iS − 。因此，
− 便得到结果状态，新增的状态为 1iS − ，于是合并 iS 和 1
(
,
)
i
i
1
1
S
| 2 |
S
S
|
|
|
|
i
i
i
≤ ， 1
− ≤
1
∑
∑
S
2
n
1
+ −
i n
2
≤ ≤
从而改进后的算法的计算时间复杂度为 (2 )nΟ
iS
|
，最坏的情况下所有的二元组都不能被清除 ，此时
2
n
[6]。此时，改进后算法的计算时间复杂性为 (min{ , 2 })n
iw
i n
≤ ≤（
nc
Ο
。当所给物品的重量 1
S
=
是整数
|
|
=
。容
2
i n
≤ ≤
−
1
i
|
i
i
)
i
)
c
n
1,(1
≤ ≤
|
≤ +
时，|
易看出，空间复杂度为 (2 )nΟ
3 第二次优化
。
上述的改进在 n 很大时，knapsack 算法由于需要太多的计算资源而缺乏实用性，但是，
在实际应用时，因为通常 p 和 w 都是整数，且 c 远小于 2^n，很多问题都可以在合理的时间
内求解。清除规则会有效地从元组集合清除大部分受控跳跃点。下面我们提出的方法会使
IKP 算法运行时间更快，且占用更少的内存资源。
参考文献[7]，在求解单源最短路径时，采用分治策略大幅度减少了程序使用的内存空
间。在这里我们也采用相同的策略，即分治算法结合我们的 IKP 算法。我们先给出新算法
框架，然后分析新算法的性能。
(1)Algorithm DKnapsack(p, w, n, c)
(2){Divide
(3) partition goods into two disjoint subset n1 and n2 with |n1|≈|n2|≈ n/2
(4) perform IKP([p/2], [w/2], [n/2], c), the result stored in 2-tuple set S
(5) perform IKP(p-[p/2], w-[w/2], n - [n/2], c), the result stored in 2-tuple set T
(6)Conquer
(7) orderly pick off pair (a, b)∈S1, reversely pick off pair (u, v)∈T1
(8) if b + v greater than found result so far and a + u <= c
- 4 -
125
130
135
中国科技论文在线
http://www.paper.edu.cn
(9) then result = b + v; j = index of (a,b) in S; k = index of (u, v) in T;
(10) if cursor in S1 greater |S1| or cursor in T1 less than 1
(11) then exit
(12) else if a + u < c then cursor in S1 move forward, if a + u >= c then cursor in T1 move
backward
(13) goto (7)}
下面通过一个具体实例说明算法 DKnapsack 执行过程
n = 5, c = 11, w = {2, 2, 6, 5, 4}, p = {6, 3, 5, 4, 6}。
算法将物品集划分成两个基数最多差 1 的子集。
n1 = 2, c = 11, w1 = {2, 2}, p1 = {6, 3}
n2 = 3, c = 11, w2 = {6, 5, 4}, p2 = {5, 4, 6}
算法 IKP 分别在两个子集上执行，得到有序二元组集合 S 和 T，最终结果如下：
S1 = {(0, 0), (2, 6), (4, 9)} T1 = {(0, 0), (4, 6), (9, 10)}
最后，我们顺序遍历 S1 和逆序遍历 T1 可以得到结果 max p = 16，然后，我们可以从所
选物品的下标开始，回溯得到所选的物品。
4 算法分析
140
基于对 IKP 算法的分析我们得到
|
S
| 2 n
⎢
=
⎣
/2
⎥
⎦
，
|
T
| 2 n
⎡
=
⎢
/2
⎤
⎥
，最坏情况下，即没有受控
T
S
|
|
跳跃点的情况下， 1
=
n⎡
/2
(2
⎤
Ο
⎢
⎥
所需的存储空间为
|
1
)
| 2n
=
1
−
，所以算法 DKnapsack 运行时间为
Ο
(min{2
⎡
⎢
n
/2
⎤
⎥
,
nc
})
，
。
5 实验
145
同都是对 0-1 背包问题的动态规划算法的改进，我们现在将 DKnapsack 算法与参考文献
[9] 提 出 的 改 进 算 法 ( 在 参 考 文 献 [9] 称 之 为 例 程 ks) 比 较 。 实 验 平 台 的 配 置 为 ：
Intel(R),Pentium(R),Dual CPU T2390,内存为 2GB，在 Visual c++ 6.0 上得到 c++程序。程序的
数据随机产生，范围在（0, 1000）之间。三种算法在数据集上各运行 20 次，取其平均值。
150
数据规模
N=25,c =1000
N=25, c =10000
N=30, c =1000
N=30,c =10000
表 1 背包容量比较小的情况下 3 种解法的平均时间耗费对比(ms)
动态规划
0
16
15
32
ks
235
235
422
436
表 2 背包容量比较大的情况下 3 种解法的平均时间耗费对比(ms)
数据规模
N=5,c =100000
N=8,c =100000
N=8,c =1000000
N=20,c =100000
N=20,c =1000000
N=30,c =1000000
6 结束语
动态规划
32
47
516
156
1547
2500
ks
0
0
0
125
125
422
DKnapsack
24
62
47
125
DKnapsack
0
0
0
47
47
125
155
从实验可以看出，在背包容量比较小的情况下，DKnapsack 的平均时间耗费跟动态规划
是比较接近的，比起 ks 有较大的优势。动态规划在背包容量比较小的情况下比起 DKnapsack
- 5 -
中国科技论文在线
http://www.paper.edu.cn
在时间耗费上占优主要是因为其代码的紧凑性和逻辑的简明性，DKnapsack 的逻辑是比较复
杂的。在背包容量比较大的情况下，比起另外两个算法，Dknapsack 的优势就很大了，这跟
我们算法分析的预期结果是一致的。
未来的工作可以将 DKnapsack 结合参考[5]提出的 0-1 背包问题的紧致上下界和参考文
献[8]关于动态规划结合分枝限界法解 0-1 背包问题的性能的论断继续探索 DKnapsack 的优
化。
[参考文献] (References)
[1] Andonov, R., Poirriez, V., Rajopadhye, S.: Efficient dynamic programming for the unbounded knapsack
problem. Technical Report LIMAV-RR 96-7, University of Valenciennes, 1996.
[2] Kellerer, H., Mansini, R., Pferschy, U., Speranza, M. G.: An efficient fully polynomial approximation scheme
for the subset-sum problem. Technical Report 14/1997, Faculty of Economics,UniversityGraz, submitted. See also
Proceedings of the 8th ISAAC Symposium. SpringerLecture Notes Comput. Sci. 1350, 394–403 (1997).
[3] Pisinger, D.: Algorithms for knapsack problems. Ph.D. thesis, DIKU, University of Copenhagen Report 95/1,
1995.
[4] Martello, S., Pisinger, D., Toth, P., 2000. New trends in exact algorithms for the 0-1 knapsack problem.
European Journal of Operational Research 123, 325–332.
[5] S. Martello, D. Pisinger and P. Toth (1997). Dynamic programming and tight bounds for the 0-1 knapsack
problem, Research Report DEIS, University of Bologna, OR/97/1.
[6] 王晓东. 计算机算法设计与分析(第三版). 电子工业出版社 2007
[7] Munro, J. I., Ramirez, R. J.: Reducing space requirements for shortest path problems. Oper. Res.30, 1009–1013
(1982).
[8] Vincent Poirriez, Nicola Yanev, Rumen Andonov: A hybrid algorithm for the unbounded knapsack problem.
Elsevier B.V. 6, 110-124 (2009)
[9] 石海鹤，揭安全，薛锦云. 0_1 背包问题的一种新解法. 计算机工程. 2008, 34(17)
160
165
170
175
180
- 6 -
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
