Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm): Worked examples

3.7.4 · D3 · Coding › Algorithm Paradigms › Greedy problems — activity selection, fractional knapsack, H

Is page mein teen greedy algorithms ko parent topic se lekar har tarah ke inputs ke against test kiya gaya hai: simple inputs, ties, zero/degenerate inputs, aur wo traps jahan greedy toot jaati hai. Pehle matrix padho, phir har worked example batata hai ki wo kaun sa cell cover karta hai.

The scenario matrix

#	Topic	Case class	Kya galat ho sakta tha	Example
C1	Activity Selection	Finish time mein ties	do equal-finishers mein se kaunsa lein?	Ex 1
C2	Activity Selection	Touching intervals (start == last finish)	kya " $\geq$ " sahi hai ya " $>$ "?	Ex 2
C3	Activity Selection	Degenerate: 0 ya 1 activity	kya loop phir bhi kaam karta hai?	Ex 3
C4	Fractional Knapsack	Sab kuch fit ho jaata hai (koi fraction ki zaroorat nahi)	greedy "over-cut" na kare	Ex 4
C5	Fractional Knapsack	Density tie + real-world words	tie-breaking irrelevant hai, prove karo	Ex 5
C6	Fractional Knapsack	0/1 twist — indivisible items	greedy density fail karti hai; DP jeetta hai	Ex 6
C7	Fractional Knapsack	Zero capacity / zero-weight item	division by zero, empty bag	Ex 7
C8	Huffman	Sab frequencies equal hain	tree balanced ban jaata hai	Ex 8
C9	Huffman	Merge ties / heap order	exam twist: cost recompute karo	Ex 9
C10	Huffman	Single symbol (degenerate)	codeword length 1 honi chahiye, 0 nahi	Ex 10

Part A — Activity Selection

Worked example Ex 1 — Cell C1: do activities ek hi time par finish karti hain

Activities (start, finish): P(1,4) Q(2,4) R(4,7) S(5,8).

Forecast: P aur Q dono finish at 4 par finish karte hain. Kya farak padta hai hum kaun sa rakhte hain? Final set size guess karo.

Finish ke hisaab se sort karo. Order: P(1,4), Q(2,4), R(4,7), S(5,8) — P aur Q 4 par tie karte hain. Yeh step kyun? Earliest-finish safe greedy key hai; ties arbitrarily break kiye ja sakte hain kyunki dono last = 4 chhod jaate hain.
Pehla uthao (maan lo P). last = 4. Yeh step kyun? P ya Q mein se jo bhi uthao, future window "start $\geq 4$ " identical hoti hai — tie harmless hai.
Scan karo: Q start $2 < 4$ ✗. R start $4 \geq 4$ ✓ → pick karo, last = 7. Yeh step kyun? R pehli compatible activity hai hamare pick ke baad.
S start $5 < 7$ ✗. Done. Result {P, R}, size 2.

Verify karo: Agar P ki jagah Q lete, tab bhi {Q, R} milta, size 2 — same count. Ties kabhi optimum size nahi badlate. ✓

Worked example Ex 2 — Cell C2: intervals jo bas touch karte hain

Activities: U(1,3) V(3,5) W(5,6). Har activity exactly tab start hoti hai jab pichli end hoti hai.

Forecast: kya "touching" activities compatible hain? Predict karo: kya hum teeno le sakte hain?

Compatibility test hai start >= last_finish. Yeh step kyun? Jo activity usi instant par start hoti hai jab doosri finish hoti hai, wo overlap nahi karti — us boundary par resource free hota hai. Isliye hum $\geq$ use karte hain, $>$ nahi.
Finish ke hisaab se sort karo (pehle se sorted hai). U uthao, last = 3.
V start $3 \geq 3$ ✓ → pick karo, last = 5. W start $5 \geq 5$ ✓ → pick karo. Yeh step kyun? Har start pichli finish se exactly milta hai, isliye sab $\geq$ test pass karte hain.
Result {U, V, W}, size 3.

Verify karo: Chunin gayi koi bhi do intervals ek interior point share nahi karti; boundaries touch karti hain lekin overlap nahi karti. Agar tumhare problem mein overlap ka matlab "sirf endpoint share karna bhi" hai, to $>$ switch karo aur size 2 milega — apni definition jaano. ✓

Part B — Fractional Knapsack

Worked example Ex 4 — Cell C4: sab kuch fit ho jaata hai, koi cut ki zaroorat nahi

Capacity $W = 100$ . Items: $A (v = 30, w = 20)$ , $B (v = 40, w = 30)$ , $C (v = 10, w = 10)$ .

Forecast: total weight $20 + 30 + 10 = 60 \leq 100$ hai. Kya hum kabhi fraction lete hain?

