Advertisement
Md_hosen_zisad

Knapsack(0/1)

Nov 26th, 2018
395
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. main()
  5. {
  6.     int i,j,n,w,b[10][10],d[10][10];
  7.     int val[]={0,3,4,5,6};
  8.     int wt[]={0,2,3,4,5};
  9.    cout<< "Enter number of element :" ;
  10.    cin >> n;
  11.    cout<<"Enter Maximum weight : " ;
  12.    cin>>w;
  13.    cout << "Given weight and benefit is shown below : " << endl;
  14.     for(i=1;i<=n;i++)
  15.     {
  16.         cout << wt[i] << "kg = ";
  17.         cout << val[i] << endl;
  18.     }
  19.     for(i=0;i<=n;i++)
  20.     {
  21.         d[i][0]=0;
  22.     }
  23.     for(j=0;j<=w;j++)
  24.     {
  25.         d[0][j]=0;
  26.     }
  27.     for(i=1;i<=n;i++)
  28.     {
  29.         for(j=1;j<=w;j++)
  30.         {
  31.             if(wt[i]<=j)
  32.             {
  33.                 if(d[i-1][j]>val[i]+d[i-1][j-wt[i]])
  34.                 {
  35.                     d[i][j]=d[i-1][j];
  36.                     b[i][j]=0;
  37.                 }
  38.                 else
  39.                 {
  40.                     d[i][j]=val[i]+d[i-1][j-wt[i]];
  41.                     b[i][j]=1;
  42.                 }
  43.             }
  44.             else
  45.             {
  46.                 d[i][j]=d[i-1][j];
  47.                 b[i][j]=0;
  48.             }
  49.         }
  50.     }
  51.     cout << "Maximum weight is : " << w << "kg." << endl;
  52.     j=w;
  53.     for(i=1;i<=n;i++)
  54.     {
  55.         if(b[i][j]==1)
  56.         {
  57.             cout << wt[i] << "kg = ";
  58.             cout << val[i] << endl;
  59.         }
  60.         j=j-wt[i];
  61.     }
  62.     cout << "Maximum benefit is : " << d[n][w] << endl;
  63.  
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement