0---1背包问题的动态规划算法
下面是动态规划的背包算法(0--1背包)
#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<ymax;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<ymax;y++) f[i][y]=f[i+1][y];
for(y=w[i];y<=c;y++)
f[i][y]=(f[i+1][y]>(f[i+1][y-w[i]]+p[i]))?f[i+1][y]:(f[i+1][y-w[i]]+p[i]); }
f[1][c]=f[2][c];
if(c>=w[1])
f[1][c]=(f[1][c]>(f[2][c-w[1]]+p[1]))?f[1][c]:(f[2][c-w[1]]+p[1]);}
void traceback(int w[],int c,int n,int x[])/*得到解向量x*/
{ int i=0;
for(i=1;i<n;i++)
if(f[i][c]==f[i+1][c]) x[i]=0;
else{ x[i]=1; c-=w[i]; }
x[n]=f[n][c]?1:0;}