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

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

Pehle se, "finish times" ya "value-per-weight" ya "sibling leaves at maximum depth" ke baare mein koi proof padhne se pehle, tumhe jaanna hoga ki ye har piece kya hai aur kaisa dikhta hai. Hum inhe order mein banate hain, taaki koi bhi symbol use hone se pehle draw kiya ja sake.

0. Yahan "problem" kya hai, aur "optimal" kya hota hai?

Poora khel yeh hai: feasible solutions ke us bade cloud mein se, ek optimal par land karo bina sab check kiye. Greedy isko ek seedhi sweep mein karne ki koshish karta hai.

1. Number line, intervals, aur "overlap"

Activity selection poori tarah ek number line par hoti hai — ek seedhi horizontal axis jahan har point time ka ek moment hota hai.

Figure s01 (neeche): ek labelled time axis par do horizontal bars. Kali bar activity $i$ hai jo $s_{i} = 1$ se $f_{i} = 4$ tak chalti hai; laal bar activity $j$ hai jo $s_{j} = 5$ se $f_{j} = 8$ tak chalti hai. Unke beech ka gap ( $4$ se $5$ tak) visual proof hai ki woh kabhi ek moment share nahi karte — woh compatible hain.

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

Figure dekho. Do bars overlap karte hain agar woh line ke kisi bhi point ko ek saath share karte hain. Do bars compatible (non-overlapping) hain agar ek doosre ke shuru hone se pehle ya theek usi waqt khatam ho jaaye — laal bar kaali ke khatam hone ke baad shuru hoti hai, toh dono schedule ki ja sakti hain.

Parent note ki line "woh next activity chuno jiska start $\geq$ last picked finish ho" kuch nahi hai, bas yahi ek inequality hai, baar baar apply ki gayi.

2. Symbols $\sum$ , $x_{i}$ , aur inequalities (knapsack ki language)

Ab parent ki cryptic line plain English mein padhti hai: $maximise \sum_{i} x_{i} v_{i} subject to \sum_{i} x_{i} w_{i} \leq W, 0 \leq x_{i} \leq 1.$ "Items ke fractions chuno taaki paisa jitna ho sake utna ho, lekin packed weight bag se kabhi zyada na ho."

Ab $w_{i}$ , $v_{i}$ , $x_{i}$ aur $W$ sab ka matlab clear hai, hum ek bhara hua bag padh sakte hain.

Figure s02 (upar): tall rectangle capacity $W = 50$ ka knapsack hai. Isme neeche se teen slabs bhari hain jinki heights actually packed weights hain ( $x_{i} w_{i}$ ):

item $A$ poora liya, $x_{A} = 1$ : weight $w_{A} = 10$ , value $v_{A} = 60$ ;
item $B$ poora liya, $x_{B} = 1$ : weight $w_{B} = 20$ , value $v_{B} = 100$ ;
item $C$ fraction $x_{C} = \frac{2}{3}$ mein liya (laal slab): weight used $x_{C} w_{C} = \frac{2}{3} \cdot 30 = 20$ , value $x_{C} v_{C} = \frac{2}{3} \cdot 120 = 80$ .

Teen packed weights hain $10 + 20 + 20 = 50 = W$ , toh bag bilkul full hai — laal slab "last slot" idea hai, final gap ko agle item ke fraction se bharta hai. Annotation total value note karta hai $\sum_{i} x_{i} v_{i} = 60 + 100 + 80 = 240$ .

3. Trees, nodes, leaves, aur depth (Huffman ki duniya)

Huffman coding ek binary tree ke roop mein draw ki jaati hai. Algorithm samajhne se pehle tree pictures mein fluent hona zaroori hai.

Figure s03 (upar): ek chhota binary tree. Sabse upar wala dot root hai (depth $0$ ). Har edge ko 0 (left) ya 1 (right) label kiya gaya hai. Same parent se latke do kaale leaves ko siblings mark kiya gaya hai. Ek leaf depth $2$ par laal mein draw ki gayi hai; uske tak neeche jaate do edge-labels padhne par uska codeword 01 milta hai. Yahi woh picture hai jo "depth" ko "number of bits" mein badal deti hai.

4. Min-heap / priority queue

