0-1beibao.rar_0-1 背包问题_01 beibao_1背包_N.W._容量维

#include<iostream.h> #include<iomanip.h> #define length 4 int max(int a,int b) { if(a>=b) return a; else return b; } int min(int a,int b) { if(a<=b) return a; else return b; } void knapsack(int v[4],int w[4],int c,int m[4][10]) { int n=length-1; int jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int p=w[n];p<=c;p++) m[n][p]=v[n]; for(int i=n-1;i>=0;i--) { jMax=min(w[1]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(int k=w[i];k<=c;k++) m[i][k]=max(m[i+1][k],m[i+1][k-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[4][10],int w[4],int c,int x[4]) { int n=length-1; 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]>0)?1:0; } void main() { int x[4]={0}; int value[length]={5,4,6,3}; int weight[length]={4,3,5,3}; int c=10; int m[4][10]={0}; knapsack(value,weight,10,m); for(int i=0;i<4;i++) { for(int j=0;j<10;j++) cout<<setw(4)<<m[i][j]; cout<<endl; } traceback(m,weight,10,x); for(int k=0;k<4;k++) cout<<x[k]<<endl; }