GFG Fractional Knapsack.txt

/*
class Item {
    int value, weight;
    Item(int x, int y){
        this.value = x;
        this.weight = y;
    }
}
*/

class CustomComp implements Comparator<Item>
{
    public int compare(Item a, Item b)
    {
        if((double)a.value/(double)a.weight < (double)b.value/(double)b.weight ) return 1;
        return -1;
    }
}

class Solution
{
    //Function to get the maximum total value in the knapsack.
    double fractionalKnapsack(int W, Item arr[], int n) 
    {
        // Your code here
        Arrays.sort(arr, new CustomComp());
        double profit = 0;
        for(Item i: arr)
        {
            if( i.weight>W )
            {
                profit += ((double)W/(double)i.weight)*i.value;
                break;
            }
            else
            {
                W -= i.weight;
                profit += i.value;
            }
        }
        return profit;
    }
}
// TC: O(nlogn + n), SC: O(1)