KnapSack

#include <iostream>
#include <iomanip>

using namespace std;

int val[] = { 1 , 4 , 5 ,7 },
     wt[] = { 1 , 3 , 4 ,5 };

int  W = 7;
int n = sizeof(val) / sizeof(int);

int knapSack[100][100];

int NS( int y , int x ){
    if( y == 0 || x == 0 )
        return 0;

    if( knapSack[y][x] == 0){
        if( x-wt[y-1] >= 0 )
            knapSack[y][x] = max( NS( y-1 , x ) , NS( y-1 , x-wt[y-1] ) + val[y-1] );
        else
            knapSack[y][x] = NS( y-1 , x );
    }
    return knapSack[y][x];
}

int main()
{
    cout << endl << "Values Array :  ";
    for(int i=0 ; i<n ; i++)
        cout << setw(5) << val[i]; cout <<"\n";

    cout << endl << "Weights Array : ";
    for(int i=0 ; i<n ; i++)
        cout << setw(5) <<  wt[i]; cout <<"\n\n\n";

    cout << endl << endl << "Value = " << NS( n , W ) ;

    cout << "\nKnapsack Table : \n";
    cout << endl;
    for(int i=0 ; i<=n ; i++){
        for(int j=0 ; j<=W ; j++)
            cout<<setw(5)<<knapSack[i][j];
        cout<<endl;
    }

    return 0;
}