Huffman ko baar baar chahiye "abhi do sabse chhoti frequencies do abhi". Yeh kaam fast karne ke liye ek data structure chahiye.

Har round mein re-sort kyun nahi karte? Kyunki har merge ke baad tum ek nayi combined frequency insert karte ho; heap use $lo g n$ time mein absorb karta hai, scratch se re-sort karne ki jagah. Isliye Huffman ka core loop heap par tikta hai, sort par nahi.

5. Sorting aur $O (\cdot)$ symbol

6. Proof tool: exchange argument

Parent note mein har correctness proof same trick hai, toh ise ek baar seekh lo.

Tum usi swap ke teen flavours miloge:

Activities. Pehle ek indexing convention fix karo: sab activities ko finish time se sort karo aur unhe rename karo taaki $f_{1} \leq f_{2} \leq \dots \leq f_{n}$ ho. Is convention ke under, $a_{1}$ woh activity denote karta hai jiska finish time overall sabse pehla hai (sorting ke baad index $1$ ). Swap: kisi bhi optimal schedule mein, uske earliest finisher ko $a_{1}$ se replace karo. Kyunki $a_{1}$ utni hi ya pehle khatam hoti hai, jo kuch purani choice ke baad fit hua woh abhi bhi fit hoga — feasible, same count.

Knapsack. $ε$ (Greek "epsilon") ko ek bahut chhota positive amount of weight hone do — itna chhota ki dono items involved abhi bhi dene aur lene ki room rakhen. $ε$ kilograms kisi low-density item $j$ se nikalao aur high-density item $i$ mein daalo (jahan $d_{i} > d_{j}$ ). Value lost $= ε d_{j}$ ; value gained $= ε d_{i}$ ; net change $= ε (d_{i} - d_{j}) > 0$ . Toh swap strictly value improve karta hai, matlab jo solution densest item pehle nahi liya usse optimal nahi ho sakta.

Huffman. Yahan hume do alag symbols use karne honge taaki kuch overloaded na ho:

Formula Huffman swap cost kahan se aati hai

Yaad karo objective hai $\sum_{i} f_{i} \cdot dep (i)$ minimize karna. Maan lo symbol $a$ do least frequent symbols mein se ek hai, frequency $f_{a}$ aur current depth $dep (a)$ ke saath. Maan lo $x$ ek symbol hai jo ek deepest leaf par baitha hai, frequency $f_{x}$ aur depth $dep (x)$ ke saath. Kyunki $a$ least frequent hai aur $x$ deepest hai, $f_{a} \leq f_{x} and dep (a) \leq dep (x) .$ Tree mein $a$ aur $x$ ki positions swap karo. Sirf cost sum ke unke do terms change hote hain, toh cost mein change hai $Δ = (f_{a} dep (x) + f_{x} dep (a)) - (f_{a} dep (a) + f_{x} dep (x)) = (f_{a} - f_{x}) (dep (x) - dep (a)) .$ Ab do factors padho: $(f_{a} - f_{x}) \leq 0$ kyunki $a$ rarer symbol hai, jabki $(dep (x) - dep (a)) \geq 0$ kyunki $x$ deeper leaf hai. Ek non-positive number times non-negative number $\leq 0$ hota hai, toh $Δ \leq 0$ : rare symbol ko neeche move karne mein koi cost nahi lagti. Isliye koi optimal tree mein do rarest symbols deepest level par hain — bilkul wahi jo unhe pehle merge karna assume karta hai.

(Dhyaan do humne depth $dep (\cdot)$ likha, na ki $d$ : symbol $d_{i}$ §2 mein knapsack density par already use ho chuka tha, aur $ℓ_{i}$ finished code length hai — teen alag ideas, teen alag names.)

Prerequisite map — ise dependency chain ki tarah padho

Neeche har arrow ka matlab hai "right wali cheez samajhne ke liye left wali chahiye". Raw ideas se upar se teeno greedy problems mein neeche padho, jo sab parent topic mein merge hote hain.

