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

Bag ek fixed-width box hai jiska capacity $W$ hai. Greedy left se densest items se fill karta hai (tall amber bars = high value-per-width). Jab agla dense item leftover slot se zyada wide hota hai, greedy use skip karta hai aur slot khali rehti hai — woh khali slot (amber-outlined gap) exactly woh value hai jo greedy throw away karta hai.

1. Greedy-choice property — koi na koi globally optimal solution locally best (greedy) choice ko contain karta hai, isliye us choice pe commit karna kabhi optimum tak pahunchne ki raah band nahi karta. (Dekho Greedy-Choice Property.)
2. Optimal substructure — poore problem ka optimal solution subproblems ke optimal solutions se bana hota hai (dekho Optimal Substructure). Dono ko typically ek Exchange Argument se prove kiya jaata hai. 0/1 knapsack mein optimal substructure hai lekin greedy-choice property nahi hai, isliye greedy fail karta hai.

${\rho }_A=\frac{60}{10}=6.0,{\rho }_B=\frac{100}{20}=5.0,{\rho }_C=\frac{120}{30}=4.0$ Descending order: $A\succ B\succ C$. Greedy is order mein list walk karta hai.

$A\succ B\succ C$ walk karo remaining capacity $r$ ke saath, start $r=50$:

• A lo (needs 10 ≤ 50): value $60$, $r=40$.
• B lo (needs 20 ≤ 40): value $60+100=160$, $r=20$.
• C try karo (needs 30 > 20): fit nahi hota, skip. Chosen $\{A,B\}$, total value $160$, wasted capacity $r=20$.

Saare subsets, weight phir value (feasible = weight ≤ 50):

Optimum $=\{B,C\}=220$. Greedy ko $160<220$ mila, isliye greedy yahaan optimal nahi hai. (Yahi Fractional Knapsack–vs–0/1 contrast hai: sirf 0/1 capacity strand kar sakta hai.)

Recurrence: $K(i,c)=\max (K(i-1,c),v_i+K(i-1,c-w_i))$ agar $w_i\le c$, warna $K(i-1,c)$. Base row $K(0,c)=0$.

Yeh do cases sab kuch kyun cover karte hain: item $i$ ke sirf do possible fates hain — ya toh woh chosen set mein hai ya nahi hai. Yeh saare solutions ka complete, non-overlapping split hai.

• Out (skip): agar $i$ choose nahi kiya, toh best jo hum kar sakte hain woh hai baaki items $\mathrm{1..}i-1$ ka best usi capacity $c$ mein — exactly $K(i-1,c)$.
• In (take): agar $i$ choose kiya, toh woh $w_i$ capacity consume karta hai aur $v_i$ contribute karta hai; jo bhi uske saath pack hoga woh items $\mathrm{1..}i-1$ ka optimal pack hona chahiye reduced capacity $c-w_i$ mein — yeh hai $v_i+K(i-1,c-w_i)$, aur yeh sirf tab legal hai jab $w_i\le c$. Kyunki "in" aur "out" saari possibilities cover karte hain, dono ka $\max$ lena guaranteed true best hai — aur yeh fact ki har branch ek optimal chote answer ko reuse karta hai exactly Optimal Substructure hai. Isliye DP kabhi early commit nahi karta: woh ek guess karne ki jagah dono fates evaluate karta hai.

Items order A$(10,60)$, B$(20,100)$, C$(30,120)$.

Sample step, $K(3,50)$: C skip karo → $K(2,50)=160$; C lo → $120+K(2,50-30)=120+K(2,20)=120+100=220$. Max hai $220$. ✓ B+C se match karta hai.

Cell $K(3,50)=220$ (aur uska parent $K(2,20)=100$, matlab "size-20 slot mein B use karo"). DP ne branch "A ko bilkul skip karo" consider kiya — yehi cheez hai jo B (20) aur C (30) dono ke liye room chhod deti hai taaki woh exactly 50 sum karein. Greedy ne pehle A pe commit kiya (highest density) aur kabhi un-commit nahi kar sakta, isliye usne kabhi "skip A" universe explore nahi kiya. Yahi Optimal Substructure ka payoff hai: DP har capacity ke liye best answer rakhta hai, un capacities ke liye bhi jo sirf tab sense banaati hain jab tum ek dense item skip karo.

Capacity $W=100$. Items (listed X, Y, Z — yeh order tie-breaks bhi fix karta hai):

• X: $w=1$, $v=2$, $\rho =2.0$ (densest, lekin tiny).
• Y: $w=100$, $v=100$, $\rho =1.0$.
• Z: $w=100$, $v=100$, $\rho =1.0$.

Greedy: X pehle lo (density 2.0) → $r=100-1=99$. Ab Y aur Z dono ko weight 100 chahiye, lekin sirf 99 units bacha hai, isliye dono fit nahi hote. Greedy value $=2$. Optimum: sirf Y lo (ya sirf Z), weight $100\le 100$, value $=100$. Toh greedy $=2$, optimum $=100$. Ratio $2/100=0.02<0.5$ — density-greedy yahaan 50 guna bura hai. Mechanism exactly parent ki warning hai: X ka single unit of weight remaining capacity ko 100 se 99 kar deta hai, jo heavy 100-value items ko lock out karne ke liye kaafi hai. X ki value ko $ϵ$ ki taraf push karne se wahi blocking effect rehti hai aur ratio → 0 ho jaata hai, yeh dikhata hai ki density-greedy arbitrarily bad ho sakta hai.

