先贴代码:
上面的算法没有提供找最优解序列的方法,下面给出找最有解序列的代码
void Trackback(int c[][100],int w[],int m,int n)
{
int i;
for(i=n;i>0;i--)
{
if(c[i][m]==c[i-1][m])//表示序号为i的物品没有被装入背包
x[i]=0;
else
{
x[i]=1;
m-=w[i];
}
}
}
int main()
{
int n,m;/*n为背包个数,m为背包容量*/
int i,j;
printf("input m and n/n");
scanf("%d%d",&m,&n);
int w[10],v[10];/*分别代表各个物品的重量和价值*/
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);/*输入每个物品的重量W和价值V*/
printf("%d",Knapsack(n,m,w,v));
printf("/n");
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
printf("%3d",c[i][j]);
printf("/n");
}
Trackback(c,w,m,n);//找最优解
for(i=1;i<=n;i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;
}
/*
测试用例为:
//10是背包容量,5是背包个数
10 5
2 6
2 3
6 5
5 4
4 6
*/