Number line + intervals → tumhe compatibility test $f_{i} \leq s_{j}$ deta hai → jo Activity Selection ko power karta hai.
Summation $\sum$ aur density $v / w$ → dono Fractional Knapsack mein feed hote hain.
Sorting + Big-O → activity selection aur knapsack ke sort-first steps ko feed karte hain.
Min-heap → woh hai jo Huffman ke core loop mein actually use hota hai (do sabse chhoti frequencies kheeencho), na ki sort.
Binary tree (depth, leaves, siblings) + prefix-free code → Huffman Coding mein feed hote hain.
Exchange argument → teeno problems mein shared correctness proof hai.
Activity Selection + Fractional Knapsack + Huffman Coding → milkar parent greedy topic hain.

Yahi chain ek diagram ki tarah (har box ek foundation hai, arrows batate hain kya unlock hoga):

Yeh poora map the parent greedy topic ko feed karta hai. Do aur jagah ye pieces reuse hote hain: Minimum Spanning Tree (Kruskal/Prim) (greedy + exchange phir se) aur Dynamic Programming (jab greedy fail ho toh kya karte hain, jaise 0/1 knapsack mein).

Equipment checklist

Page band karo aur har cheez answer karo; agar atak jao toh apna section dobara padho.

f_{i} \leq s_{j}

ka kya matlab hai, aur yeh kin do activities ke baare mein bata sakta hai?

Activity

i

activity

j

ke shuru hone se pehle ya theek usi waqt khatam hoti hai, toh woh compatible hain (non-overlapping) — yeh

f_{i} \leq f_{j}

label karne ke baad.

w_{i}

ke baare mein kya true hona chahiye, aur knapsack item ki density

d_{i}

words mein kya hai?

Value divided by weight,

v_{i} / w_{i}

— money per kilogram;

w_{i} > 0

chahiye taaki division defined ho.

x_{i} = 0

x_{i} = 1

, aur

x_{i} = 0.5

har ek ka kya matlab hai?

Item skip karo, poora lo, aadha lo.

Huffman objective jo hum minimize karte hain, formula mein kya hai?

Total cost

\sum_{i} f_{i} \cdot ℓ_{i} = \sum_{i} f_{i} \cdot dep (i)

bits, sab symbols

i

ke upar.

dep (u)

ka kya matlab hai?

Root se node

u

tak neeche edges ki sankhya (root ka

dep = 0

hai).

Code tree mein leaf ki depth uski codeword length

ℓ_{i}

ke barabar kyun hoti hai?

Root se leaf tak har edge ek bit (0 ya 1) add karta hai, toh depth = bits ki sankhya =

ℓ_{i}

Code ko prefix-free kya banata hai, aur leaves ise kyun guarantee karte hain?

Koi codeword doosre ki shuruwat nahi hoti; symbols sirf leaves par hote hain, toh koi path doosre ka prefix nahi ho sakta.

Jab do leaves ek parent share karte hain toh unhe kya kehte hain?

Siblings.

Ek min-heap tumhe kaunsa ek operation sasta deta hai, aur us par kya cost hai?

Sabse chhota element pop karo (aur naya daalo), dono kaafi

lo g n

time mein.

Huffman apne core loop ke liye sort ki jagah min-heap kyun use karta hai?

Har merge ek nayi combined frequency insert karta hai; heap use

lo g n

time mein re-insert karta hai, scratch se re-sort karne ki jagah.

Activity-selection exchange argument mein

a_{1}

kya denote karta hai?

f_{1} \leq \dots \leq f_{n}

sort karne ke baad,

a_{1}

woh activity hai jiska finish time overall sabse pehla hai.

Huffman swap mein

Δ = (f_{a} - f_{x}) (dep (x) - dep (a)) \leq 0

kyun hai?

f_{a} - f_{x} \leq 0

(rarer symbol) times

dep (x) - dep (a) \geq 0

(deeper leaf) non-positive hota hai.

Knapsack exchange argument mein

ε

kya hai?

Weight ki ek bahut chhoti positive amount, itni chhoti ki dono items abhi bhi de aur le sakein.

O (g (n))

formally kya matlab hai?

T (n) \leq c \cdot g (n)

kisi constant

c

aur sab bade

n

ke liye — growth par upper bound, constants ignore karte hue.

Is topic mein letter

f

ke do alag meanings kya hain?

Activity selection mein finish time

f_{i}

; Huffman coding mein symbol frequency

f_{i}