Advertisement
Oppenheimer

Fractional kanpsack

Jul 9th, 2023
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. //{ Driver Code Starts
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct Item{
  6.     int value;
  7.     int weight;
  8. };
  9.  
  10. bool cmp(Item  a , Item b){
  11.     double acmp = ((double)(a.value))/((double)(a.weight));
  12.     double bcmp = ((double)(b.value))/((double)(b.weight));
  13.     return acmp > bcmp ;
  14. }
  15.  
  16. class Solution
  17. {
  18.     public:
  19.     //Function to get the maximum total value in the knapsack.
  20.     double fractionalKnapsack(int w, Item arr[], int n)
  21.     {
  22.        
  23.         if(n == 1 && arr[0].weight<w)return (double)arr[0].value;
  24.         sort(arr , arr+n , cmp);
  25.         double profit= 0;
  26.         for(int a=0;a<n;a++){
  27.             if((arr[a].weight) <= w){profit += arr[a].value;w = w- arr[a].weight;}
  28.             else {
  29.                 profit += w * ((double)arr[a].value/(double)arr[a].weight);
  30.                 w=0;
  31.                 break;
  32.                
  33.             }
  34.         }
  35.         return profit;
  36.     }
  37.        
  38. };
  39.  
  40.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement