#include <stdio.h>
int V [100][100][100];
int max(int a,int b)
{
if(a>=b)
return a;
else
return b;
}
int KnapSack(int n,int w[100],int z[100],int v[100],int x[100],int c,int b)
{
int i,p,q;
for(i=0;i<=n;i++)
V[i][0][0]=0;
for(p=0;p<=c;p++)
for(q=0;q<=b;q++)
V[0][p][q]=0;
for(i=0;i<=n-1;i++)
for(p=0;p<=c;p++)
for(q=0;q<=b;q++)
if(p<w[i]&&q<z[i])
V[i][p][q]=V[i-1][p][q];
else
V[i][p][q]=max(V[i-1][p][q],V[i-1][p-w[i]][q-z[i]]+v[i]);
p=c;
q=b;
for(i=n-1;i>=0;i--)
{
if(V[i][p][q]>V[i-1][p][q])
{
x[i]=1;
p=p-w[i];
q=q-z[i];
}
else
x[i]=0;
}
printf("最优解为:\n");
for(i=0;i<n;i++)
printf("%d ",x[i]);
printf("\n");
int r=0;
for(i=0;i<n;i++)
{
if(x[i]==1)
r+=v[i];
else
r+=0;
}
return r;
}
void main()
{
int k,w[100],z[100],v[100],x[100],n,i,c,b;
printf("请输入背包的最大容量\n");
scanf("%d",&c);
printf("请输入背包的最大容积\n");
scanf("%d",&b);
printf("请输入物品数\n");
scanf("%d",&n);
printf("请分别输入物品的重量\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("请分别输入物品的体积\n");
for(i=0;i<n;i++)
scanf("%d",&z[i]);
printf("请分别输入物品的价值\n");
for(i=0;i<n;i++)
scanf("%d",&v[i]);
k=KnapSack(n,w,z,v,x,c,b);
printf("最大物品价值为%d\n:",k);
}
int V [100][100][100];
int max(int a,int b)
{
if(a>=b)
return a;
else
return b;
}
int KnapSack(int n,int w[100],int z[100],int v[100],int x[100],int c,int b)
{
int i,p,q;
for(i=0;i<=n;i++)
V[i][0][0]=0;
for(p=0;p<=c;p++)
for(q=0;q<=b;q++)
V[0][p][q]=0;
for(i=0;i<=n-1;i++)
for(p=0;p<=c;p++)
for(q=0;q<=b;q++)
if(p<w[i]&&q<z[i])
V[i][p][q]=V[i-1][p][q];
else
V[i][p][q]=max(V[i-1][p][q],V[i-1][p-w[i]][q-z[i]]+v[i]);
p=c;
q=b;
for(i=n-1;i>=0;i--)
{
if(V[i][p][q]>V[i-1][p][q])
{
x[i]=1;
p=p-w[i];
q=q-z[i];
}
else
x[i]=0;
}
printf("最优解为:\n");
for(i=0;i<n;i++)
printf("%d ",x[i]);
printf("\n");
int r=0;
for(i=0;i<n;i++)
{
if(x[i]==1)
r+=v[i];
else
r+=0;
}
return r;
}
void main()
{
int k,w[100],z[100],v[100],x[100],n,i,c,b;
printf("请输入背包的最大容量\n");
scanf("%d",&c);
printf("请输入背包的最大容积\n");
scanf("%d",&b);
printf("请输入物品数\n");
scanf("%d",&n);
printf("请分别输入物品的重量\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("请分别输入物品的体积\n");
for(i=0;i<n;i++)
scanf("%d",&z[i]);
printf("请分别输入物品的价值\n");
for(i=0;i<n;i++)
scanf("%d",&v[i]);
k=KnapSack(n,w,z,v,x,c,b);
printf("最大物品价值为%d\n:",k);
}