Worked examples — When greedy fails — 0 - 1 knapsack counter-example

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

Yeh page ek drill room hai. Parent note ne ek baar prove kar diya ki density-greedy fail hoti hai. Yahan hum har tarah ka instance cover karenge taaki koi bhi case aisa na ho jo tumne pehle dekha na ho.

Shuru karne se pehle, vocabulary ka ek reminder — koi bhi symbol use karne se pehle define kiya jayega.

---

Scenario matrix

Neeche har row ek case class hai — ek alag tarika jis mein greedy-vs-optimal ki kahaani ho sakti hai. Worked examples mein baad mein [Cell 3] jaisi tag hogi taaki tum dekh sako ki sab cover hua.

Cell	Case class	Kya stress karta hai	Example
1	Greedy = OPT (lucky)	greedy abhi bhi sahi ho sakti hai	Ex 1
2	Greedy < OPT (classic gap)	wasted capacity ek combo block karta hai	Ex 2
3	Sort-by-value greedy fail	wrong key capacity hog karti hai	Ex 3
4	Degenerate: kuch fit nahi	zero-item answer	Ex 4
5	Degenerate: sab fit ho jaata	capacity $\ge$ total weight	Ex 5
6	Zero-value / zero-weight items	edge inputs $v_i=0$, $w_i=0$	Ex 6
7	Greedy arbitrarily bad	tiny high-density item ruin kar deta hai	Ex 7
8	½-approximation rescue	guaranteed sasta fix	Ex 8
9	Real-world word problem	translate → solve	Ex 9
10	Exam twist: DP table banao	$K(i,c)$ hand se bharo	Ex 10

Har example ka Forecast padho aur scroll karne se pehle guess karo. Woh guess hi point hai.

---

Figure 1. Capacity line $W=50$ tak ek single stacked bar: A (orange, 10) + B (violet, 20) + C (magenta, 20) bag ko exactly $50$ tak fill karta hai bina kisi gap ke, total value $230$.

1. Densities. ${\rho }_A=60/10=6$, ${\rho }_B=100/20=5$, ${\rho }_C=70/20=3.5$. Yeh step kyun? Greedy ka sirf input density ordering hai, toh pehle isse compute karo.
2. Greedy walk. A lo (room $50\to 40$, value $60$). B lo (room $40\to 20$, value $160$). C try karo (needs $20$, room exactly $20$ → fits), value $230$. Yeh step kyun? Greedy har item tab leta hai jab fit ho; yahan kuch skip nahi hota.
3. Greedy total $=60+100+70=230$, room left $=0$. Yeh step kyun? Li gayi values sum karo aur confirm karo ki bag exactly full hai — zero waste warning sign hai ki greedy already optimal ho sakti hai.
4. Kya kuch better hai? Teeno items ka total weight $10+20+20=50=W$ hai, toh sab items ek saath fit ho jaate hain. Sach mein "sab lo" se beat nahi kar sakte. Yeh step kyun? Jab poora set fit ho jaaye, OPT = sum of all values, koi search nahi chahiye.

Verify: Greedy $=230$, OPT $=230$. Equal ✓.

---

Figure 2. Capacity line $W=50$ tak do stacked bars. Left (orange/violet) greedy A+B hai, $30$ pe top out karta hai, hatched empty GAP $20$ ke saath aur total value $160$. Right (violet/magenta) B+C hai, saare $50$ fill karta hai total value $220$ ke saath. Left ka empty slot exactly woh room hai jo item C ko chahiye tha.

1. Densities. ${\rho }_A=6$, ${\rho }_B=5$, ${\rho }_C=4$. Order: A, B, C. Yeh step kyun? Greedy ki marching order establish karo.
2. Greedy walk. A lo (room $\to 40$, val $60$). B lo (room $\to 20$, val $160$). C try karo (needs $30>20$) → skip. Yeh step kyun? C ko slice nahi kar sakte (0/1 rule), toh greedy 20 units waste ke saath ruk jaata hai.
3. Greedy total $=160$. Yeh step kyun? Li gayi items A+B ki values sum karo greedy ka final score record karne ke liye OPT se compare karne se pehle.
4. OPT dhundho. B+C try karo: weight $20+30=50=W$ ✓, value $100+120=220$. Yeh step kyun? Step 2 mein waste hue 20 units hint hain ki ek lower-density item (C) bag better fill kar sakta tha. A ki jagah C lena us gap ko recover karta hai.

