Intuition The one core ideaThe 0/1 knapsack asks: given a bag that can only carry so much weight, which whole items should you pack to make your loot worth the most? The whole story of "when greedy fails" is really the story of one word — "whole" : because you can't slice items, grabbing the "best-looking" one first can waste space that a smarter combination would have used perfectly.
This page builds every symbol, word, and picture that the parent note the parent topic silently assumes. Read it top to bottom — each idea is a brick for the next.
n i
==n how many items exist in total . If there are 3 items, n = 3
We give each item a number from 1 n 1 2 n i stand-in for "whichever item we're talking about right now" — it ranges over i = 1 , 2 , … , n
So "for every i n
We meet n i before anything else because every symbol below leans on them — you cannot write "the weight of item i i
Definition An item, its weight, and its valueAn item is one object you might put in the bag. Item i i = 1 , … , n
its weight — how much room / load it uses up. We write the weight of item i w i
its value — how much that object is worth to you. We write it as ==v i
Allowed values: we require w i > 0 positive weight — a zero-weight item makes no sense here and would break the density formula later), and v i ≥ 0 w i v i W positive whole numbers (integers) , which is what lets the DP table below have a finite grid of cells.
The little i subscript . It is just a name tag : w 1 v 3 not multiplication, not a power — it is a label, like the number on a jersey.
Figure 1 — a single item drawn as an orange box labelled "item i". A teal arrow points to its left edge tagged "weight w i v i every item bundles exactly two numbers — one weight and one value.
Intuition Why two separate numbers?If items only had value , you'd take everything. If they only had weight , nothing would be worth choosing. The whole problem is interesting because value and weight pull in different directions — a heavy thing might be precious, a light thing might be junk. The tension between w i v i
W maximum total weight called the capacity , written with a capital ==W not allowed to exceed W W W > 0
Notice the case matters: small w i one item ; capital W bag's limit . Same letter, very different jobs — mixing them up is the most common beginner slip.
Intuition Picture the capacity as a shelf edgeImagine stacking items and watching a red line at height W at or below the line, the load is legal. Cross the line and the bag "breaks" — that choice is forbidden.
Definition A set, and what makesS set is just an unordered collection of distinct things — like a bag of labels with no repeats and no particular order. We write a set with curly braces: { 1 , 3 }
The set of all item numbers is { 1 , 2 , … , n }
A subset is any set you can build by keeping some (or none, or all) of those numbers. ==S pack .
"i ∈ S "i in S" ) means "item i i ∈ / S
The empty set ∅ = { } nothing — a perfectly valid choice (pack an empty bag).
Definition The indicator switchx i x i yes/no switch for item i x i = 1 "I took it" (i ∈ S x i = 0 "I left it" (i ∈ / S S x i
The symbol { 0 , 1 } set of two allowed values . Writing x i ∈ { 0 , 1 } "the switch x i . That is the famous "0/1" in the problem's name.
Intuition Why a 0/1 switch and not a dial?A dial that could sit at, say, 0.4 can't be cut : a laptop at 40% is a broken laptop worth nothing. So we forbid the dial and keep only the switch. Later we'll meet the Fractional Knapsack does allow the dial — and that one tiny change is why greedy works there and fails here.
Figure 2 — left panel: a 0/1 "switch" showing two boxes, "0 (leave it)" and a filled "1 (take it)", under the label x i ∈ { 0 , 1 } x i ∈ [ 0 , 1 ] 0/1 knapsack allows only the switch; the fractional version allows the dial.
Definition Sigma, the "add-them-all" symbolThe big Greek letter ==∑ "add up" . The writing underneath tells you what to add .
∑ i ∈ S w i = (add the weight w i of every item i that is in S ) S = { A , C } ∑ i ∈ S w i = w A + w C
Edge case — empty set: if S = ∅ ∑ i ∈ ∅ w i = 0 0
Read it left to right as a sentence: "sum, over every i S w i
ρ i value-density : how much value you get per kilogram .
ρ i = w i v i ρ rho (say "row"); here it just names this ratio. A fraction w i v i "value shared out over the weight" — divide the worth by the room it costs. This is exactly why we insisted w i > 0 : dividing by a zero weight would be undefined.
Intuition Why divide? — picture two blocksItem A: value 60, weight 10 → ρ = 6 ρ = 4 big items and small items on the same scale — you couldn't compare a 10-kg item to a 30-kg item by raw value alone; dividing normalises them to a per-kilo price tag.
Figure 3 — a graph with weight w i v i steeper the line, the higher the density ρ = v / w density is the slope of the line from the origin to the item.
Definition The greedy algorithm (density heuristic)"Greedy " is a strategy that, at every step, grabs whatever looks best right now and never reconsiders . For knapsack the "best right now" score is the density ρ i
Compute ρ i = v i / w i
Sort the items from highest density to lowest.Walk down that sorted list; take an item if it still fits in the space that's left, otherwise skip it.
Because it commits to each item the moment it's reached and never undoes that choice, greedy is fast but short-sighted — and that short-sightedness is the whole reason it can fail on 0/1 knapsack.
Common mistake Density is arate , not a total
A high ρ i per kilo — it does not tell you the total loot is best. That gap between "best rate" and "best total" is exactly where greedy trips. Keep this seed in mind; the parent note grows the whole failure from it.
K ( i , c ) K ( i , c ) "the best total value you can get using only items 1 i c
i how many of the items (numbered 1 n (1, 2, 3, …).c a pretend capacity you're testing (0, 1, 2, …, up to W
K name for this table of answers, like naming a spreadsheet. The two things in the brackets, ( i , c ) row and column that pick out one cell. The final answer we care about is K ( n , W ) all items allowed, full capacity.
Intuition Why remember answers at all?The greedy algorithm commits early and never reconsiders. The fix must be allowed to say "what if I'd left that item?" To do that cheaply it writes down the best result for every ( i , c ) Dynamic Programming , and K ( i , c )
Definition Exchange argument & greedy-choice property (plain words)
An Exchange Argument "if the best answer didn't use my greedy pick, I'll swap my pick in for something worse and show the answer only gets better." It needs the swap to be legal (not break the capacity).
The Greedy-Choice Property "a locally best choice is always part of some overall-best answer."
The parent's punchline is that in 0/1 knapsack the exchange is illegal (you can only swap whole items, which changes weight), so the greedy-choice property fails .
item weight w_i and value v_i
problem statement: max total value under limit
set S subset of 1 to n and switch x_i
greedy heuristic: sort by density, take if fits
counter-example: greedy fails
Read it as: the count n i item numbers and the subset S ; those plus capacity and ∑ problem ; the problem plus density builds the greedy attempt; greedy plus the failed exchange argument produces the counter-example ; and the counter-example motivates the DP fix built on the table K
What does n i n i 1 , 2 , … , n
What does the subscript in w i It is a name tag — "the weight of item number i
What is the allowed range of w i v i W w i > 0 v i ≥ 0
Why must w i Because density ρ i = v i / w i w i
What is the difference between w i W Small w i W
What is a set, and what makes S { 1 , … , n } A set is an unordered collection of distinct things; S
What does x i ∈ { 0 , 1 } The switch for item i
What is ∑ i ∈ S v i S = ∅ Zero — the sum over an empty set is 0 (an empty bag is worth nothing).
What does ∑ i ∈ S v i Add up the value v i i S
What does "s.t." abbreviate and mean? "Subject to" — the constraint you must obey, here that total weight stays ≤ W
What exactly does the greedy algorithm do here? Compute density v i / w i
What is value-density ρ i ρ i = v i / w i
Why is a high ρ i ρ i
What does K ( i , c ) The best total value achievable using only items 1.. i c
Which final cell answers the whole problem? K ( n , W )
Why does the exchange argument fail for 0/1 knapsack? You can only swap whole items, which changes total weight and may break the capacity, so the swap isn't always legal.
When greedy fails — 0 - 1 knapsack counter-example (index 3.7.5) — the parent that uses every symbol built here.Fractional Knapsack — same symbols, but the switch x i x i ∈ [ 0 , 1 ] Dynamic Programming — the paradigm behind the table K ( i , c ) Greedy Algorithms — where the density heuristic does win.Greedy-Choice Property · Exchange Argument · Optimal Substructure — the proof machinery. 
