Advertisement
ismaeil

KnapSack

Jan 29th, 2020
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3.  
  4. using namespace std;
  5.  
  6. int val[] = { 1 , 4 , 5 ,7 },
  7.      wt[] = { 1 , 3 , 4 ,5 };
  8.  
  9. int  W = 7;
  10. int n = sizeof(val) / sizeof(int);
  11.  
  12. int knapSack[100][100];
  13.  
  14. int NS( int y , int x ){
  15.     if( y == 0 || x == 0 )
  16.         return 0;
  17.  
  18.     if( knapSack[y][x] == 0){
  19.         if( x-wt[y-1] >= 0 )
  20.             knapSack[y][x] = max( NS( y-1 , x ) , NS( y-1 , x-wt[y-1] ) + val[y-1] );
  21.         else
  22.             knapSack[y][x] = NS( y-1 , x );
  23.     }
  24.     return knapSack[y][x];
  25. }
  26.  
  27. int main()
  28. {
  29.     cout << endl << "Values Array :  ";
  30.     for(int i=0 ; i<n ; i++)
  31.         cout << setw(5) << val[i]; cout <<"\n";
  32.  
  33.     cout << endl << "Weights Array : ";
  34.     for(int i=0 ; i<n ; i++)
  35.         cout << setw(5) <<  wt[i]; cout <<"\n\n\n";
  36.  
  37.     cout << endl << endl << "Value = " << NS( n , W ) ;
  38.  
  39.     cout << "\nKnapsack Table : \n";
  40.     cout << endl;
  41.     for(int i=0 ; i<=n ; i++){
  42.         for(int j=0 ; j<=W ; j++)
  43.             cout<<setw(5)<<knapSack[i][j];
  44.         cout<<endl;
  45.     }
  46.  
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement