Fractional Knapsack

Problem

Given two arrays, val[] and wt[] , representing the values and weights of items, and an integer capacity representing the maximum weight a knapsack can hold, determine the maximum total value that can be achieved by putting items in the knapsack. You are allowed to break items into fractions if necessary.
Return the maximum value as a double, rounded to 6 decimal places.

Examples :

Input: val[] = [60, 100, 120], wt[] = [10, 20, 30], capacity = 50
Output: 240.000000
Explanation: By taking items of weight 10 and 20 kg and 2/3 fraction of 30 kg. Hence total price will be 60+100+(2/3)(120) = 240

Input: val[] = [500], wt[] = [30], capacity = 10
Output: 166.670000
Explanation: Since the item’s weight exceeds capacity, we take a fraction 10/30 of it, yielding value 166.670000.

Solution

Calculate the value-to-weight ratio for each item and sort them in descending order. Pick items with the highest ratio first, and if the remaining capacity cannot accommodate a full item, take the required fraction of it. This greedy strategy yields the maximum possible value.

Time - O(nlogn)

Space - O(n)

class Solution {
    
    class Item {
        double value;
        double weight;
        double valuePerWeight;
        
        Item(double value, double weight){
            this.value = value;
            this.weight = weight;
            this.valuePerWeight = value/weight;
        }
        
    
        public double getValue(){
            return this.value;
        }
                
        public double getWeight(){
            return this.weight;
        }
        
        public double getValuePerWeight(){
            return this.valuePerWeight;
        }
    }
    
    public double fractionalKnapsack(int[] val, int[] wt, int capacity) {
        int n = val.length;

        List<Item> items = new ArrayList<>();
        
        for(int i=0; i<n; i++){
            items.add(new Item(val[i], wt[i]));
        }
        
        Collections.sort(items, (a, b) -> Double.compare(b.getValuePerWeight(), a.getValuePerWeight()));
        
        // System.out.println(wtVal);
        int remainingCapacity = capacity;
        double maxVal = 0;
        
        for(int i=0; i<n; i++){
            
            Item item = items.get(i);
            double weight = item.getWeight();
            double valuePerWeight = item.getValuePerWeight();
            
            if(remainingCapacity >= weight){
                remainingCapacity-=weight;
                maxVal += valuePerWeight * weight;
            }
            else {
                maxVal += valuePerWeight * remainingCapacity;
                break;
            }
        }
        
        return maxVal;
        
    }
}