knakul853

Untitled

Nov 22nd, 2020
571
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. bool cmp(Item&a, Item&b){
  3.    
  4.      double r1 = (a.value * 1.0)/(a.weight*1.0);
  5.      double r2 = (b.value * 1.0)/(b.weight*1.0);
  6.      return r1 > r2;
  7.    
  8. }
  9.  
  10. // function to return fractionalweights
  11. double fractionalKnapsack(int W, Item arr[], int n)
  12. {
  13.     // Your code here
  14.     double ans = 0;
  15.     sort(arr, arr+n, cmp);
  16.    
  17.     for(int i=0; i<n; i++){
  18.         if(W >= arr[i].weight){
  19.             ans+=arr[i].value;
  20.             W-=arr[i].weight*1.0;
  21.         }
  22.         else{
  23.             ans += ((W*1.0)/(arr[i].weight * 1.0)) * (1.0 * arr[i].value);
  24.             break;
  25.         }
  26.     }
  27.    
  28.     return ans;
  29. }
RAW Paste Data