When greedy fails — 0 - 1 knapsack counter-example: Foundations

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

Yeh page har ek symbol, word, aur picture build karta hai jo parent note the parent topic silently assume karta hai. Ise top to bottom padho — har idea agle ke liye ek brick hai.

0. Pehle: kitne items hain, aur hum unhe kaise count karte hain

Hum $n$ aur $i$ se sabse pehle milte hain kyunki neeche har symbol inhi par lean karta hai — aap "item $i$ ka weight" tab tak nahi likh sakte jab tak yeh na pata ho ki $i$ kahan tak range karta hai.

1. Ek "item" kya hota hai? (weight aur value)

Letter ke neeche chhota $i$ subscript kehlata hai. Yeh bas ek name tag hai: $w_{1}$ matlab "item 1 ka weight", $v_{3}$ matlab "item 3 ki value". Yeh multiplication nahi hai, power nahi — yeh ek label hai, jaise jersey par number.

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

Figure 1 — ek single item ek orange box ke roop mein draw kiya gaya "item i" label ke saath. Ek teal arrow uske left edge ki taraf point karta hai jis par "weight $w_{i}$ (room it uses)" tag hai; ek plum arrow uske top-right ki taraf point karta hai jis par "value $v_{i}$ (what it is worth)" tag hai. Ek takeaway: har item exactly do numbers bundle karta hai — ek weight aur ek value.

2. Bag aur uski limit: capacity $W$

Note karo ki case matter karta hai: chhota $w_{i}$ = ek item ka weight; capital $W$ = bag ki limit. Same letter, bahut alag kaam — inhe mix karna sabse common beginner galti hai.

3. Sets aur subsets: $S$ actually kya hai

Symbol ${0, 1}$ do allowed values ka set hai. $x_{i} \in {0, 1}$ likhne ka literal matlab hai "switch $x_{i}$ sirf 0 ya sirf 1 ho sakta hai." Yahi famous "0/1" hai problem ke naam mein.

Figure 2 — left panel: ek 0/1 "switch" do boxes dikhata hai, "0 (leave it)" aur ek filled "1 (take it)", label $x_{i} \in {0, 1}$ ke neeche. Right panel: ek "dial" bar partly filled 0.6 tak ek plum arrow ke saath "take 0.6 of it", $x_{i} \in [0, 1]$ ke neeche. Ek takeaway: 0/1 knapsack sirf switch allow karta hai; fractional version dial allow karta hai.

4. $\sum$ symbol — chosen pile ko saath mein add karna

Ise left to right ek sentence ki tarah padho: "sum, har $i$ ke liye jo $S$ mein hai, $w_{i}$ ka."

5. Value-density $ρ_{i}$ — value per unit weight

Figure 3 — ek graph jisme x-axis par weight $w_{i}$ hai aur y-axis par value $v_{i}$ hai. Teen lines origin se points A(10,60), B(20,100), C(30,120) tak jaati hain, orange, teal, plum colored. Jitni steep line, utni zyada density $ρ = v / w$ (A sabse steep hai 6 par, C sabse flat hai 4 par). Ek takeaway: density origin se item tak line ka slope hai.

6. "Greedy" ka matlab kya hai — woh algorithm jiske baare mein yeh page hai

7. DP table symbol $K (i, c)$ — "best value so far"

$K$ bas is answers ki table ka naam hai, jaise ek spreadsheet ko naam dena. Brackets mein do cheezein, $(i, c)$ , row aur column hain jo ek cell pick karti hain. Final answer jo hume chahiye woh hai $K (n, W)$ — saare items allowed, poori capacity par.

8. Do aur phrases jo aap miloge

Prerequisite map

Ise aise padho: count $n$ /index $i$ item numbers aur subset $S$ feed karte hain; woh plus capacity aur $\sum$ problem define karte hain; problem plus density greedy attempt build karta hai; greedy plus failed exchange argument counter-example produce karta hai; aur counter-example table $K$ par bana DP fix motivate karta hai.

Equipment checklist

n

kya count karta hai, aur index

i

kahan tak range karta hai?

n

items ki total number hai;

i

1, 2, \dots, n

tak range karta hai, "jis bhi item ki hum baat kar rahe hain" ke liye stand-in hai.

w_{i}

mein subscript ka kya matlab hai?

Yeh ek name tag hai — "item number

i

ka weight" — multiplication ya power nahi.

w_{i}

v_{i}

, aur

W

ki allowed range kya hai?

w_{i} > 0

(strictly positive),

v_{i} \geq 0

, aur teeno standard problem mein positive whole numbers (integers) hain.

w_{i}

strictly positive kyun hona chahiye?

Kyunki density

ρ_{i} = v_{i} / w_{i}

mein

w_{i}

se divide hota hai; zero weight ise undefined bana deta.

w_{i}

aur

W

mein kya fark hai?

Chhota

w_{i}

ek single item ka weight hai; capital

W

bag ki total capacity limit hai.

Ek set kya hai, aur kya

S

{1, \dots, n}

ka subset banata hai?

Ek set distinct cheezein ki unordered collection hai;

S

koi bhi collection hai jo item numbers mein se kuch, koi nahi, ya sab rakh ke bani ho.

x_{i} \in {0, 1}

words mein kya kehta hai?

Item

i

ka switch sirf 0 (leave it) ya 1 (take it) ho sakta hai — koi fractions nahi.

S = \emptyset

hone par

\sum_{i \in S} v_{i}

kya hota hai?

Zero — empty set par sum 0 hota hai (ek khali bag worth kuch nahi).

\sum_{i \in S} v_{i}

generally kya compute karta hai?

Har item

i

ki value

v_{i}

add karo jo tumhare chosen set

S

mein hai — total loot value.

"s.t." kiska abbreviation hai aur kya matlab hai?

"Subject to" — woh constraint jo aapko manni hai, yahan ki total weight

\leq W

rahe.

Greedy algorithm yahan exactly kya karta hai?

Density

v_{i} / w_{i}

compute karo, items ko highest-first sort karo, phir list walk karo har item ko lete hue agar woh abhi bhi fit hoti ho — kabhi reconsider nahi karte.

Value-density

ρ_{i}

kya hai aur divide kyun karte hain?

ρ_{i} = v_{i} / w_{i}

, value per unit weight; divide karna bade aur chhote items ko same per-kilo scale par laata hai.

High

ρ_{i}

aur high total value ek kyun nahi hain?

ρ_{i}

ek per-kilo rate hai; total value poora bag fill karne par depend karta hai, aur ek high-rate item bachi hui room waste kar sakta hai.

K (i, c)

kya store karta hai?

Best total value jo sirf items

1.. i

use karke pretend capacity

c

mein achieve ki ja sakti hai.

Poore problem ka answer kaunsa final cell deta hai?

K (n, W)

— saare items allowed, poori capacity par.

0/1 knapsack mein exchange argument kyun fail karta hai?

Aap sirf whole items swap kar sakte ho, jo total weight change karta hai aur capacity break kar sakta hai, toh swap hamesha legal nahi hota.

Connections

When greedy fails — 0 - 1 knapsack counter-example (index 3.7.5) — woh parent jo yahan build har symbol use karta hai.
Fractional Knapsack — same symbols, lekin switch $x_{i}$ ek dial $x_{i} \in [0, 1]$ ban jaata hai.
Dynamic Programming — woh paradigm table $K (i, c)$ ke peeche hai.
Greedy Algorithms — jahan density heuristic actually jeetta hai.
Greedy-Choice Property · Exchange Argument · Optimal Substructure — proof machinery.