Heuristic: $\max (\text{density-greedy value},\text{best single item that fits})$ return karo.

• Density-greedy value $=2$ (4.1 se).
• Best single item jo $W=100$ mein fit ho: Y ya Z, value $100$.
• $\max (2,100)=100$. Optimum hai $100$, toh heuristic $100\ge \frac{1}{2}\cdot 100=50$ return karta hai. ✓ Yeh ½-approximation guarantee meet karta hai (dekho Approximation Algorithms). "Best single item" clause hi woh case rescue karta hai jahan ek heavy item poora answer hai.

$O(nW)$ pseudo-polynomial hai: yeh $W$ ki numeric value mein polynomial hai, $W$ likhne ke liye lagte bits ki sankhya mein nahi. $W$ likhne mein ${\log }_{2}W$ bits lagte hain, toh $W=2^{(\text{input size})}$ — runtime input length mein exponential hai. Agar hum $W$ (aur weights) ko $2^{40}$ jaisa badhne dein, toh table mein $\sim n\cdot 2^{40}$ cells honge aur DP intractable ho jaayega. 0/1 knapsack actually NP-hard hai; koi known algorithm input ki bit-length mein polynomial nahi hai. Isliye $O(nW)$ genuine, useful bound sirf tabhi hai jab $W$ chota ho.

Sliver ki definition. $\delta$ ek arbitrarily small positive weight increment hai, matlab hum limit $\delta \to 0^{+}$ consider karte hain, aur hum hamesha exactly utna hi remove karte hain $\delta$ jitna add karte hain, toh swap weight-preserving hai by construction. Fractional exchange: ek optimal solution diya jo densest available item $d$ ka kuch miss karta hai, $d$ ka weight $\delta$ ka ek sliver lo aur ek equal mass $\delta$ kisi lower-density item ka remove karo. Total weight unchanged hai (humne $\delta$ add kiya aur $\delta$ remove kiya), aur value strictly badhti hai (higher density in, lower density out) — ek contradiction jab tak optimum already $d$ ka jitna ho sakta tha utna use na kar le. 0/1 mein illegal line: "mass $\delta$ ka ek sliver lo." 0/1 mein sirf allowed swap hai poora item, isliye $\delta$ ab 0 ki taraf shrink nahi ho sakta — woh ek full weight $w_d$ pe jump karta hai. Woh whole swap total weight change karta hai aur $\sum w_i\le W$ violate kar sakta hai — exchange guaranteed feasible nahi hai. Consequence: koi feasible weight-preserving exchange nahi hone se yeh proof nahi ho sakta ki greedy choice safe hai, isliye greedy-optimality collapse ho jaati hai aur hum Dynamic Programming pe fall back karte hain.

$W=50$. Items listed P, Q, R, S (listing order ties bhi fix karta hai, page-wide rule ke according):

• P: $w=10$, $v=60$ ($\rho =6.0$)
• Q: $w=20$, $v=100$ ($\rho =5.0$)
• R: $w=30$, $v=120$ ($\rho =4.0$)
• S: $w=50$, $v=200$ ($\rho =4.0$)

Note karo R aur S tie karte hain $\rho =4.0$ pe; tie-breaking rule R ko S se pehle consider karta hai (R pehle listed hai). (a) Density-greedy order $P\succ Q\succ R\succ S$: P lo ($r=40$), Q lo ($r=20$), R ko 30 chahiye skip, S ko 50 chahiye skip → set $\{P,Q\}$, value $160$. (b) Value-greedy (value se sort karo: S$200\succ$ R$120\succ$ Q$100\succ$ P$60$): S lo ($w=50$, $r=0$) → kuch fit nahi hota → set $\{S\}$, value $200$. True optimum: ≤ 50 wale feasible sets enumerate karo. Candidates: $\{S\}=200$, $\{Q,R\}=220$ (wt 50), $\{P,Q\}=160$, $\{P,R\}=180$ (wt 40). Best hai $\{Q,R\}=220$. Toh density-greedy → $160$ (set $\{P,Q\}$), value-greedy → $200$ (set $\{S\}$) — alag-alag galat sets — aur optimum $220$ hai set $\{Q,R\}$, jo kisi bhi heuristic ne choose nahi kiya. Yeh parent ke lesson ka sharpest form hai: koi bhi single sort key optimum nahi dhundh sakta.

Greedy (kisi bhi key se) capacity strand kar sakta hai ya hog kar sakta hai; fix hai DP $K(i,c)=\max (K(i-1,c),v_i+K(i-1,c-w_i))$ ke saath, jo parent instance pe true optimum $220$ deta hai aur un har instances ko correctly handle karta hai jo tumne yahaan banaye.