Densities: $d_{A} = 30/20 = 1.5$ , $d_{B} = 40/30 \approx 1.333$ , $d_{C} = 10/10 = 1.0$ . Yeh step kyun? Density $v_{i} / w_{i}$ ek kilogram slot ki value hai — hamesha greedy key hoti hai.
Descending sort karo: $A, B, C$ . $A$ pura lo (room $100 \to 80$ , value 30), $B$ pura lo (room $80 \to 50$ , value 70), $C$ pura lo (room $50 \to 40$ , value 80). Yeh step kyun? Har item puri tarah fit hoti hai, isliye $x_{i} = 1$ ; fraction tabhi force hota hai jab item overflow kare.
Room $40$ bacha, koi items nahi bache. Total value 80.

Verify karo: $30 + 40 + 10 = 80$ ; total weight used $60 \leq 100$ . Kyunki sab items fit ho gaye, sab kuch le liya — bag poora bhi nahi bhara, aur yahi optimal hai (koi bacha item add karne ko nahi). ✓

Worked example Ex 5 — Cell C5: density tie + word problem

Ek juice bar bag $W = 5$ litres rakh sakta hai. Teen syrups: Mango (₹90, 3 L), Berry (₹60, 2 L), Lime (₹150, 5 L). Rupee value maximize karo; tum fractions pour kar sakte ho.

Forecast: har ek ki price-per-litre compute karo — unme se do tie karti hain. Kya tie answer badalta hai?

Densities (₹/L): Mango $90/3 = 30$ , Berry $60/2 = 30$ , Lime $150/5 = 30$ . Sab ₹30/L par tie karte hain. Yeh step kyun? Density per-litre price hai; equal densities matlab koi farak nahi kaun sa syrup bag bharta hai.
Kyunki har litre ₹30 ka hai chahe source koi bhi ho, bag kisi bhi tarah se bharo: 5 L total → value $5 \times 30 = ₹150$ . Yeh step kyun? Equal density ke saath Exchange Argument swap karne par zero change deta hai — har choice optimal hai.
E.g. sara Mango lo (3 L) + 1 L Berry (₹30) + 1 L Lime (₹30): $90 + 30 + 30 = ₹150$ .

Verify karo: $150 = 5 L \times ₹30/ L$ . Koi bhi mix jo exactly 5 L hit kare ₹150 deta hai. Ties harmless hain — same total. ✓

Worked example Ex 6 — Cell C6: 0/1 twist jahan greedy FAIL karti hai

Parent ke counterexample jaale hi items, lekin items indivisible hain (0/1 knapsack): $W = 50$ , $A (60, 10)$ , $B (100, 20)$ , $C (120, 30)$ .

Forecast: greedy-by-density ne $A, B$ liya phir $\frac{2}{3} C = 80$ fractional value 240 ke liye. Lekin agar tum $C$ ko cut nahi kar sakte, to density-greedy kya deta hai, aur kya wo optimal hai? Padhne se pehle guess karo.

Density order: $d_{A} = 6, d_{B} = 5, d_{C} = 4$ → try $A, B, C$ . Yeh step kyun? Yahi greedy rule hai — hum ise indivisible items par test kar rahe hain.
$A$ lo (w 10, room $50 \to 40$ ), $B$ lo (w 20, room $40 \to 20$ ). Ab $C$ ka weight 30 $>$ 20 hai — cut nahi kar sakte, isliye skip karo. Greedy value $= 60 + 100 =$ 160. Yeh step kyun? Koi fractions allowed nahi → overflowing item poori tarah drop ho jaata hai, 20 ka wasted gap chhodkar.
Optimal (Dynamic Programming se): try $B + C = 100 + 120 =$ 220 (weight $20 + 30 = 50$ , exactly fit hota hai). Yeh step kyun? DP densest item $A$ ko skip karne ka consider karta hai taaki do heavier-but-larger-total items fit ho sakein — greedy kabhi reconsider nahi karta, isliye yeh miss ho jaata hai.

Verify karo: greedy 160 $<$ optimal 220. Density-greedy 0/1 ke liye galat hai; fractional answer (240) ek unreachable upper bound hai. Lesson: fractions hi hain jo greedy ko safe banate hain. ✓

Worked example Ex 7 — Cell C7: zero capacity aur ek zero-weight item

Case (a): $W = 0$ koi bhi items ke saath. Case (b): $W = 10$ aur ek item $Z (v = 50, w = 0)$ (ek "free" item, zero weight) plus $A (v = 20, w = 10)$ .

Forecast: $d_{Z} = v_{Z} / w_{Z}$ kya hai? Algorithm kya karta hai?

$W = 0$ : kisi cheez ke liye jagah nahi, har $x_{i} = 0$ , total value 0. Yeh step kyun? Empty bag kuch nahi rakh sakta — loop kuch nahi leta.
Zero-weight item $Z$ : $d_{Z} = 50/0$ undefined (infinite density) hai — bina kisi weight cost ke pure value. Yeh step kyun? $w_{i} = 0$ ko special-case karna zaroori hai: aisa item hamesha sorting se pehle poora free mein liya jaata hai, kyunki yeh kabhi capacity consume nahi karta.
$Z$ lo (value 50, room unchanged 10), phir $A$ poora lo (value 20, room $10 \to 0$ ). Total 70.

