Fractional Knapsack
In the fractional knapsack problem, items can be broken into fractions. Unlike the 0/1 knapsack, greedy works: take items with the highest value-to-weight ratio first.
Algorithm: Sort items by value/weight ratio descending. Then take as much as possible of each item until the knapsack is full.
Java implementation:
static class Item { int value, weight; double ratio; }
public static double fractionalKnapsack(Item[] items, int capacity) {
Arrays.sort(items, (a,b) -> Double.compare(b.ratio, a.ratio));
double totalValue = 0.0;
for (Item item : items) {
if (capacity >= item.weight) {
capacity -= item.weight;
totalValue += item.value;
} else {
totalValue += item.value * ((double) capacity / item.weight);
break;
}
}
return totalValue;
}
Time: O(n log n) for sorting.
Two Minute Drill
- Fractional knapsack allows taking fractions of items.
- Greedy by value/weight ratio works.
- Sort items by ratio descending.
- Time O(n log n).
Need more clarification?
Drop us an email at career@quipoinfotech.com