0-1背包问题（动态规划） 解题报告

利用动态规划，以自底向上的方式解各子问题。

解题思路：此问题可转化为：给定c>0，wi>0，vi>0，1≤i≤n，要求找出一

个n元0-1向量(x1，x2，…，xn)，xi∈{0，1}，1≤i≤n，使得∑wixi≤c，而且

∑vixi达到最大。因此，0-1背包是一个特

殊的整数规划问题：

max ∑vixi

s.t. ∑wixi≤c

xi∈{0，1}，1≤i≤n

代码如下：

#include<iostream>
#include<iomanip>
#include<string>

usingnamespacestd;

intMin(intw,intc)//取较小值
{
return(w<c?w:c);
}

intMax(intw,intc)//取较大值
{
return(w<c?c:w);
}

voidKnapsack(intv[],intw[],intc,intn,int**m)
{
intrange1=Min(w[n]-1,c);
for(intj=0;j<=range1;j++)//如果物品的重量超过负重就都复制为0
m[n][j]=0;
for(j=w[n];j<=c;j++)//对于可以放的
m[n][j]=v[n];
for(inti=n-1;i>1;i--)//从下往上
{
range1=Min(w[i]-1,c);
for(j=0;j<=range1;j++)//如果物品的重量超过负重则不加入
m[i][j]=m[i+1][j];
for(intrange2=w[i];range2<=c;range2++)
m[i][range2]=Max(m[i+1][range2],m[i+1][range2-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<<"最优解:"<<m[1][c]<<endl;
}

voidPrint_Case(int**m,intw[],intc,intn,intx[])//输出物品存放的情况
{
cout<<"得到的一组最优解如下:"<<endl;
for(inti=1;i<n;i++)
if(m[i][c]==m[i+1][c])
x[i]=0;
else
{
x[i]=1;
}
x[n]=(m[n][c])?1:0;
for(inty=1;y<=n;y++)
{
cout<<setw(5)<<x[y];
}
cout<<endl;
return;
}

voidmain()
{
intn,c;
int**m;
cout<<"请输入物品的个数以及重量的上限:";
cin>>n>>c;
int*v=newint[n+1];
cout<<"请输入物品的价值(v[i]:)"<<endl;
for(inti=1;i<=n;i++)
cin>>v[i];
int*w=newint[n+1];
cout<<"请输入物品的重量(w[i]):"<<endl;
for(intj=1;j<=n;j++)
cin>>w[j];
int*x=newint[n+1];
m=newint*[n+1];
for(intp=0;p<n+1;p++)
{
m[p]=newint[c+1];
}
Knapsack(v,w,c,n,m);
Print_Case(m,w,c,n,x);
}