讨论 / 引自他人的伪代码,再自己加以理解(但鄙人愚昧,不是很理解,只是照搬操作)
liusikai 2013-07-05 16:17:00
点我顶贴 收藏 删除
#define MAXINT 0xFFFFFFF

#include<stdio.h>

int main()

{

int k,V,n,i,j,t,a,b,z;

int w[201],v[201],f[5001][51],temp[51];

scanf("%d%d%d",&k,&V,&n);

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

{

scanf("%d%d",&w[i],&v[i]);

}

for(i=0;i<=V;i++)

{

for(j=1;j<=k;j++)

{

f[i][j]=-MAXINT;

}

}

f[0][k]=0;

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

{

for(j=V;j>=0;j--)

{

if(j-w[i]<0) continue;

for(t=k,a=k,b=k;t>=1;t--)

{

if(f[j][a]>f[j-w[i]][b]+v[i])

{

temp[t]=f[j][a];//.....................................................................储存每个状态可能取到的最优值。

a--;

}

else//if(f[j][a]<=f[j-w[i]][b]+v[i])......为什么同一种条件两种不同表述,答案也不一样。

{

temp[t]=f[j-w[i]][b]+v[i];//...........................................................储存每个状态可能取到的最优值。

b--;

}

}

for(t=1;t<=k;t++)

{

f[j][t]=temp[t];//..............这个循环作用就是把每个状态表示成一个大小为K的数据,并在这个数组中有序的保持该状态可取到的前K个最优值。

}

}

}

z=0;

for(i=1;i<=k;i++)//....................................................................................合并每个状态的值直到第K的值。类似于归并排序。

{

z+=f[V][i];//.........................“如果把每个状态表示成一个大小为K的数组,并在这个数组中有序的保持该状态可取到的前K个最优值,

//......................................那么,对于任何两个状态的max运算等价于两个由大到小的有序队列的合并。”--摘自《背包九讲》

}

printf("%d\n",z);

return 0;

}

#1 liusikai@2013-07-05 16:17:00
回复 删除
希望一位大神给我详细讲讲更深次的理解,小弟只能理解到此了。呵呵呵。。。。
查看更多回复
提交回复