当前位置: 代码迷 >> C语言 >> [求助]动态规划的背包算法问题
  详细解决方案

[求助]动态规划的背包算法问题

热度:179   发布时间:2005-12-09 15:03:00.0
[求助]动态规划的背包算法问题

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

搜索更多相关的解决方案: 动态规划  算法  背包  

----------------解决方案--------------------------------------------------------
  相关解决方案