When greedy fails — 0 - 1 knapsack counter-example: Visual walkthrough

3.7.5 · D2 · Coding › Algorithm Paradigms › When greedy fails — 0 - 1 knapsack counter-example

Step 1 — Bag, ek ruler ki tarah drawn

KYA HAI. Ek knapsack bas ek container hai jisme ek hi limit hoti hai: woh kitna total weight hold kar sakta hai. Us limit ko capacity kehte hain, likha jaata hai $W$ . Hamaari story mein $W = 50$ . Bas itna hi — koi shape nahi, koi volume nahi, sirf ek single number-line of room.

Ise ruler ki tarah kyun draw karein. Kyunki "kya yeh fit hoga?" hamesha numbers ka comparison hota hai: abhi tak maine kitna weight pack kiya hai versus $W$ . $0$ se $50$ tak ka ek horizontal bar har packing decision ko "main bar mein kitna aage hoon?" mein badal deta hai.

PICTURE. Neeche ka bar $0$ (empty) se $W = 50$ (full) tak jaata hai. Har item jo hum pack karenge woh ek colored block hoga is bar ke saath. Jab colored part door wali edge tak pahunch jaaye, bag exactly full hai; agar end mein koi bare bar bacha ho toh woh wasted capacity hai — room jo humne liya par use nahi kiya.

Step 2 — Teen items, aur "weight" aur "value" ka matlab

KYA HAI. Humare paas total $n$ items hain, jahan $n$ bas kitni items hain — yahan $n = 3$ , jinhe hum A, B, C label karte hain. Ek single item $i$ do numbers carry karta hai:

uska weight $w_{i}$ — woh kitna bar khaata hai, aur
uski value $v_{i}$ — ise lene par aapko kitne "points" milte hain.

Hamare teen items:

Do numbers kyun, ek kyun nahi. Agar items mein sirf weight hota, toh packing trivial hoti. Tension — poori difficulty — yeh hai ki jo cheez aap chahte hain (value) aur jo cheez aapko limit karti hai (weight) alag numbers hain. Ek block lamba lekin sasta ho sakta hai, ya chhota lekin beeshkiimti.

PICTURE. Har item scale par drawn hai: uski width = weight, uski height/label = value. Dhyan do A chhota hai (10 wide) lekin proud (60), C lamba hai (30 wide) lekin sirf 120. Aapki aankh ko conflict already feel hona chahiye.

Step 3 — Density: woh number jis par greedy trust karta hai

KYA HAI. Greedy ko sort karne ke liye ek single "yeh item kitna achha hai?" score chahiye. Woh value-density use karta hai: $ρ_{i} = \frac{v _{i}}{w _{i}} ρ_{i} = "points per kilo" v_{i} = prize \div w_{i} = bar eaten$

Symbol ko aawaz mein padho: $ρ_{i}$ ("rho-sub- $i$ ") value divided by weight hai — har unit weight par aapko kitne points milte hain.

Divide kyun karein? Kyunki "har unit scarce resource par kaunsa item best hai?" yeh natural greedy question hai. Weight scarce hai (sirf 50 hai). Value ko weight se divide karna aapko exchange rate batata hai: aap jitna limited bar spend karte ho, utne points earn hote hain.

PICTURE. Har item ko ek slope ki tarah draw karo: rise = value, run = weight. Steep line = high density = "greedy ise pasand karta hai." Slopes A ko steepest rank dete hain, phir B, phir C. Greedy is order mein pack karega.

Step 4 — Greedy pack karta hai: A, phir B, phir… stuck

KYA HAI. Greedy rule: $ρ_{i}$ descending order mein sort karo (A, B, C), list mein chalte jao, item lo agar woh fit ho.

A lo ( $w_{A} = 10$ ): bar filled $0 \to 10$ , value $= 60$ , room left $= 50 - 10 = 40$ . Kyun? Highest density.
B lo ( $w_{B} = 20$ ): bar filled $10 \to 30$ , value $= 60 + 100 = 160$ , room left $= 50 - 30 = 20$ . Kyun? Next-highest, still fits ( $20 \leq 40$ ).
C try karo ( $w_{C} = 30$ ): 30 chahiye, lekin sirf 20 bacha hai. $30 > 20$ → fit nahi hota. Skip.

Yeh kyun rukta hai. Greedy kabhi unpack nahi karta. Jab A bag mein baith jaata hai, uske 10 units hamesha ke liye gone. Isse ek 20-unit gap bacha rehta hai jisme C (jise 30 chahiye) kabhi nahi ghus sakta.

PICTURE. Bar ko left-to-right fill hote dekho: blue A, phir orange B, phir right end par ek red bare gap of 20. C upar float karta hai, andar girne ke liye bahut lamba. Greedy ka score $160$ par freeze ho jaata hai.

Step 5 — Optimum: A drop karo, B + C lo

KYA HAI. Ab woh combination try karo jo greedy ne consider karne se inkaar kar diya: A ko table par chhodo, B aur C lo.

$20 + 30 w_{B} + w_{C} = 50 = W 100 + 120 v_{B} + v_{C} = 220$

Yeh kyun jeet jaata hai. Densest item A ko sacrifice karke, hum woh 10 units free karte hain jo C ko block kar rahi thi. Ab B (20) aur C (30) bar ko exactly tile karte hain — $20 + 30 = 50$ , zero waste. Bag perfectly packed hai, aur $220 > 160$ .

