蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc

一、实验内容：
分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。
注：0/1背包问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。
二、所用算法的基本思想及复杂度分析：
1.蛮力法求解0/1背包问题：
1）基本思想：
对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。
2）代码:
#include<iostream>
#include<algorithm>
usingnamespacestd;
#defineN100 //最多可能物体数
structgoods //物品结构体
{
intsign; //物品序号
intw; //物品重量
intp; //物品价值
}a[N];
boolm(goodsa,goodsb)
{
return(a.p/a.w)>(b.p/b.w);
}
intmax(inta,intb)
{
returna<b?b:a;
}
intn,C,bestP=0,cp=0,cw=0;
intX[N],cx[N];
/*蛮力法求解0/1背包问题*/
intForce(inti)
{
if(i>n-1){
if(bestP<cp&&cw+a[i].w<=C){
for(intk=0;k<n;k++) X[k]=cx[k];//存储最优路径
bestP=cp;
}
returnbestP;
}
cw=cw+a[i].w;
cp=cp+a[i].p;
cx[i]=1; //装入背包
Force(i+1);
cw=cw-a[i].w;
cp=cp-a[i].p;
cx[i]=0; //不装入背包
Force(i+1);
returnbestP;
}
intKnapSack1(intn,goodsa[],intC,intx[])
{
Force(0);
returnbestP;
}
intmain()
{
goodsb[N];
printf("物品种数n:");
scanf("%d",&n); //输入物品种数
printf("背包容量C:");
scanf("%d",&C); //输入背包容量
for(inti=0;i<n;i++) //输入物品i的重量w及其价值v
{
printf("物品%d的重量w[%d]及其价值v[%d]:",i+1,i+1,i+1);
scanf("%d%d",&a[i].w,&a[i].p);
b[i]=a[i];
}
intsum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题
printf("蛮力法求解0/1背包问题:\nX=[");
for(i=0;i<n;i++)
cout<<X[i]<<"";//输出所求X[n]矩阵
printf("] 装入总价值%d\n",sum1);
bestP=0,cp=0,cw=0;//恢复初始化
}
3）复杂度分析：
蛮力法求解0/1背包问题的时间复杂度为：。
2.动态规划法求解0/1背包问题：
1）基本思想：
令表示在前个物品中能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数：

按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第个阶段。最后，便是在容量为的背包中装入个物品时取得的最大价值。
2）代码：
#include<iostream>
#include<algorithm>
usingnamespacestd;
#defineN100 //最多可能物体数
structgoods //物品结构体
{
intsign; //物品序号
intw; //物品重量
intp; //物品价值
}a[N];
boolm(goodsa,goodsb)
{
return(a.p/a.w)>(b.p/b.w);
}
intmax(inta,intb)
{
returna<b?b:a;
}
intn,C,bestP=0,cp=0,cw=0;
intX[N],cx[N];
intKnapSack2(intn,goodsa[],intC,intx[])
{
intV[N][10*N];
for(inti=0;i<=n;i++) //初始化第0列
V[i][0]=0