Question

动态规划算法实现求解0/1背包问题程序，输入应该放入背包中的物品的序号及背包中的总价值。 附：初始化

动态规划算法实现求解0/1背包问题程序，输入应该放入背包中的物品的序号及背包中的总价值。
附：初始化变量int n＝5,c=10；/*物品数量为5个，背包承载量为10*/
int value[5]＝｛6，3，5，4，6｝；
int weight[5]＝｛2，2，6，5，4｝；急！！！！！有加分！
改为输出应该放入背包中物品的序号以及背包中的总价值！！！

Answer 1

#include <stdio.h>
int list[200][200];
int x[15];
int n;
int c;
int s;
int max (int a,int b)
{
if(a>b)return a;
else return b;
}

int ks(int n,int weight[],int value[],int x[],int c)
{
int i,j;
for(i=0;i<=n;i++)
list[i][0]=0;
for(j=0;j<=c;j++)
list[0][i]=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=c;j++)
if(j<weight[i])
list[i][j]=list[i-1][j];
else
list[i][j]=max(list[i-1][j],list[i-1][j-weight[i]]+value[i]);
j=c;
for(i=n-1;i>=0;i--){
if(list[i][j]>list[i-1][j]){
x[i]=1;
j=j-weight[i];
}else x[i]=0;
}

printf("背包中的物品序列号:\n");
for(i=0;i<n;i++)
printf("%d\n",x[i]);

return list[n-1][c]; }
void main(){
int weight[15]={2,2,6,5,4};
int value[15]={6,3,5,4,6};

c=10;
n=5;

s=ks(n,weight,value,x,c);

printf("背包中的总价值:\n");
printf("%d\n",s);

}