When greedy fails — 0 - 1 knapsack counter-example: Question bank

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

Ye items parent note ke ideas pe lean karti hain: Greedy Algorithms, Fractional Knapsack, Dynamic Programming, Greedy-Choice Property, aur Exchange Argument.

Is page pe use hone wale symbols (pehle padho)

Formula DP function

$K (i, c)$ aur uski recurrence — scratch se derived Object: $K (i, c)$ define karo = sirf items ${1, \dots, i}$ use karke capacity $c$ ke andar jo best total value achieve ho sakti hai. Humein jo poora answer chahiye woh hai $K (n, W)$ . Ek hi decision: item $i$ ke liye, ya toh choddo ya lo — beech mein kuch nahi.

Skip item $i$ : ek kam item ke saath wahi puzzle solve karna hai, same room ⇒ value $K (i - 1, c)$ .
Take item $i$ (sirf tab legal hai jab $w_{i} \leq c$ ): tumhe $v_{i}$ milta hai, lekin baaki ke liye room $w_{i}$ se shrink ho jaata hai ⇒ value $v_{i} + K (i - 1, c - w_{i})$ . Jo bhi bada ho woh rakho: $K (i, c) = {K (i - 1, c) max (K (i - 1, c), v_{i} + K (i - 1, c - w_{i})) w_{i} > c w_{i} \leq c$ Base case: $K (0, c) = 0$ (koi item nahi ⇒ koi value nahi, kisi bhi room $c$ ke liye). Sahi kyun hai? Yeh dono branches try karta hai aur kabhi pehle commit nahi karta, isliye koi bhi future combination kabhi foreclosed nahi hoti.

True ya false — justify karo

Greedy by value-density hamesha optimal 0/1 knapsack answer deta hai.

False.

W = 50

pe A(10,60), B(20,100), C(30,120) ke saath yeh A+B = 160 leta hai, lekin B+C = 220 bag ko exactly fill karta hai; integrality constraint ek dense item ko capacity waste karne deta hai.

Greedy by value-density hamesha optimal fractional knapsack answer deta hai.

True. Slivers allow hone par tum bag ko exactly

W

tak top off kar sakte ho next item ka fraction use karke, isliye koi capacity waste nahi hoti aur Exchange Argument hold karta hai.

Agar greedy bag ko exactly capacity

W

tak fill kare, toh uska answer optimal hona chahiye.

False.

W

tak fill karna "wasted capacity" ka symptom remove karta hai lekin disease nahi — low-value items ka full bag phir bhi kisi alag full (ya halke bhi) higher-value subset se beatable ho sakta hai.

Optimal 0/1 solution hamesha greedy se kam se kam utna weight use karti hai.

False. Optimality value maximize karti hai, weight nahi; best subset greedy se kam weigh kar sakta hai agar woh lighter combination zyada worth ho.

Capacity

W = 50

ke saath, sabse zyada single value wala item hamesha kisi optimal knapsack mein hota hai.

False. Ek high-value lekin heavy item capacity monopolize kar sakta hai — ek value-130-weight-50 item exactly

W = 50

akele fill karta hai, (100,30)+(120,30)=220 pair ko block karta hai (weights

30 + 20 \leq 50

), isliye 130-item optimum se exclude ho jaata hai.

Value-density se sort karna aur raw value se sort karna same greedy pick order deta hai.

False. Density

v_{i} / w_{i}

aur value

v_{i}

items ko alag rank karte hain; ek low-value light item density pe ek high-value heavy item se aage aa sakta hai.

0/1 knapsack mein optimal substructure hai.

True. Items

1.. i

use karne wala best solution

1.. i - 1

pe best sub-solution mein decompose hota hai; DP recurrence

K (i, c)

exactly yahi exploit karta hai.

0/1 knapsack mein greedy-choice property hai.

False. Koi fixed "locally best item lo" rule provably optimal solution ka part nahi hai — woh missing Greedy-Choice Property exactly isliye greedy fail hota hai aur Dynamic Programming ki zaroorat hoti hai.

DP runtime

O (nW)

0/1 knapsack ko polynomial-time problem banata hai.

False.

O (nW)

mein (item, capacity value) ke ek cell count hoti hai, lekin

W

ko likhne ke liye sirf

lo g_{2} W

bits chahiye, toh table input size mein exponential hai; yeh pseudo-polynomial hai, problem ki NP-hardness ke consistent.

Kyunki fractional knapsack easy hai, uska integer version bhi easy hona chahiye.

False.

x_{i} \in {0, 1}

constraint add karna problem ko polynomial se NP-hard mein jump karva deta hai — model mein ek choti si change poora complexity class badal sakti hai.

Error dhundho

"Greedy ne 20 units khali chhodi, lekin density maximize hui, isliye value bhi maximize hui."

Error hai average density ko total value ke barabar maanna. Integer cap ke neeche, khali room uncaptured value hai; C density 4 pe gap fill karta hai aur jeet jaata hai despite lower density.

"Exchange argument density-greedy ko optimal prove karta hai, aur ise fractions ki parwah nahi."

Error hai swap kya require karta hai isko ignore karna. Exchange Argument ek arbitrarily small sliver swap karta hai weight fixed rakhne ke liye; 0/1 mein whole-item swaps total weight change karte hain aur capacity break kar sakte hain, isliye proof illegal hai.

"Main greedy fix karunga — agar densest item fit nahi hota, toh bas next densest lo — yeh optimality recover kar leta hai."

Error yeh maanna hai ki ek smarter skip-rule proof restore kar deta hai. Koi simple sort/skip key nahi hai jo saare inputs ke liye optimal ho; fix hai DP ya ek guaranteed approximation, patched heuristic nahi.

"C lo (30 chahiye) baaki 20 room mein — yeh mostly fit hota hai, isliye count karo."

Error 0/1 rule violate karta hai: ek item poora hai ya absent. "Mostly fits" fractional-knapsack thinking hai; C simply 20 units mein place nahi ho sakta.

"Density-greedy kam se kam hamesha optimal ke kareeb hoti hai, isliye yeh ek safe approximation hai."

Error bounded error assume karna hai. Pure density-greedy arbitrarily bad ho sakti hai; sirf

max (density-greedy, best single item that fits)

hi ek proven ½-guarantee deta hai.

"K(i,c) item i lene ke liye commit karta hai jab bhi woh fit hota hai, kyunki yeh value grab karta hai."

Error recurrence ko galat state karta hai.

K

skip (

K (i - 1, c)

) aur take (

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

) ka max leta hai — dono try karta hai aur kabhi pehle commit nahi karta; exactly isliye yeh greedy ko beat karta hai.

Why questions

Value ko weight se divide kyun karein (ratio

v_{i} / w_{i}

) subtract karne ya sirf value padhne ki jagah?

Bag tumhe room mein charge karta hai, aur ratio scarce room ke spent har unit pe earned value measure karta hai — true "exchange rate"; subtraction worth aur room ko aise mix karta hai jaise woh same currency ho, aur raw value room ko bilkul ignore karta hai.

0/1 knapsack mein leftover capacity value cost kar sakti hai, lekin fractional mein kabhi nahi — kyun?

Fractional mein tum next item ko slice karte ho bag exactly fill karne ke liye, isliye leftover hamesha zero hota hai; 0/1 mein tum slice nahi kar sakte, isliye baaki har item se chhotha gap khali rehta hai aur lost value represent karta hai.

Counter-example mein low-density item C ka B ke saath milke liya ja sakna kyun zaroori hai?

Failure greedy ka capacity churaana hai: A(10) woh room consume karta hai jo B(20)+C(30)=50 ko saath rehne ke liye chahiye tha, isliye greedy ka early pick globally optimal B+C pairing ko foreclose kar deta hai.

DP "har capacity ke liye best value remember karta hai" running choice ki jagah — kyun?

Kyunki leftover capacity ka optimal use exact amount pe depend karta hai jo bacha hai;

K (i, c)

har

c

ke liye store karna ensure karta hai ki koi future combination prematurely rule out na ho.

"Value se sort karo" tempting kyun lagta hai phir bhi galat hai jab value exactly wahi cheez hai jo hum maximize kar rahe hain?

Value cost side (weight) ko ignore karta hai; ek heavy high-value item woh capacity occupy kar sakta hai jo do lighter items zyada total value ke liye use karte.

Integrality (

x_{i} \in {0, 1}

) add karna greedy ko kyun tod deta hai lekin Dynamic Programming ko nahi?

Greedy ek proof (exchange) pe rely karta hai jisme slivers chahiye; DP sirf optimal substructure pe rely karta hai, jo whole-or-nothing constraint ke baad bhi untouched survive karta hai.

O (nW)

chote

W

ke liye fast hai phir bhi true polynomial algorithm nahi — kyun?

Yeh numeric value

W

mein polynomial hai, lekin input sirf

lo g_{2} W

bits spend karta hai

W

store karne ke liye, isliye kaam us bit-length mein exponentially badhta hai — pseudo-polynomial algorithm ki pehchaan.

Edge cases

Agar har item capacity

W

se zyada bhaari hai, toh greedy aur optimum kya return karte hain?

Dono value 0 return karte hain — kuch fit nahi hota, isliye

K (n, W) = 0

aur greedy saare items skip karta hai; yeh degenerate case hai jahan dono trivially agree karte hain.

Agar kisi item ka weight

w_{i} = 0

ho lekin value

v_{i} > 0

ho?

Uski density

v_{i} / w_{i}

divide by zero hai — ise "hamesha lena chahiye" kyunki room kuch cost nahi hota, lekin ratio blow up ho jaata hai aur sort break ho jaata hai; ya toh input constraint

w_{i} \geq 1

add karo, ya zero-weight items ko special-case karo — heuristic run karne se pehle unhe sab free mein le lo.

Agar saare items ki equal value-density ho, toh kya greedy optimal ho jaati hai?

Guaranteed nahi — equal density matlab answer reduce ho jaata hai maximum weight fit karne mein, aur greedy ka fit order phir bhi ek gap chhod sakta hai jo ek alag equal-density subset zyada fully fill karta.

Jab kai items same density share karein, toh kya tie-break order greedy ka total change kar sakta hai?

Haan — density akele equals mein order fix nahi karta, aur pehle ek heavy equal-density item lena woh room consume kar sakta hai jo do lighter equals ko chahiye tha, isliye alag tie-break rules (jaise lighter-first vs. heavier-first) same input pe alag greedy totals produce kar sakte hain.

Agar

W = 0

ho, toh answer kya hai aur kya recurrence ise handle karta hai?

Answer 0 hai; base/guard

w_{i} > c

har positive-weight item ke liye

c = 0

pe trigger hota hai, isliye

K (i, 0) = 0

har

i

ke liye — koi special case nahi chahiye (zero-weight items lone exception hain, phir bhi lene layak hain).

Agar exactly ek item ho, toh kya greedy aur optimum identical hain?

Haan — ek item ke saath ek hi decision hai take-if-it-fits, isliye dono

v_{1}

dete hain (jab

w_{1} \leq W

) ya 0; ek single item woh capacity-blocking conflict create nahi kar sakta jo greedy ko trip karta hai.

Agar do items ka weight identical ho lekin value alag ho, toh kya greedy phir bhi err kar sakta hai?

Sirf is pair se nahi (yeh equal weight pe higher value prefer karta hai), lekin pair phir bhi kisi teesre item ke saath combine ho sakta hai taki greedy ka earlier pick ek better overall subset block kare.

Kya greedy kabhi accidentally "bad" instance pe optimal answer return kar sakta hai?

Haan — greedy hamesha galat nahi hota, sirf provably sahi nahi hota; kai instances pe yeh optimum se coincide karta hai, exactly isliye ek lucky case test karna usse validate nahi karta.

Recall Ek-line survival summary

Greedy tab fail hota hai jab ek locally best item capacity chura leta hai jो ek better whole-item combination ko chahiye thi; ilaaj hai Dynamic Programming (take aur skip dono try karo $K (i, c)$ se), aur koi simple sort key kabhi ise replace nahi kar sakti.