下面是动态规划的背包算法（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;}
请大家帮我分析以下，我有点不明白。最好加一些标注解释。谢谢！！

[此贴子已经被作者于2005-12-11 13:23:23编辑过]

假设给定n个物体和一个背包，物体i的重量为wi，价值为pi（I=1,2,……,n），背包能容纳的物体重量为m，要从这n个物体中选出若干件放入背包，使得放入物体的总重量小于等于m，而总价值达到最大。如果用xi=1表示将第I件物体放入背包，用xi=0表示未放入，则问题变为选择一组xi（I=0,1）

这里的xi只能取0或1两种值，所以称为0-1背包问题

有漏洞,好象有点排列,组合的意思....

[此贴子已经被作者于2005-12-13 20:03:56编辑过]