这是01背包问题,2级指针的动态分配内存是不是不怎么对 #include<iostream.h> #include<malloc.h>

min(int x,int y) { return(x<y? x:y); } max(int x,int y) { return(x>y? x:y); }

void Knapsack(int *v,int *w,int c,int n,int **m) { int i,j; int jMax=min(w[n]-1,c); for(j=0;j<=jMax;j++) m[n][j]=0; for(j=w[n];j<=c;j++) m[n][j]=v[n];

for(i=n-1;i>1;i--) { jMax=min(w[i]-1,c); for(j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(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]); }

void Traceback(int **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 c,n; int *v,*w,*x,**m; int i,j; cout<<"输入背包容量c: "; cin>>c; cout<<"输入物品件数n: "; cin>>n; v=new int[n]; w=new int[n]; x=new int[n]; m=new int *[n]; for(i=1;i<n+1;i++) m[i]=new int[c];

cout<<"输入N个物品的价值："<<endl; cin>>v[i]; for(i=0;i<n;i++) cout<<"输入N个物品的重量："<<endl; for(i=0;i<n;i++) cin>>w[i]; cout<<endl; Knapsack(v,w,c,n,m); Traceback(m,w,c,n,x); for(i=0;i<n;i++) { for(j=0;j<n;j++) cout<<m[i][j]; cout<<endl; } for(i=0;i<n;i++) cout<<x[i]; delete [n]v; delete [n]w; delete [n]x; {for (i = 0; i < n+1; i++) delete [c] m[i]; delete [n]m;} }

[此贴子已经被作者于2005-10-15 11:25:34编辑过]