Noesis
3.7.5Algorithm Paradigms

When greedy fails — 0 - 1 knapsack counter-example

1,947 words9 min readdifficulty · medium
🇮🇳 Yeh note Hinglish mein padho →

WHAT is the 0/1 knapsack problem?

WHAT does greedy do here?

The natural greedy heuristic for knapsack:

  1. Compute value-density (value per unit weight) ρi=vi/wi\rho_i = v_i / w_i for each item.
  2. Sort items by ρi\rho_i descending.
  3. Walk the list; take an item if it still fits in the remaining capacity.

WHY it fails for 0/1 — the counter-example

In 0/1, you can't slice the last item. So greedy may leave wasted capacity, and that gap is exactly where a better combination hides.

Figure — When greedy fails — 0 - 1 knapsack counter-example

WHERE greedy's correctness proof collapses

HOW to actually solve 0/1 knapsack (the fix)

Use Dynamic Programming — consider every item and remember the best value for each capacity.

Running DP on the example gives K(3,50)=220K(3,50)=220 ✓ — matching B+C.

Flashcards

What property must a problem have for greedy to be provably optimal?
A greedy-choice property (a locally optimal choice is part of some globally optimal solution) plus optimal substructure, provable by an exchange argument.
Why does greedy solve fractional knapsack but not 0/1?
Fractional allows slivers, so you can always fill the bag exactly and the exchange argument holds; 0/1's integrality means a whole item can waste capacity and block a better combo. :::
State the 0/1 knapsack greedy counter-example.
W=50W=50; A(10,60), B(20,100), C(30,120). Greedy by density takes A+B = 160; optimum is B+C = 220.
What is the value-density greedy heuristic?
Sort items by vi/wiv_i/w_i descending, take each if it fits in remaining capacity.
Write the 0/1 knapsack DP recurrence.
K(i,c)=max⁡(K(i−1,c), vi+K(i−1,c−wi))K(i,c)=\max(K(i-1,c),\, v_i+K(i-1,c-w_i)) if wi≤cw_i\le c, else K(i−1,c)K(i-1,c); base K(0,c)=0K(0,c)=0.
Runtime of the DP solution?
O(nW)O(nW) (pseudo-polynomial — depends on the numeric value of WW).
What approximation guarantee can you get cheaply for 0/1 knapsack?
A ½-approximation: take max⁡\max(density-greedy value, best single item that fits).
Why does sorting by value alone fail?
A high-value heavy item can monopolize capacity and block a higher-total-value subset of lighter items.
Recall Feynman: explain to a 12-year-old

Imagine a small backpack and three toys. The "grab the best-bang-for-its-size toy first" trick works if you could cut toys into pieces — you'd always fill every empty corner. But real toys can't be cut! So sometimes grabbing the "best per size" toy first leaves an awkward empty space, and you miss out on two other toys that together would've fit perfectly and been worth more. To find the truly best haul, you have to try both choices for each toy — "take it" or "leave it" — and remember the best result for every possible amount of leftover space. That careful try-both method is dynamic programming.

Connections

  • Greedy Algorithms — when local choices do work (Huffman, MST, activity selection)
  • Fractional Knapsack — the version where greedy is optimal (exchange argument)
  • Dynamic Programming — the correct paradigm for 0/1 knapsack
  • Optimal Substructure and Greedy-Choice Property — the two properties greedy needs
  • NP-hardness — 0/1 knapsack is NP-hard; DP is pseudo-polynomial, not polynomial
  • Approximation Algorithms — ½-approx and FPTAS for knapsack
  • Exchange Argument — the proof technique that passes for fractional, fails for 0/1

Concept Map

maximize value under W

uses heuristic

picks highest

leaves

hides

gives

gives

27% worse than

breaks

greedy is optimal for

contrasts with

myopic choice forecloses

0/1 Knapsack: take whole or none

Maximize total value

Greedy: sort by density rho

Densest item first

Wasted capacity

Better combination B plus C

Greedy total 160

Optimal total 220

Integrality constraint: no fractions

Fractional knapsack: x in 0 to 1

Fills bag exactly

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, greedy algorithm ka funda simple hai: har step pe jo "abhi sabse achha" lag raha hai use utha lo aur peeche mud ke mat dekho. Kayi problems me ye trick perfectly kaam karti hai — jaise fractional knapsack me, jahan tum item ka tukda bhi le sakte ho. Wahan density (value per kg) ke hisab se sort karke utha lo, aur bag ka har corner bhar jaata hai, koi space waste nahi hoti. Iska proof bhi solid hai (exchange argument se).

Lekin 0/1 knapsack me ek bada twist hai: item ya to pura lo ya bilkul mat lo, tukda nahi chalega. Bas yahi cheez greedy ko tod deti hai. Example: capacity 50, items A(10kg,60), B(20kg,100), C(30kg,120). Greedy density se A aur B uthata hai (total 160), phir C nahi fit hota aur 20 unit space waste ho jaati hai. But asli optimal answer to B+C = 220 hai, jo poora bag bhar deta hai! Greedy ne A ko greedily uthaya, aur wahi A ne baaki ka space "block" kar diya.

Toh lesson kya hai? Greedy myopic hota hai — aage ka nahi sochta. Total value bag bharne se aati hai, sirf density se nahi. Iska sahi solution hai Dynamic Programming: har item ke liye "lo ya chhodo" dono try karo aur best yaad rakho — recurrence K(i,c)=max⁡(K(i−1,c), vi+K(i−1,c−wi))K(i,c)=\max(K(i-1,c),\,v_i+K(i-1,c-w_i)), time O(nW)O(nW). Yaad rakhna: "Greedy grabs, gaps remain" — greedy densest cheez utha leta hai, par jo gap chhodta hai, asli behtar answer wahi chhupa hota hai.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,825 wordsD2Visual walkthroughThe derivation in pictures · 2,061 wordsD3Worked examplesEvery scenario covered · 3,961 wordsD4ExercisesGraded, full solutions · 2,577 wordsD5Question bankConcept traps, quick reveals · 2,132 words

Test yourself — Algorithm Paradigms

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Dynamic programming — overlapping subproblems, optimal substructureCoding · 3.7.6Approximation algorithms — approximation ratio, examplesCoding · 4.6.29