Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //{ Driver Code Starts
- #include <bits/stdc++.h>
- using namespace std;
- struct Item{
- int value;
- int weight;
- };
- bool cmp(Item a , Item b){
- double acmp = ((double)(a.value))/((double)(a.weight));
- double bcmp = ((double)(b.value))/((double)(b.weight));
- return acmp > bcmp ;
- }
- class Solution
- {
- public:
- //Function to get the maximum total value in the knapsack.
- double fractionalKnapsack(int w, Item arr[], int n)
- {
- if(n == 1 && arr[0].weight<w)return (double)arr[0].value;
- sort(arr , arr+n , cmp);
- double profit= 0;
- for(int a=0;a<n;a++){
- if((arr[a].weight) <= w){profit += arr[a].value;w = w- arr[a].weight;}
- else {
- profit += w * ((double)arr[a].value/(double)arr[a].weight);
- w=0;
- break;
- }
- }
- return profit;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement