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

False. On $W=50$ with A(10,60), B(20,100), C(30,120) it takes A+B = 160, but B+C = 220 fills the bag exactly; the integrality constraint lets a dense item waste capacity.

True. With slivers allowed you can top the bag off to exactly $W$ using a fraction of the next item, so no capacity is wasted and the Exchange Argument holds.

False. Filling to $W$ removes the "wasted capacity" symptom but not the disease — a full bag of low-value items can still be beaten by a different full (or even lighter) higher-value subset.

False. Optimality maximizes value, not weight; the best subset can weigh less than greedy's if that lighter combination happens to be worth more.

False. A high-value but heavy item can monopolize capacity — a value-130-weight-50 item exactly fills $W=50$ alone, blocking the (100,30)+(120,30)=220 pair (weights $30+20\le 50$), so the 130-item is excluded from the optimum.

False. Density $v_i/w_i$ and value $v_i$ rank items differently; a low-value light item can out-rank a high-value heavy one on density.

True. The best solution using items $\mathrm{1..}i$ decomposes into the best sub-solution over $\mathrm{1..}i-1$; that is exactly what the DP recurrence $K(i,c)$ exploits.

False. No fixed "take the locally best item" rule is provably part of an optimal solution — that missing Greedy-Choice Property is precisely why greedy fails and Dynamic Programming is needed.

False. $O(nW)$ counts one cell per (item, capacity value), but $W$ needs only ${\log }_{2}W$ bits to write, so the table is exponential in the input size; this is pseudo-polynomial, consistent with the problem's NP-hardness.

False. Adding the $x_i\in \{0,1\}$ constraint jumps the problem from polynomial to NP-hard — a tiny change in the model can change the whole complexity class.

The error is equating average density with total value. Under an integer cap, empty room is uncaptured value; C at density 4 fills the gap and wins despite lower density.

The error is ignoring what the swap requires. The Exchange Argument swaps an arbitrarily small sliver to keep weight fixed; whole-item swaps in 0/1 change total weight and may break capacity, so the proof is illegal.

The error is assuming a smarter skip-rule restores a proof. There is no simple sort/skip key that is optimal for all inputs; the fix is DP or a guaranteed approximation, not a patched heuristic.

The error violates the 0/1 rule: an item is whole or absent. "Mostly fits" is fractional-knapsack thinking; C simply cannot be placed in 20 units.

The error is assuming bounded error. Pure density-greedy can be arbitrarily bad; only $\max (\text{density-greedy},\text{best single item that fits})$ gives a proven ½-guarantee.

The error mis-states the recurrence. $K$ takes the max of skip ($K(i-1,c)$) and take ($v_i+K(i-1,c-w_i)$) — it tries both and never commits early; that is exactly why it beats greedy.

The bag charges you in room, and a ratio measures value earned per scarce unit of room spent — the true "exchange rate"; subtraction mixes worth and room as if they were the same currency, and raw value ignores room entirely.

In fractional you slice the next item to fill the bag exactly, so leftover is always zero; in 0/1 you cannot slice, so a gap smaller than every remaining item stays empty and represents lost value.

The failure is greedy stealing capacity: A(10) consumes room that B(20)+C(30)=50 needed to co-exist, so greedy's early pick forecloses the globally optimal B+C pairing.

Because the optimal use of leftover capacity depends on the exact amount left; storing $K(i,c)$ for every $c$ ensures no future combination is prematurely ruled out.

Value ignores the cost side (weight); a heavy high-value item can occupy capacity that two lighter items would have filled for more total value.

Greedy relies on a proof (exchange) that needs slivers; DP relies only on optimal substructure, which survives the whole-or-nothing constraint untouched.

It is polynomial in the numeric value $W$, but the input only spends ${\log }_{2}W$ bits to store $W$, so the work grows exponentially in that bit-length — the hallmark of a pseudo-polynomial algorithm.

Both return value 0 — nothing fits, so $K(n,W)=0$ and greedy skips all items; this degenerate case is where the two trivially agree.

Its density $v_i/w_i$ divides by zero — it "should" be taken always since it costs no room, but the ratio blows up and breaks the sort; either add the input constraint $w_i\ge 1$, or special-case zero-weight items by taking every one of them for free before running the heuristic.

Not guaranteed — equal density means the answer reduces to fitting maximum weight, and greedy's fit order can still leave a gap that a different equal-density subset would fill more fully.

Yes — density alone doesn't fix an order among equals, and taking a heavier equal-density item first can consume room two lighter equals needed, so different tie-break rules (e.g. lighter-first vs. heavier-first) can produce different greedy totals on the same input.

The answer is 0; the base/guard $w_i>c$ triggers for every positive-weight item at $c=0$, so $K(i,0)=0$ for all $i$ — no special case needed (zero-weight items are the lone exception, still worth taking).

Yes — with one item the only decision is take-if-it-fits, so both give $v_1$ (when $w_1\le W$) or 0; a single item cannot create the capacity-blocking conflict that trips greedy.

Not from this pair alone (it prefers the higher value at equal weight), but the pair can still combine with a third item so that greedy's earlier pick blocks a better overall subset.

Yes — greedy is not always wrong, only not provably right; on many instances it coincides with the optimum, which is exactly why testing one lucky case never validates it.