FractionalKnapsack-GreedyMethod.java

//Algorithm 

   // 1. Sort the given array of items according to weight / value(W /V) ratio in descending order.
   // 2 .Start adding the item with the maximum W / V ratio.
   // 3.  Add the whole item, if the current weight is less than the capacity, else, add a portion of the item to the knapsack.
   // 4. Stop, when all the items have been considered and the total weight becomes equal to the weight of the given knapsack.
class itemComparator implements Comparator<Item>
{
    @Override
    public int compare(Item a, Item b) 
    {
        double r1 = (double)(a.value) / (double)(a.weight); 
        double r2 = (double)(b.value) / (double)(b.weight); 
        if(r1 < r2) return 1; 
        else if(r1 > r2) return -1; 
        else return 0; 
    }
}
class Solution{
    double fractionalKnapsack(int W, Item arr[], int n) {
        Arrays.sort(arr, new itemComparator()); 
        
        int curWeight = 0; 
        double finalvalue = 0.0; 
        
        for (int i = 0; i < n; i++) {
       
            if (curWeight + arr[i].weight <= W) {
                curWeight += arr[i].weight;
                finalvalue += arr[i].value;
            }
     
            else {
                int remain = W - curWeight;
                finalvalue += ((double)arr[i].value / (double)arr[i].weight) * (double)remain;
                break;
            }
        }
     
        return finalvalue;
        
    }
}