When greedy fails — 0 - 1 knapsack counter-example

3.7.5 · Coding › Algorithm Paradigms

WHAT is the 0/1 knapsack problem?

WHAT does greedy do here?

Knapsack ke liye natural greedy heuristic:

Har item ki value-density (value per unit weight) $ρ_{i} = v_{i} / w_{i}$ compute karo.
Items ko $ρ_{i}$ ke hisaab se descending sort karo.
List par chalo; ek item lo agar woh remaining capacity mein fit ho.

WHY yeh 0/1 ke liye fail karta hai — counter-example

0/1 mein, aap last item ko slice nahi kar sakte. Toh greedy wasted capacity chhod sakti hai, aur wahi gap mein ek better combination chhupa hota hai.

Worked example Classic counter-example

Capacity $W = 50$ .

Item	weight $w_{i}$	value $v_{i}$	density $ρ_{i} = v_{i} / w_{i}$
A	10	60	6.0
B	20	100	5.0
C	30	120	4.0

Greedy (by density): sort → A(6), B(5), C(4).

A lo → load 10, value 60, room bacha 40. Kyun? Sabse zyada density.
B lo → load 30, value 160, room bacha 20. Kyun? Next highest, abhi bhi fit hai.
C try karo (30 chahiye) → 20 mein fit nahi hota. Skip.
Greedy total = 160. Wasted capacity = 20.

Optimal: B + C lo → weight $20 + 30 = 50$ , value $100 + 120 = 220$ . Yeh greedy se better kyun? Yeh poora bag use karta hai (koi waste nahi) aur lower-density item C ko accept karta hai kyunki woh gap ko perfectly fill karta hai.

Greedy ne 160 diya, optimum 220 hai — greedy 27% worse hai, bilkul close bhi nahi.

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

WHERE greedy ki correctness proof collapse karti hai

HOW 0/1 knapsack actually solve karein (fix)

Dynamic Programming use karo — har item consider karo aur har capacity ke liye best value yaad rakho.

Example par DP chalane se $K (3, 50) = 220$ ✓ milta hai — B+C se match karta hai.

Flashcards

Kisi problem mein greedy ke provably optimal hone ke liye kya property honi chahiye?

Ek greedy-choice property (ek locally optimal choice kisi globally optimal solution ka hissa hoti hai) plus optimal substructure, ek exchange argument se provable.

Greedy fractional knapsack solve karta hai lekin 0/1 nahi — kyun?

Fractional slivers allow karta hai, toh aap bag exactly fill kar sakte ho aur exchange argument hold karta hai; 0/1 ki integrality ka matlab hai ki ek whole item capacity waste kar sakta hai aur ek better combo block kar sakta hai.

0/1 knapsack greedy counter-example state karo.

W = 50

; A(10,60), B(20,100), C(30,120). Greedy by density A+B = 160 leta hai; optimum B+C = 220 hai.

Value-density greedy heuristic kya hai?

Items ko

v_{i} / w_{i}

descending se sort karo, har ek lo agar remaining capacity mein fit ho.

0/1 knapsack DP recurrence likho.

K (i, c) = max (K (i - 1, c), v_{i} + K (i - 1, c - w_{i}))

agar

w_{i} \leq c

, warna

K (i - 1, c)

; base

K (0, c) = 0

DP solution ka runtime?

O (nW)

(pseudo-polynomial —

W

ki numeric value par depend karta hai).

0/1 knapsack ke liye sasti approximation guarantee kya milti hai?

½-approximation:

max

(density-greedy value, best single item that fits) lo.

Sirf value se sort karna kyun fail karta hai?

Ek high-value heavy item saari capacity monopolize kar sakta hai aur lighter items ka ek higher-total-value subset block kar sakta hai.

Greedy-optimality proof ke liye exchange argument kyun zaruri hai?

Kyunki yeh dikhata hai ki locally optimal choice ko globally optimal solution mein shamil kiya ja sakta hai bina value lose kiye — agar yeh argument fail ho toh greedy ki correctness guarantee nahi hoti.

Recall Feynman: 12-saal ke bacche ko samjhao

Socho ek chhota backpack aur teen khilone hain. "Sabse zyada bang-for-its-size wala khilona pehle lo" trick tab kaam karti hai jab aap khilone ke tukde kar sako — aap har khaali kona fill kar lete. Lekin asli khilone kate nahi ja sakte! Toh kabhi kabhi "best per size" wala khilona pehle lene se ek awkward khaali jagah reh jaati hai, aur aap do aur khilonaon se chook jaate ho jo saath mein perfectly fit ho jaate aur zyada kaam ke hote. Sach mein best haul dhundne ke liye, har khilone ke liye dono choices try karni padti hain — "lo" ya "chhoddo" — aur har possible bacha hua space ke liye best result yaad rakhna padta hai. Woh careful try-both method dynamic programming hai.

Connections

Greedy Algorithms — jab local choices kaam karti hain (Huffman, MST, activity selection)
Fractional Knapsack — woh version jahan greedy optimal hai (exchange argument)
Dynamic Programming — 0/1 knapsack ke liye sahi paradigm
Optimal Substructure aur Greedy-Choice Property — woh do properties jo greedy ko chahiye
NP-hardness — 0/1 knapsack NP-hard hai; DP pseudo-polynomial hai, polynomial nahi
Approximation Algorithms — knapsack ke liye ½-approx aur FPTAS
Exchange Argument — woh proof technique jo fractional ke liye pass hoti hai, 0/1 ke liye fail