Fractional knapsack

Easy

Problem

Items have values and weights, and the knapsack has capacity W. You may take any fraction of an item. Return the maximum total value you can carry.

Example 1

Input:  values = [60, 100, 120], weights = [10, 20, 30], W = 50
Output: 240

Take items 1 and 2 whole and 2/3 of item 3.

Also asked as: Fractional Knapsack Problem

Test cases

Case 1

Input:    [[60,10],[100,20],[120,30]], 50
Expected: 240

Case 2

Input:    [[500,30]], 10
Expected: 166.66666666666666

Case 3

Input:    [[60,10],[100,20]], 50
Expected: 160

Case 4

Input:    [], 10
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort by value/weight ratio, take greedily, split the last item

Time O(n log n)Space O(1)

Unlike 0/1 knapsack, you can take fractions, so always take from the item with the best value density.

function fractionalKnapsack(items, capacity) { // items: [value, weight]
items.sort((a, b) => b[0] / b[1] - a[0] / a[1]);
let total = 0;
for (const [v, w] of items) {
if (capacity >= w) { capacity -= w; total += v; }
else { total += v * (capacity / w); break; }
}
return total;
}