编写程序实现0-1背包问题

#include

#include

#define ymax 100

#define nmax 100

float f[nmax][ymax];

void Knapsack(float p[],int w[],int c,int n)

{

int y=0,i=0;

for(y=0;y

f[n][y]=0;

for(y=w[n];y<=c;y++)

f[n][y]=p[n];

for(i=n-1;i>1;i–)

{

for(y=0;y

f[i][y]=f[i+1][y];

for(y=w[i];y<=c;y++)

{ if(f[i+1][y]>f[i+1][y-w[i]]+p[i])

f[i][y]=f[i+1][y];

else

f[i][y]=(f[i+1][y-w[i]]+p[i]);

}

}

f[1][c]=f[2][c];

if(c>=w[1])

if(f[1][c]>(f[2][c-w[1]]))

f[1][c]=f[1][c];

else

f[1][c]=f[2][c-w[1]]+p[1];

}

void Traceback(int w[],int c,int n,int x[])

{

int i=0;

for(i=1;i

{

if(f[i][c]==f[i+1][c])

x[i]=0;

else

{

x[i]=1;

c-=w[i];

}

}

if(x[n]==f[n][c])

x[n]=0;

else

x[n]=1;

}

int main()

{

float s=0,temp=0;

float *p;

int m=0,n=0,i=0,*w,*x;

printf(“请输入背包的最大体积:\nm=”);

scanf(“%d”,&m);

printf(“请输入背包中物品的个数:\nn=”);

scanf(“%d”,&n);

p=(float*)malloc((n+1)*sizeof(float));

printf(“请输入各物品的价值:\n”);

for(i=1;i<=n;i++)

scanf(“%f”,p+i);

w=(int*)malloc((n+1)*sizeof(int));

printf(“请输入各物品的重量:\n”);

for(i=1;i<=n;i++)

scanf(“%d”,w+i);

x=(int*)malloc((n+1)*sizeof(int));

Knapsack(p,w,m,n);

Traceback(w,m,n,x);

s=f[1][m];

printf(“您装入背包中物品的总价值为： %f\n”,s);

for(i=1;i<=n;i++)

{

if(x[i]==1)

{

printf(“ 物品价值: %f”,p[i]);

printf(“ 物品重量: %d\n”,w[i]);

}

}

return 0;

}