#include<iostream.h> #include<fstream.h> //#include<math.h> int m[21][51],w[21],v[21],flag[21]; int min(int a,int b) {     if(a>b)         return b;     else         return a; } int max(int a,int b) {     if(b>a)         return b;     else         return a; } void knapsack(int n,int c) {     int i,j; //    int k=n-1;     int jMax=min(w[n]-1,c);//jMax表示第N个物品不能装入的最大容积     for(i=0;i<=jMax;i++)         {         m[n][i]=0;         }     for(i=w[n];i<=c;i++)         {         m[n][i]=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 trackback(int n,int c) {     int i;     for(i=1;i<n;i++)         if(m[i][c]==m[i+1][c])             flag[i]=0;         else             {             flag[i]=1;             c-=w[i];             }             flag[n]=(m[n][c]>0)?1:0; } int main() {         ifstream fin("F.in");     ofstream fout("F.out");     int n,c,i;     while(fin>>n>>c)         {         for(i=1;i<=n;i++)             {             fin>>w[i]>>v[i];             }         knapsack(n,c);         trackback(n,c);         fout<<m[1][c]<<endl;         fout<<"{";         for(i=1;i<=n;i++)             {             if(i!=1)                 fout<<",";             fout<<flag[i];             }         fout<<"}"<<endl;         }     fin.close();     fout.close();     return 0; }

评论