Verify: Greedy $=160$, OPT $=220$. Shortfall $=60$ coins, yaani greedy $160/220\approx 72.7\%$ of optimal hai (≈27% worse) ✓.

---

Figure 3. $W=50$ tak do stacked bars. Left (magenta) value-greedy hai: ek giant item H poore $50$ fill karta hai lekin sirf $130$ worth hai. Right (violet/orange) P+Q hai, poore $50$ fill karta hai aur $220$ worth hai. Same fill, bahut zyada value — heavy item value hog tha.

1. Value se sort karo (density nahi). Order: H$(130)$, Q$(120)$, P$(100)$. Yeh step kyun? Hum tempting "maximize value → valuable cheezein pehle lo" heuristic test kar rahe hain.
2. Value-greedy walk. H lo (weight $50$, room $50\to 0$, value $130$). Room $0$ → P skip, Q skip. Yeh step kyun? H heavy aur valuable hai; ise pakadna poora bag monopolize kar leta hai.
3. Value-greedy total $=130$. Yeh step kyun? Sirf H liya gaya, toh akela uska value heuristic ka score hai — true optimum nikalne se pehle record karo.
4. OPT dhundho. P+Q: weight $20+30=50=W$ ✓, value $100+120=220$. Yeh step kyun? Do lighter items milke single heavy hog se zyada value dete hain.

Verify: value-greedy $=130$, OPT $=220$. $130<220$ ✓.

---

Figure 4. Ek tiny capacity line $W=5$ pe teen item-weight bars (10, 20, 30) se kaafi neeche. Koi nahi pohuncha — sab line ke upar hain, toh loaded bar empty hai (value 0).

1. Har item ko $W$ se check karo. $w_A=10>5$, $w_B=20>5$, $w_C=30>5$. Har item bahut heavy hai. Yeh step kyun? "Take if it fits" test sabke liye fail hota hai — greedy walk kuch nahi leta.
2. Greedy total $=0$, room left $=5$. Yeh step kyun? Empty subset hi ek legal solution hai.
3. OPT. Koi bhi subset (sivaaye $\varnothing$ ke) ka weight $\le 5$ nahi, toh OPT $=0$ bhi. Yeh step kyun? Ek degenerate instance jahan greedy aur OPT trivially zero pe agree karte hain.

Verify: Greedy $=0$, OPT $=0$ ✓.

---

1. Total weight. $10+20+30=60\le 100=W$. Yeh step kyun? Agar poora set fit ho, toh capacity constraint inactive hai.
2. Greedy walk. A, B, C lo — har ek hamesha-shrinking-lekin-phir-bhi-ample room mein fit hota hai. Total $=60+100+120=280$. Yeh step kyun? Greedy ko kabhi skip nahi karna padta; sab grab kar leta hai.
3. OPT $=280$ (sab lo — ek item add karna kisi nonnegative-value total ko kabhi nahi ghatata). Yeh step kyun? Slack capacity ke saath, OPT = sum of all values.

Verify: Greedy $=280$, OPT $=280$ ✓.

---

1. Densities — zeros ke saath careful. ${\rho }_A=6$. Z ke liye: $w_Z=0$, toh upar wali infinite-density convention se, Z ko priority label $+\infty$ milta hai ("free value" ⇒ pehle sorts). N ke liye: ${\rho }_N=0/15=0$ (last sorts). Yeh step kyun? $w=0$ ka koi finite ratio nahi, toh pehle define ki gayi convention use karte hain — Z ko "hamesha pehle" tag milta hai; ek genuine ordering phir bhi exist karti hai: Z, A, N.
2. Greedy walk (rule jaisa likha hai). Z lo (label $+\infty$, weight $0$ → room $50$ hi rehta, value $5$). A lo (room $50\to 40$, value $65$). N try karo (weight $15\le 40$ → fits, toh greedy leta hai), value $65+0=65$, room $\to 25$. Yeh step kyun? Hum "take if it fits" literally follow karte hain — N liya jaata hai chahe useless ho, kyunki rule value kabhi inspect nahi karta.
3. Greedy total $=65$ (Z + A + N; N ne $0$ contribute kiya). Yeh step kyun? Li gayi values $5+60+0$ sum karo; useless N total ko unchanged chhod deta hai, jo exactly woh point hai jo demonstrate kiya ja raha hai.
4. OPT. Z free positive value hai ⇒ hamesha in ($+5$). A ek aur sirf positive-value weighted item hai ($+60$). N $0$ contribute karta hai toh include ya exclude karne se score nahi badlega. OPT $=5+60=65$. Yeh step kyun? Yahan greedy = OPT waise bhi hai — zero-value item harmless tha kyunki kaafi room bacha tha. Ek tighter bag mein, blindly N lena woh room waste kar sakta tha joh ek positive item ko chahiye tha, isliye real solvers ek guard add karte hain "don't take $v_i=0$ items"; lekin woh guard base rule ke upar ek optimization hai, base rule khud nahi.

