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;
}
}