Fractional Knapsack Problem

Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

In the 0-1 Knapsack problem, we are not allowed to break items. We either take the whole item or don’t take it.

Input: Items as (value, weight) pairs arr[] = {{60, 10}, {100, 20}, {120, 30}} Knapsack Capacity, W = 50; Output: Maximum possible value = 240 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

public class Main {
    static class ItemValue {
        double wt, val;
        Double cost;
        public ItemValue(int wt, int val) {
            this.wt = wt;
            this.val = val;
            cost = new Double(val / wt);
        }
    }

    public static double getMaxValue(int[] wt, int[] val, int capacity) {
        ItemValue[] iVal = new ItemValue[wt.length];
        for (int i = 0; i < wt.length; i++) {
            iVal[i] = new ItemValue(wt[i], val[i]);
        }
        Arrays.sort(iVal, (a, b) -> b.cost.compareTo(a.cost));
        double totalValue = 0d;
        for (ItemValue i : iVal) {
            int curWt = (int) i.wt;
            int curVal = (int) i.val;
            if (capacity - curWt >= 0) {
                // item can be picked whole
                capacity = capacity - curWt;
                totalValue += curVal;
            } else {
                // item cant be picked whole
                double fraction = ((double) capacity / (double) curWt);
                totalValue += (curVal * fraction);
                capacity = (int) (capacity - (curWt * fraction));
                break;
            }
        }
        return totalValue;
    }
}