Verify: Greedy $=65$, OPT $=65$ ✓.

---

Figure 5. Capacity line $W=1000$ pe. Greedy bar (orange) height 1 ka ek sliver dikhata hai (item T, value 2) ek vast hatched gap of 999 ke saath. Optimal bar (magenta) ek solid block hai jo poore 1000 fill karta hai (item M, value 1500). Sliver ne giant ko block kar diya.

1. Densities. ${\rho }_T=2/1=2$, ${\rho }_M=1500/1000=1.5$. Order: T, M. Yeh step kyun? T per kilo best lagta hai.
2. Greedy walk. T lo (room $1000\to 999$, value $2$). M try karo (needs $1000>999$) → skip. Yeh step kyun? Tiny item ne room ka 1 unit chura liya, aur itna kaafi hai giant ko block karne ke liye.
3. Greedy total $=2$. Yeh step kyun? Sirf T liya gaya, toh akela uska value greedy ka score hai — compare karne se pehle record karo.
4. OPT. Bas M lo: weight $1000=W$ ✓, value $1500$. Yeh step kyun? Tiny lure ko drop karne se giant fit ho jaata hai.

Verify: Greedy $=2$, OPT $=1500$, ratio $<0.5$ ✓.

---

1. Density-greedy value (Ex 7 se) $=2$. Yeh step kyun? Do candidates mein se ek.
2. Best single item that fits. T ($v=2$) aur M ($v=1500$, aur $1000\le 1000$ toh fit hai) dono candidates hain; best hai M $=1500$. Yeh step kyun? Yeh second candidate exactly Ex-7 disaster se bachata hai — ek lone giant jise greedy ne skip kar diya.
3. Heuristic answer $=\max (2,1500)=1500$. Yeh step kyun? Do candidates mein se better lo.

Verify: HEUR $=1500$, OPT $=1500$, aur $1500\ge 0.5\times 1500$ ✓.

---

Figure 6. $50$ kg pe capped drone payload bar. Naive dispatch laptop+monitor (orange/violet) $30$ kg pe load karta hai ek $20$-kg empty gap ke saath, fees \160$.Optimalmonitor+printer(violet/magenta)loadkartahaipoore$50$kgfillkarke,fees$$220$.

1. Knapsack mein translate karo. $W=50$; items A=laptop$(10,60)$, B=monitor$(20,100)$, C=printer$(30,120)$. Yeh step kyun? Word problems disguise mein knapsack hain: capacity = payload, value = fee, integrality = "parcel split nahi kar sakte".
2. Density-greedy (ek naive dispatcher kya karta hai). A phir B = \160$,printerskip(needs$30$,sirf$20$ bacha). Yeh step kyun? Tempting-but-wrong shortcut dikhata hai.
3. Optimal load. monitor + printer $=20+30=50$ kg $=W$, fees \100 + $120 = $220$. Yeh step kyun? Payload exactly fill karta hai; story ka "split nahi kar sakte" woh 0/1 constraint hai jo DP zaruri banata hai.

Verify: naive $=160$, optimal $=220$ ✓.

---

Figure 7. Bhara hua DP grid. Rows $i=0,1,2,3$ hain (items unlocked, orange labels); columns $c=\mathrm{0..5}$ hain (violet labels). Har cell $K(i,c)$ rakhta hai. Bottom-right cell $K(3,5)=7$ magenta se highlight hai; ek arrow "skip" link dikhata hai cell directly above se.