Verify karo: $50 + 20 = 70$ ; weight used $= 0 + 10 = 10 \leq 10$ . Division-by-zero se bachna aur free items pehle lena robust code ke liye mandatory hai. ✓

Part C — Huffman Coding

Agle examples mein ek code-tree picture hai; merge order hi poori kahani hai.

Figure — Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm)

Worked example Ex 8 — Cell C8: sab frequencies equal hain → balanced tree

Char symbols har ek frequency 1 ke saath: a:1, b:1, c:1, d:1.

Forecast: equal frequencies ke saath, tree ka shape kaisa hoga? Codeword lengths guess karo.

Min-heap: [1,1,1,1]. Do sabse chhote pop karo (a,b) → 2 mein merge karo. Heap: [1,1,2]. Yeh step kyun? Huffman hamesha do minimums merge karta hai; yahan sab equal hain isliye pair choice arbitrary hai.
(c,d) pop karo → 2 mein merge karo. Heap: [2,2].
(2,2) pop karo → 4 = root mein merge karo. Heap: [4]. Yeh step kyun? Last node root hai; char leaves ke liye teen merges ( $n - 1 = 3$ ).
Tree balanced hai: har leaf depth 2 par → har codeword length 2.

Verify karo (cost identity): total bits $=$ internal-node frequencies ka sum $= 2 + 2 + 4 =$ 8. Direct check: $4 symbols \times 1 \times 2 bits = 8$ ✓. Equal frequencies ⇒ Huffman fixed-length code mein degenerate ho jaata hai, bilkul expected ki tarah.

Worked example Ex 9 — Cell C9: merge ties, exam-style cost twist

Symbols: a:2, b:2, c:3, d:7.

Forecast: ek tie hai (do 2's, aur ek 4 possibly 3-family se tie kar sakta hai). Total encoded length compute karo.

Heap [2,2,3,7]. a(2), b(2) pop karo → 4 merge karo. Heap: [3,4,7]. Yeh step kyun? Do sabse chhote 2's ka pair hai; do equal 2's ke beech tie-break cost affect nahi karta.
3(c), 4(ab) pop karo → 7 merge karo. Heap: [7,7]. Yeh step kyun? Ab 3 aur 4 do sabse chhote hain; note karo 7 (=merge) d:7 se tie karta hai lekin wo agle round mein hai.
7, 7 pop karo → 14 = root merge karo. Heap: [14].
Lengths: d root se ek edge par hai → length 1. c do edges par hai → length 2. a, b teen edges par hain → length 3.

Verify karo (do tarike):

Cost identity: internal nodes $4 + 7 + 14 =$ 25 bits.
Direct: $2 (3) + 2 (3) + 3 (2) + 7 (1) = 6 + 6 + 6 + 7 =$ 25 ✓. Dono agree karte hain — heap mein tie ne minimum cost nahi badla.

Worked example Ex 10 — Cell C10: single symbol (degenerate)

Ek symbol: a:12. Saare a's ka message encode karo.

Forecast: Huffman ka loop $n - 1 = 0$ baar run karta hai. a ko kaun sa codeword milega — length 0?

Sirf ek symbol → koi merges nahi hote (min-heap mein sirf ek node hai). Yeh step kyun? $n = 1$ ke saath, "pop two" step kabhi run nahi kar sakta; loop body 0 baar execute hota hai.
Length 0 ka codeword illegal hai — tum ek a ko do se alag nahi bata sakte. Yeh step kyun? Prefix codes ko kam se kam ek bit per symbol chahiye jab kuch bhi bheja jaana ho.
Special-case fix: a ko single-bit codeword 0 assign karo (length 1). Yeh step kyun? Standard implementations akele symbol ke liye length $\geq 1$ force karti hain.

Verify karo: cost $= 12 \times 1 =$ 12 bits (har occurrence par ek bit). Theoretical entropy ek certain source ki 0 hoti hai, lekin real encoders ko phir bhi $\geq 1$ bit/symbol emit karna padta hai — wo degenerate case jo pure information theory chhupa leta hai. ✓

Recall Har example ne kaun sa cell fix kiya?

Finish time mein ties — harmless? ::: Haan — dono equal finishers same future window chhod jaate hain (Ex 1). Kya touching intervals start >= last ke under overlap karte hain? ::: Nahi — boundary contact allowed hai (Ex 2). Kya density-greedy 0/1 knapsack solve karta hai? ::: Nahi — Ex 6 mein 160 vs optimal 220 milta hai; DP use karo. Huffman with all-equal frequencies kaisa tree deta hai? ::: Ek balanced fixed-length tree (Ex 8). Single-symbol alphabet ke liye codeword length? ::: 1 (kabhi 0 nahi), special case se (Ex 10).

Upar use kiye gaye related tools: Priority Queue / Binary Heap (Huffman merges), Sorting Algorithms (finish-time / density sort), Exchange Argument (kyun har greedy pick safe hai), Dynamic Programming (0/1 fallback), Minimum Spanning Tree (Kruskal/Prim) (ek aur exchange-argument greedy).