基于Visual C++的0-1背包问题的动态规划算法

摘要：0-1背包问题是经典的NP问题。本文对0-1背包问题的动态规划算法进行了分析，用Visual C++实现该算法。

关键词：0-1背包；动态规划

中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)17-31378-02

The Dynamic Programming Algorithms of 0-1 Knapsack Problem Based on Visual C++

CHEN Zi-li, PAN Yan-yan

(Fujian Communication Technology College,Fuzhou 350007,China)

Abstract:The 0-1knapsack problem is a classic NP problem.In this paper,the 0-1 knapsack problem and its algorithm is analyzd ,the algorithms is based on Dynamic Programming.And carry out that algorithms in the Visual C++.

Key words:0-1 Knapsack;Dynamic Programming

1 0-1背包问题

0-1背包问题是：已知n个物品的重量及其价值分别为Wi>0和Pi>0，背包的容量假设设为Ci>0，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？

2 几种解法的比较

2.1 动态规划算法

动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小，求解也越容易。

2.2 回溯法

回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。使用递归回溯法解决背包问题的优点在于它算法思想简单， 而且它能完全遍历搜索空间，肯定能找到问题的最优解；但是由于此问题解的总组合数有2n个，因此，随着物件数 n 的增大，其解的空间将以2n级增长，当 n 大到一定程度上，用此算法解决背包问题将是不现实的。

2.3 贪心算法

使用贪心方法求解时计算的复杂度降低了很多。贪心算法是一种不要求最优解，只希望得到较为满意解的方法。一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心方法常以当前情况为基础作最优选择，而不是考虑各种可能的整体情况，所以贪心算法不需要回溯。但是，对于某些情况，实际上有解，而该算法不能找到解。

2.4 分枝-限界法

分枝界限是另一种系统地搜索解空间的方法，与回溯法的主要区别在于对E节点的扩充方式。每个活节点有且仅有一次会变成E节点。当一个节点变为E节点是，则生成从该节点移动一步即可到达的所有新节点。在生产的节点中，抛弃那些不可能导出可行解的节点，其余节点加入到活节点表，然后从表中选择一个节点作为下一个E节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充才结束。

2.5 遗传算法

遗传算法是一类借鉴生物自然选择和自然遗传机制的随机化的搜索算法。它适用于处理传统搜索方法难于解决的复杂和非线性问题。遗传算法是一种群体型操作，该操作以群体中所有个体为对象。选择、交叉和变异是遗传算法的三个主要算子，它们构成了遗传算法的主要操作。使用遗传算法解决物件数较大的背包问题，它具有收敛快、搜索速度快的特点。然而在一般情况下，使用基本遗传算法解决背包问题时，得到问题的近似解也不能满足逼近最优解的要求。

下面介绍用动态规划算法实现0-1背包问题的求解。

3 动态规划算法

3.1 0-1背包问题的描述

3.2 最优子结构性质

0-1背包问题具有最优子结构性质。设(y1,y2,…,yn)是所给0-1背包问题的一个最优解。则

3.3 递归关系

设所给0-1背包问题的子问题：

的最优解值为m(i.j),即m(i.j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，就可以建立计算m(i.j)的递归式如下：

4 C++实现算法

#include

#include

#include

int min(int w,int c)

{int temp;

if (w

else

temp=c;

return temp;}

int max(int w,int c)

{int temp;

if (w>c)temp=w;

else temp=c;

return temp;}

void knapsack(int v[],int w[],int c,int ,int**m)

//求最优值

{int jmax=min(w[n]-1,c);

for(int j=0;j

m[n][j]=0;

for(int jj=w[n];jj

m[n][jj]=v[n];

for(int i=n-1;i>1;i--){ //递归部分

jmax=min(w[i]-1,c);

for(int j=0;j

m[i][j]=m[i+1][j];

for(int jj=w[i];jj

m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);}

m[1][c]=m[2][c];

if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

cout

for(int l=2;l

for(int j=0;j

{cout

cout

int traceback(int **m,int w[],int c,int n,int x[])

//回代，求最优解

{cout

for(int i=1;i

if(m[i][c]==m[i+1][c]) x[i]=0;

else {x[i]=1;

c-=w[i];}

x[n]=(m[n][c])?1:0;

for(int y=1;y

{cout

return x[n];}

void main(){

int n,c;

int**m;

cout

cin>>n>>c;

int *v=new int[n+1];

cout

for(int i=1;i

cin>>v[i];

int *w=new int[n+1];

cout

for(int j=1;j

cin>>w[j];

int *x=new int[n+1];

m=new int*[n+1];//动态的分配二维数组

for(int p=0;p

m[p]=new int[c+1];}

knapsack(v,w,c,n,m);

traceback(m,w,c,n,x);}

5 测试

在Visual C++ 下对该算法进行测试 ：例：背包的容量c＝10，物品个数n＝5，w＝{2,2,6,5,4},

v＝{6,3,5,4,6}。

输出结果： 1 1 0 0 1

背包的总重量：8

背包的总价值：15

6 算法分析

上述算法Knapsack需要O (nc)计算时间，traceback需要O（n）计算时间。采用动态规划算法解决0-1背包问题，并通过编程在Visual C++下进行测试得到了较好的结果，证明了算法的正确性。但是，算法还是有缺陷的，当c很大时，算法需要计算的时间较多，还需改进。

参考文献：

[1]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2004.

[2]刘玉娟,王相海.0-1背包2问题的两种扩展形式及其解法[J].计算机应用研究,2006.

[3]杨晓红.基于Visual C++的0-1背包问题的贪婪算法[J].科技资讯导报,2007.

[4]黄波,蔡之华.0/1背包问题及其解法研究[J].电脑知识与技术,2007.

[5]杨甲明.基于遗传算法的0-1背包问题的求解[D].石家庄经济学院,2006.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。