1. Row 0 (koi item nahi). $K(0,c)=0$ sabhi $c\in \{0,1,2,3,4,5\}$ ke liye. Yeh step kyun? Base case: koi item nahi → koi value nahi. Har DP yahan se grow hoti hai.
2. Row 1 (item $w=2,v=3$). $c<2$ ke liye: $K=0$. $c\ge 2$ ke liye: $\max (0,3+K(0,c-2))=3$. Row1 $=[0,0,3,3,3,3]$. Yeh step kyun? Ek item worth 3 fit hota hai jab room $\ge 2$ ho; zyada room value add nahi karta.
3. Row 2 (item $w=3,v=4$).
   • $c=0,1,2$: $w_2=3>c$ → bahut heavy → Row1 copy → $0,0,3$.
   • $c=3$: $\max (K_1(3)=3,4+K_1(0)=4)=4$.
   • $c=4$: $\max (K_1(4)=3,4+K_1(1)=4)=4$.
   • $c=5$: $\max (K_1(5)=3,4+K_1(2)=4+3=7)=7$. Row2 $=[0,0,3,4,4,7]$. Yeh step kyun? $c=5$ pe hum dono items 1 aur 2 lete hain ($2+3=5$ kg, $3+4=7$).
4. Row 3 (item $w=4,v=5$).
   • $c=0,1,2,3$: $w_3=4>c$ → bahut heavy → Row2 copy → $0,0,3,4$.
   • $c=4$: $\max (K_2(4)=4,5+K_2(0)=5)=5$.
   • $c=5$: $\max (K_2(5)=7,5+K_2(1)=5)=7$. Row3 $=[0,0,3,4,5,7]$. Yeh step kyun? $c=5$ pe, items 1+2 rakhna (value 7) item 3 akele lene (value 5) se beat karta hai.
5. Answer $K(3,5)=7$, items 1+2 se achieve hota hai. Yeh step kyun? Bottom-right cell poore problem ka answer hai — koi early commitment nahi, har cell pe dono take/skip try kiye.

Verify: $K(3,5)=7$, aur sabhi subsets of weight $\le 5$ pe brute force bhi agree karta hai ✓.

---

Recall Quick self-quiz over the matrix

Density-greedy 0/1 knapsack pe guaranteed correct kab hoti hai? ::: Jab sab items fit ho jaayein ($W\ge \sum w_i$, Cell 5) ya trivially koi fit na ho (Cell 4) — yaani jab capacity kabhi choice force na kare. Kya fixed greedy rule ek $v=0$ item jo fit ho use leta hai? ::: Haan — rule hai "take iff it fits" aur value kabhi inspect nahi karta; Ex 6 dikhata hai ki woh N leta hai aur simply kuch gain nahi karta. Ex 7 greedy score vs OPT? ::: $2$ vs $1500$ — greedy ne ~0.13% capture kiya, koi guarantee nahi prove hoti. ½-approximation kaunse do candidates compare karta hai? ::: density-greedy ki value, aur woh single sabse valuable item jo fit ho. $K(i,c)$ ka matlab kya hai? ::: Pehle $i$ items aur capacity $c$ ke sub-bag se maximum value; answer hai $K(n,W)$. Ex 10 mein DP table ka final answer? ::: $K(3,5)=7$ (items 1 aur 2). Zero-weight positive-value item ko kaise handle karte hain? ::: Ise priority $+\infty$ do (hamesha pehle, hamesha lo) — Cell 6.

---

Connections

• Parent: When greedy fails — woh theory jin examples ko ye drill karte hain
• Dynamic Programming — Ex 10 DP by hand hai
• Fractional Knapsack — jahan greedy actually optimal hai (Ex 2 se contrast); Ex 8 mein upper-bound lemma ka source
• Greedy Algorithms · Greedy-Choice Property · Exchange Argument — kyun wahan proof hold karta hai, yahan nahi
• Approximation Algorithms — Ex 8 ka ½-guarantee
• NP-hardness — kyun koi fast exact greedy key exist nahi karti
• Optimal Substructure — woh property jise DP recurrence exploit karta hai