SHARE
TWEET

knapsack

Farid_Mia59 Dec 14th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. float w[100],p[100],x[100];
  4. int n;
  5. class ksack
  6. {
  7. public:
  8. void knapsack(int m,int n)
  9. {
  10.     for(int i=1;i<n;i++)
  11.     {
  12.         int max=i;
  13.         for(int j=i+1;j<=n;j++)
  14.         {
  15.             if((p[j]/w[j])>(p[max]/w[max]))
  16.             {
  17.                 max=j;
  18.             }
  19.         }
  20.         swap(p[max],p[i]);
  21.         swap(w[max],w[i]);
  22.     }
  23.     int u=m;
  24.     int i;
  25.     for(i=1;i<=n;i++)
  26.     {
  27.         if(w[i]>u) break;
  28.     x[i]=1;
  29.     u=u-w[i];
  30.     }
  31.     if(i<=n)
  32.     {
  33.         x[i]=u/w[i];
  34.     }
  35. }
  36.  
  37. void profit(int n)
  38. {
  39.     float sum=0;
  40.     for(int i=1;i<=n;i++)
  41.         sum+=w[i]*x[i]*p[i];
  42.     cout<<endl<<"total profit:"<<sum;
  43. }
  44. };
  45. int main()
  46. {
  47.     ksack k;
  48.     //int n;
  49.     freopen("in.txt","r",stdin);
  50.  
  51.     //cout<<"Enter the number of item :";
  52.     cin>>n;
  53.     //cout<<"Enter the number of profits:";
  54.     for(int i=1;i<=n;i++)
  55.     {
  56.         cin>>p[i]>>w[i];
  57.     }
  58.  cout<<"number of item:"<<n<<endl;
  59.     cout<<"number of profits:";
  60.     for(int i=1;i<=n;i++)
  61.     {
  62.         cout<<p[i]<<" ";
  63.     }
  64.  
  65.       cout<<endl<<"number of weight:";
  66.     for(int i=1;i<=n;i++)
  67.     {
  68.         cout<<w[i]<<" ";
  69.     }
  70.     k.knapsack(60,n);
  71.     cout<<endl<<"number of profits swap:";
  72.     for(int i=1;i<=n;i++)
  73.     {
  74.         cout<<p[i]<<" ";
  75.     }
  76.  
  77.       cout<<endl<<"number of weight swap:";
  78.     for(int i=1;i<=n;i++)
  79.     {
  80.         cout<<w[i]<<" ";
  81.     }
  82.  
  83.     cout<<endl<<"number of portion:";
  84.     for(int i=1;i<=n;i++)
  85.     {
  86.         cout<<x[i]<<" ";
  87.     }
  88.  
  89.     k.profit(n);
  90.     return 0;
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top