#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;
}

评论