PICTURE. Wahi ruler, nayi packing: orange B phir green C, 50 par flush mein milte hain. Koi red gap nahi. Number 220 ek completely full bar ke upar baitha hai. Ise directly Step 4 ke leaky 160 se compare karo.

Step 6 — Fractional version kyun theek hoti

KYA HAI. Fractional knapsack mein aap items slice kar sakte ho ( $x_{i} \in [0, 1]$ ). Greedy ko slivers allow karke redo karo:

Saara A lo (10) aur saara B lo (20) → room left 20.
C ka $\frac{20}{30} = \frac{2}{3}$ lo → weight $20$ , value $\frac{2}{3} \times 120 = 80$ .
Total value $= 60 + 100 + 80 = 240$ .

Greedy yahan suddenly kyun jeet jaata hai. Slivers se kabhi gap nahi hota — aap hamesha bag ko exactly $W$ tak top up karte ho. Bacha hua 20 agle item ke ek fraction se fill ho jaata hai, toh density-order sach mein sabse zyada value squeeze out karta hai. Exchange argument exactly is liye kaam karta hai kyunki aap arbitrarily small pieces swap kar sakte ho.

PICTURE. Bar A fill karta hai, phir B, phir C ka ek striped 2/3-slice exactly 50 tak pahunchta hai. Koi red nahi. Yeh 240 fractional optimum hai — aur yeh 0/1 optimum 220 ko bhi beat karta hai, kyunki slicing ek superpower hai jo 0/1 forbid karta hai.

Step 7 — Fix ek nazar mein: DONO choices try karo (DP)

KYA HAI. Dynamic programming kabhi early commit nahi karta. Har item ke liye woh dono questions poochhta hai — skip karo ya lo. Ise bookkeep karne ke liye, ek remaining-room number introduce karo, lowercase $c$ se likha jaata hai (ek plain integer jo $0, 1, 2, \dots, W$ run karta hai — is counting variable $c$ ko item C se confuse mat karo hamaari table se). Phir $K (i, c)$ ka matlab hai "sirf items $1 \dots i$ use karke best achievable value jab bag mein abhi bhi $c$ units of room bacha hai":

$K (i, c) = max (skip item i K (i - 1, c), take item i, if w_{i} \leq c v_{i} + K (i - 1, c - w_{i}))$

Padho: $i$ = abhi tak kitni items consider karne ki permission hai; $c$ = leftover room ki ek integer amount, $0$ se $W$ tak koi bhi value. $max$ compare karta hai "i ko bahar chhodo" (room $c$ rehta hai) vs "i ko andar daalo aur chhota bag $c - w_{i}$ solve karo."

Ise fool kyun nahi kiya ja sakta. Greedy is liye mara kyunki usne A decide kar liya B+C ke baare mein jaane bina. DP kuch bhi early decide nahi karta — woh har item ke liye skip aur take dono explore karta hai, toh koi bhi future combination kabhi foreclose nahi hota. Woh jo kaam karta hai woh har (item, room) pair ke liye ek comparison hai: $n$ items times $W + 1$ possible room values, yaani runtime $O (nW)$ — yahan $n = 3$ items aur $W = 50$ .

PICTURE. Ek branching tree: har item par path take / skip fork karta hai. Greedy ek single straight line pe chala (A→B→stuck, value 160). DP har branch explore karta hai; winning path skip-A → take-B → take-C 220 par green light up karta hai.

Ek-picture summary

Ek hi canvas par sab kuch: wahi 50-unit ruler ki teen packings.

Greedy (A + B): ek leaky bar, red gap of 20, value 160.
0/1 optimum (B + C): ek full bar, koi gap nahi, value 220.
Fractional (A + B + ⅔C): ek slice ke zariye full bar, value 240.

Story upar se neeche padhti hai: jitni zyada freedom hogi (whole-only → fractions), bar utna zyada full aur score utna zyada — aur ek cheez jo greedy ka density rule handle nahi kar sakta woh hai whole-item rule se force hone wala gap.

Recall Feynman retelling — poora walkthrough plain words mein

Bag ko 50-cm tape ki strip samjho jise aapko colored blocks se dhakna hai; har block apne weight jitna wide hai aur uski worth us par printed number hai. Greedy blocks ko "worth-per-centimetre" ke order mein uthata hai: pehle chhota rich blue block A, phir orange block B. Ab sirf 20 cm tape bare hai, lekin green block C 30 cm wide hai — fit hone ke liye bahut mota. Greedy kandhe uchkata hai aur 160 par ruk jaata hai, ek 20-cm bald patch chhodke. Clever move yeh hai ki shiny A block ko purpose se refuse karo: B (20 cm) aur C (30 cm) rakho aur woh tape ko perfectly cover kar lete hain, scoring 220. Agar aapko blocks cut karne ki permission hoti (fractional world), greedy jeet jaata — aap kisi bhi gap ko plug karne ke liye C ko snip kar dete aur 240 tak pahunch jaate. Lekin whole-block rules gaps chhodte hain, aur gaps lost points hain. Toh greedily grab karne ki bajaye, aap har block ke liye "rakho" aur "skip karo" dono try karte ho aur har possible amount of leftover tape ke liye best plan yaad rakhte ho — woh patient try-both bookkeeping dynamic programming hai, aur woh hamesha 220 dhundh leta hai.

Connections

Parent: When greedy fails
Greedy Algorithms · Fractional Knapsack · Dynamic Programming
Optimal Substructure · Greedy-Choice Property · Exchange Argument
Approximation Algorithms · NP-hardness