#include<bits/stdc++.h>
using namespace std;

main()
{
    int i,j,n,w,b[10][10],d[10][10];
    int val[]={0,3,4,5,6};
    int wt[]={0,2,3,4,5};
    n=4;
    w=5;
    cout << "Given weight and benefit is shown below : " << endl;
    for(i=1;i<=n;i++)
    {
        cout << wt[i] << "kg = ";
        cout << val[i] << endl;
    }
    for(i=0;i<=n;i++)
    {
        d[i][0]=0;
    }
    for(j=0;j<=w;j++)
    {
        d[0][j]=0;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=w;j++)
        {
            if(wt[i]<=j)
            {
                if(d[i-1][j]>val[i]+d[i-1][j-wt[i]])
                {
                    d[i][j]=d[i-1][j];
                    b[i][j]=0;
                }
                else
                {
                    d[i][j]=val[i]+d[i-1][j-wt[i]];
                    b[i][j]=1;
                }
            }
            else
            {
                d[i][j]=d[i-1][j];
                b[i][j]=0;
            }
        }
    }
    cout << "Maximum weight is : " << w << "kg." << endl;
    j=w;
    for(i=1;i<=n;i++)
    {
        if(b[i][j]==1)
        {
            cout << wt[i] << "kg = ";
            cout << val[i] << endl;
        }
        j=j-wt[i];
    }
    cout << "Maximum benefit is : " << d[n][w] << endl;

    return 0;
}