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