SabirSazzad

greedy knapsack fractional

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