求教一个算法问题
有人能给个最优装载问题的动态规划代码吗？
[装载问题] 有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的
大小都一样，但货箱的重量都各不相同。设第i 个货箱的重量为wi（1≤i≤n），而货船的最大
载重量为c，我们的目的是在货船上装入最多的货物。
如：W = {5,4,3,4,3,2} ; c = 10 ; 可以选{5,3,2}和{4,3,3}
问题点数：100、回复次数：3Top
1 楼aden_wang（小菜牛）回复于 2005-06-05 12:40:58 得分 100
这么简单的问题，就是标准算法吗！代码如下：
void Knapsack(int w[],int c,int n)
{
for(int y=0; y<ymax; y++)
f[0][y]=0;
for(y=w[0]; y<=c; y++)
f[0][y]=w[0];
for(int i=1; i<n; i++)
{
for(y=0; y<ymax; y++)
f[i][y]=f[i-1][y];
for(y=w[i]; y<=c; y++)
f[i][y] = max( f[i-1][y],(f[i-1][y-w[i]]+w[i]) ); }
}
void traceback(int w[],int c,int n,int x[])
{
for(int i=0; i<n-1; i++)
{
if(f[i][c]==f[i+1][c])
{
x[i]=0;
}
else
{
x[i]=1;
c-=w[i];
}
}
x[n-1]=f[n-1][c]?1:0;
}
int _tmain(int argc, _TCHAR* argv[])
{
int s=0,temp=0;
int w[] = {5,4,3,4,3,2};
int m=10;
int n=sizeof(w)/sizeof(w[0]);
int i=0;
int* x = new int[n+1];
Knapsack(w,m,n);
traceback(w,m,n,x);
s=f[n-1][m];
cout<<"the max value is:"<<s<<endl;
for(i=0;i<n;i++)
{
if( x[i]==1 )
{
cout<<"the w:"<<w[i]<<endl;
}
}
getchar();
return 0;
}
Top
2 楼aden_wang（小菜牛）回复于 2005-06-05 12:42:53 得分 0
#define ymax 100
#define nmax 100
using namespace std;
int f[nmax][ymax];Top
3 楼wiali（维埃里）回复于 2005-06-05 23:03:57 得分 0
aden_wang(小菜牛) 你的程序不对啊，最优解是出来的，但是由哪几个组成的不对啊Top
