1. Sort by ratio
Take the most value-dense items first.
items.sort((a, b) => b.value / b.weight - a.value / a.weight)Typorithm · medium
Fractional Knapsack
▷ Interactive algorithm labfractional-knapsackgreedyratio-sortfractionsgreedy-choice
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Fractional Knapsack
Greedy
Sort items by value-to-weight ratio, take whole items greedily, then a fraction of the next to fill up.
Unlike 0/1 knapsack, you may take fractions of an item.
The greedy choice is to always take the most value-dense item available.
When the next item does not fully fit, take just enough of it to fill the remaining capacity.
Preparing algorithm lab…
01
Sort by value / weight, descending.
02
Take whole items while they fit.
03
Fill the last gap with a fraction.
function fractionalKnapsack(items, capacity) {
items.sort((a, b) => b.value / b.weight - a.value / a.weight);
let total = 0;
for (const { value, weight } of items) {
if (capacity >= weight) {
total += value;
capacity -= weight;
} else {
total += value * (capacity / weight);
break;
}
}
return total;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Take whole
If the item fits, take all of it.
if (capacity >= weight)3. Take fraction
Otherwise take the fraction that fills the remaining capacity.
total += value * (capacity / weight)4. Knapsack full
After a partial item the knapsack is full, so stop.
breakA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.