蛮力法、动态规划法、回溯法和分支限界法求解01背包问题
- 格式：docx
- 大小：24.90 KB
- 文档页数：22
1 / 22
一、实验内容：
分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。
注：0/1背包问题：给定n种物品和一个容量为C的背包，物品i的重量是w
i，其价值为v
i，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。
二、所用算法的基本思想及复杂度分析：
1.蛮力法求解0/1背包问题：
1）基本思想：
对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。
2）代码:
#include
#include
using namespace std;
#define N 100 //最多可能物体数
struct goods//物品结构体
{
int sign;//物品序号
int w; //物品重量
2 / 22
int p; //物品价值
}a[N];
bool m(goods a,goods b)
{
return (a.p/a.w)>(b.p/b.w);
}
int max(int a,int b)
{
return a
}
int n,C,bestP=0,cp=0,cw=0;
int X[N],cx[N];
/*蛮力法求解0/1背包问题*/
int Force(int i)
{
if(i>n-1){
if(bestP
for (int k=0;k
}
return bestP;
}
3 / 22
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);
return bestP;
}
int KnapSack1(int n,goods a[],int C,int x[])
{
Force(0);
return bestP;
}
int main()
{
goods b[N];
printf("物品种数n: ");
scanf("%d",&n);//输入物品种数
printf("背包容量C: ");
4 / 22
scanf("%d",&C);//输入背包容量
for (int i=0;i
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];
}
int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题printf("蛮力法求解0/1背包问题:\nX=[ ");
for(i=0;i
cout<
printf("]装入总价值%d\n",sum1);
bestP=0,cp=0,cw=0;//恢复初始化
}
3）复杂度分析：
蛮力法求解0/1背包问题的时间复杂度为：T(n)O(2n)。
2.动态规划法求解0/1背包问题：
1）基本思想：
令V(i,j)表示在前i(1in)个物品中能够装入容量为j(1jC)的背包中的物品的最大值，则可以得到如下动态函数： V(i,0)V(0,j)0 V(i1,j)(jw
i)
5 / 22
V(i,j)
maxV(i1,j),V(i1,jw)v(jw)iii
按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。
2）代码：
#include
#include
using namespace std;
#define N 100//最多可能物体数
struct goods//物品结构体
{
int sign;//物品序号
int w;//物品重量
int p;//物品价值
}a[N];
bool m(goods a,goods b)
{
return (a.p/a.w)>(b.p/b.w);
6 / 22
}
int max(int a,int b)
{
return a
}
int n,C,bestP=0,cp=0,cw=0;
int X[N],cx[N];
int KnapSack2(int n,goods a[],int C,int x[])
{
int V[N][10*N];
for(int i=0;i<=n;i++)//初始化第0列
V[i][0]=0;
for(int j=0;j<=C;j++)//初始化第0行
V[0][j]=0;
for(i=1;i<=n;i++)//计算第i行，进行第i次迭代
for(j=1;j<=C;j++)
if(j
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p);j=C;//求装入背包的物品
for (i=n;i>0;i--)
7 / 22
{
if (V[i][j]>V[i-1][j]){
x[i-1]=1;
j=j-a[i-1].w;
}
elsex[i-1]=0;
}
return V[n][C]; //返回背包取得的最大价值
}
int main()
{
goods b[N];
printf("物品种数n: ");
scanf("%d",&n); //输入物品种数
printf("背包容量C: ");
scanf("%d",&C); //输入背包容量
for (int i=0;i
{
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];
}
8 / 22
int sum2=KnapSack2(n,a,C,X);//调用动态规划法求0/1背包问题
printf("动态规划法求解0/1背包问题:\nX=[ ");
for(i=0;i
cout<
printf("]装入总价值%d\n",sum2);
for (i=0;i
{
a[i]=b[i];
}//恢复a[N]顺序
}
3）复杂度分析:
动态规划法求解0/1背包问题的时间复杂度为：T(n)O(nC)。
3.回溯法求解0/1背包问题：
1）基本思想：
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。
对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。
2）代码:
#include
9 / 22
#include
using namespace std;
#define N 100//最多可能物体数
struct goods //物品结构体
{
int sign;//物品序号
int w;//物品重量
int p;//物品价值
}a[N];
bool m(goods a,goods b)
{
return (a.p/a.w)>(b.p/b.w);
}
int max(int a,int b)
{
return a
}
int n,C,bestP=0,cp=0,cw=0;
int X[N],cx[N];
int BackTrack(int i)
{
