如今的教科书都是很多打印错误的,下面的程序是我根据书上的程序修改过的,但是不能得出正确结果,请教一下各位大虾,是什么问题呢,知道的解析一下,先谢了。
#include<iostream>
using namespace std;
template <class Type>
void Knapsack(Type *v,int *w,int c,int n,Type **m)
{
int jMax= min(w[n]-1,c);
for(int j=0;j<=jMax;j++)
m[n][j]=0;
for(int j=w[n];j<=c;j++)
m[n][j]=v[n];
for(int i=n-1;i>1;i--)
{
jMax=min(w[i]-1,c);
for(int j=0;j<=jMax;j++)
{
m[i][j]=m[i+1][j];
}
for(int j=w[i];j<=c;j++)
m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
template <class Type>
void Traceback(Type **m,int *w,int c,int n,int *x)
{
for(int i=1;i<n;i++)
{
if(m[i][c]==m[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
x[n]==(m[n][c])?1:0;
}
}
void main()
{
int W[5]={2,2,6,5,4},V[5]={6,3,5,4,6};
int n=5,c=10;
int **M;
M=new int *[5];
for(int j=0;j<11;j++)
M[j]=new int;
Knapsack(V,W,10,n-1,M);
int X[6];
Traceback(M,W,10,n,X);
cout<<"得出0-1向量:";
for(int h=0;h<5;h++)
cout<<X[h]<<" ";
}
[此贴子已经被作者于2006-11-3 14:03:47编辑过]