0/1 knapsack

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• DP time formula? from Lesson 5.1.1
• Why does greedy fail for 0/1 knapsack? from Lesson 4.2.2
• Fractional knapsack value for W 50, (60,10), (100,20), (120,30)? from Lesson 4.2.2

1 · The Hook

🎣

The 0/1 knapsack (take each item whole or not at all) defeated greedy. DP solves it by asking, for every item and every capacity, "best value using the first i items with capacity w?". The table has n × W entries, each filled in constant time.

2 · Predict First

🤔

Items (weight, value): (2, 3), (3, 4), (4, 5), (5, 6); capacity 5. Best total value?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

(2, 3) + (3, 4) = weight 5, value 7. No other combination that fits does better.

Subproblem and recurrence

K[i][w] = best value using items 1 … i with capacity w.

• K[0][w] = 0; K[i][0] = 0.
• If wᵢ > w: K[i][w] = K[i − 1][w] (item i does not fit).
• Else: K[i][w] = max(K[i − 1][w], vᵢ + K[i − 1][w − wᵢ]) (skip it, or take it).

Answer: K[n][W].

Cost

Θ(nW) time and space (space Θ(W) with a single row, filled right to left). This is pseudo-polynomial: polynomial in the value W, but exponential in the number of bits of W. 0/1 knapsack is NP-hard.

Reconstructing the items

Walk back from K[n][W]: if K[i][w] ≠ K[i − 1][w], item i was taken (w ← w − wᵢ).

Table for the predict example

K[4][5] = 7; walking back: row 2 is where 7 first appears → item 2 taken, w = 2 → item 1 taken.

4 · Visual

K[i][w] = max( K[i-1][w] ,  v_i + K[i-1][w - w_i] )
               skip item i   take item i (if it fits)

           w - w_i        w
row i-1:  [  a  ] ...  [  b  ]
row i  :               [max(b, v_i + a)]

5 · Worked Examples

Example 1 Easy

Items (weight, value): (1, 1), (3, 4), (4, 5), (5, 7); capacity 7. Best value?

Solution

(3, 4) + (4, 5) fills weight 7 for value 9; the next best, (1, 1) + (5, 7), gives 8.

Example 2 Medium

How many table entries does the DP fill for 20 items and capacity 100 (including row 0 and column 0)?

Solution

21 × 101 = 2,121.

Example 3 GATE

Items (weight, value): (5, 10), (4, 40), (6, 30), (3, 50); capacity 10. Maximum value?

Solution

(4, 40) + (3, 50) = weight 7, value 90; adding anything else exceeds 10.

6 · GATE Traps

⚠️

• 0/1 knapsack: K[i − 1] in the "take" term (each item once); using K[i] would allow repeats (unbounded knapsack).
• Θ(nW) is pseudo-polynomial, not polynomial.
• The one-row version must fill right to left to avoid reusing an item.
• Greedy by ratio is wrong here.

7 · Memory Hook

🧠

"Skip it or take it: max of the row above."

8 · Connect the Dots

Knapsack's table was items × capacity. The next classic, longest common subsequence, uses a table of prefix × prefix, the template for all string DPs.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksKnapsack

Items (weight, value): (2, 3), (3, 4), (4, 5), (5, 6); capacity 5. Maximum value?

Numerical answer: ________

Q2NAT2 marksKnapsack table

Same items, capacity 5. What is K[3][4] (first 3 items, capacity 4)?

Numerical answer: ________

Q3NAT2 marksKnapsack

Items (weight, value): (1, 1), (3, 4), (4, 5), (5, 7); capacity 7. Maximum value?

Numerical answer: ________

Q4MCQ1 markComplexity

The DP for 0/1 knapsack with n items and capacity W runs in:

• (A) Θ(nW)
• (B) Θ(2ⁿ)
• (C) Θ(n + W)
• (D) Θ(n log n)

Q5MSQ2 marksFacts

Which are true?

• (A) The DP can use one row of size W + 1 filled left to right.
• (B) The 0/1 knapsack DP is pseudo-polynomial.
• (C) Greedy by value/weight is optimal for 0/1 knapsack.
• (D) Reconstruction walks back comparing K[i][w] with K[i − 1][w].

10 · Rule Card

• K[i][w] = max(K[i−1][w], vᵢ + K[i−1][w − wᵢ]) if wᵢ ≤ w, else K[i−1][w].
• Θ(nW) time; pseudo-polynomial; one row right-to-left.
• Reconstruct: item i taken iff K[i][w] ≠ K[i−1][w].

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

0/1 knapsack DPskip-or-take recurrenceknapsack table K[i][w]pseudo-polynomial timeitem reconstructionunbounded knapsack (contrast)

12 · Answer Vault