程序代码:
#include<stdio.h>
int n=5,w[6]={0,2,2,6,5,4},v[6]={0,6,3,5,4,6},c=10;
int a[10][30];
int f(int n,int c)
{ int i,j,m;
for(i=1;i<=n;i++)
for(j=1;j<=c;j++)
if(j<w[i])a[i][j]=a[i-1][j];
else
{ m=a[i-1][j-w[i]]+v[i];
if(m<a[i-1][j])m=a[i-1][j];
a[i][j]=m;
}
return a[n][c];
}
void g(int n,int c,int x[])
{ int i,j;
i=n,j=c;
while(i>0&&j>0)
if(a[i][j]>a[i-1][j])x[i]=1,i--,j-=w[i];
else x[i]=0,i--;
}
int main()
{ int r,i,j,x[10];
r=f(n,c);
printf(" w v \n");
for(i=0;i<=n;i++)
{ printf("%3d %3d ",w[i],v[i]);
for(j=0;j<=c;j++)
printf("%3d",a[i][j]);
printf("\n");
}
g(n,c,x);
for(i=1;i<=n;i++)
if(x[i])printf("%d",i);
printf("\nr=%d\n",r);
return 0;
}