Greedy Algorithms8 sections · 316 units
Open in Course

0/1 Knapsack - Why Greedy Fails

Discrete items block

In 00/11 knapsack, items are indivisible. Greedy by ratio fails.

Example: items = [(60,10), (100,20), (120,30)], W = 5050. Greedy: take item 11 (ratio P2), item 22 (ratio P4). Total weight: 3030, value: 160160. Item 33 does not fit.

But items 22 + 33: weight = 5050, value = 220220. Better! The discrete constraint causes blocking. Use DP for 00/11 knapsack.