SabirSazzad

greedy knapsack 0-1

Oct 31st, 2017
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. struct Products{
  4.     string name;
  5.     int weight;
  6.     int totalPrice;
  7.     int unitPrice;
  8.     int taken;
  9. };
  10. void greedyKnapsack(Products p[], int n, int capacity)
  11. {
  12.     int i,currentWeight=0;
  13.     for(i=0;i<n;i++)
  14.     {
  15.         if(currentWeight+p[i].weight<= capacity)
  16.         {
  17.             currentWeight = currentWeight+p[i].weight;
  18.             p[i].taken = 1;
  19.         }
  20.     }
  21.     cout << "--------------------------------------------\n"<<endl;
  22.  
  23.     for(i=0; i<n; i++)
  24.     {
  25.         cout << p[i].name << "-->" ;
  26.         if(p[i].taken==1)
  27.         {
  28.             cout << "Yes\n";
  29.         }
  30.         else
  31.         {
  32.             cout << "No\n";
  33.         }
  34.     }
  35.     float profit=0;
  36.     for(i=0;i<n;i++)
  37.     {
  38.         if(p[i].taken == 1)
  39.         {
  40.             profit = profit + p[i].totalPrice;
  41.         }
  42.     }
  43.     cout << "\n-------------------------------------------\n"<<endl;
  44.     cout << "Total profit: " << profit <<endl;
  45.     cout << "Empty Space: " << capacity-currentWeight <<endl;
  46.  
  47. }
  48.  
  49. int main()
  50. {
  51.     int capacity;
  52.     cout << "Input Capacity: ";
  53.     cin >> capacity;
  54.     int type=0;
  55.     cout << "Input Number of Types: ";
  56.     cin >> type;
  57.     Products p[type];
  58.     int i,j;
  59.     for(i=0; i<type; i++)
  60.     {
  61.         cout << "Input product name: ";
  62.         cin >> p[i].name;
  63.         cout << "Input product weight: ";
  64.         cin >> p[i].weight;
  65.         cout << "Input product total price: ";
  66.         cin >> p[i].totalPrice;
  67.         p[i].unitPrice =  p[i].totalPrice/p[i].weight;
  68.         p[i].taken = 0;
  69.     }
  70.     for(i=1;i<type;++i)
  71.     {
  72.         for(j=0;j<(type-i);++j)
  73.         {
  74.             if(p[j].unitPrice<p[j+1].unitPrice)
  75.             {
  76.                 swap(p[j],p[j+1]);
  77.             }
  78.         }
  79.  
  80.     }
  81.     greedyKnapsack(p,type,capacity);
  82.  
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment