Greedy Algorithms8 sections · 316 units
Open in Course

Counterexample - Better Example

A clearer failure

Items: (weight= 33, value= 44), (weight= 22, value= 33), (weight= 22, value= 33). Capacity = 44. Ratios: 1.331.33, 1.51.5, 1.51.5. Greedy takes item 22 or 33 first (ratio 1.51.5), say item 22. Weight used: 22. Item 33 also fits. Total: 33 + 33 = 66.

But taking item 11 alone uses weight 33 and gets value 44. Then item 22 or 33? Item 22 has weight 22, but 33 + 22 = 55 > 44. Does not fit. Hmm, greedy got 66, item 11 alone gets 44. Greedy wins here. Let me find a real counterexample. Testing examples helps you understand when greedy breaks.