0/1

Knapsack Without Repetition

Pattern · item × budget 2-D table Core DP2 lecture topic O(nB) 4difficulty
Question — exam style

You are given n objects and a knapsack. Object i has an integer weight w[i] and an integer value v[i]. The knapsack has integer capacity B. You may put each object in the knapsack at most once (you cannot take fractions or duplicates). Design a dynamic-programming algorithm for the following task.

Input:Weights w[1..n], values v[1..n], capacity B (all positive integers).
Output:The maximum total value of a subset of objects whose total weight is at most B.

Model answer

4-part format
aSubproblem in words
K(i, b) = the maximum total value achievable using a subset of the first i objects (objects 1..i), each used at most once, with total weight ≤ b, for 0 ≤ i ≤ n and 0 ≤ b ≤ B.

Two axes: which objects are available (i) and how much capacity remains (b). The capacity bound B becoming a table dimension is exactly why this is pseudo-polynomial.

bRecurrence math only, with base cases + bounds
K(0, b) = 0 for 0 ≤ b ≤ B K(i, 0) = 0 for 0 ≤ i ≤ n If w[i] > b: K(i, b) = K(i-1, b) Else: K(i, b) = max{ K(i-1, b), v[i] + K(i-1, b - w[i]) } for 1 ≤ i ≤ n, 1 ≤ b ≤ B

Either skip object i (K(i−1, b)), or take it and add its value to the best packing of the remaining objects in the reduced capacity: v[i] + K(i−1, b−w[i]). Both branches drop to row i−1.

cImplementation analysis
(1) # of subproblems
O(nB)
(2) Time to fill table
O(nB) — O(1) per entry
(3) Where answer is extracted
K(n, B)
(4) Time to extract
O(1)
The single character that defines 0/1 vs. unlimited

The "take" branch here is v[i] + K(i−1, b−w[i]) — dropping to row i−1 is what forbids reusing object i. In the with-repetition version (see 6.17) the same branch stays on row i: K(i, b−w[i]). This one index is the entire difference between the two Knapsacks. Read the problem for "at most once" vs. "unlimited supply" and pick accordingly.

Say "pseudo-polynomial" if asked about efficiency

O(nB) looks polynomial but isn't: B is a number whose input encoding has only log B bits, so the runtime is exponential in the input size. If the exam asks whether Knapsack has a polynomial-time algorithm, the honest answer is "this DP is pseudo-polynomial, not polynomial."

Optional pseudocode not required by Ed #9

A mechanical translation. The take-branch drops to row i-1 — that's what forbids reuse.

function Knapsack01(w[1..n], v[1..n], B):
    for b = 0 to B: K[0][b] = 0
    for i = 1 to n:
        K[i][0] = 0
        for b = 1 to B:
            if w[i] > b:
                K[i][b] = K[i-1][b]
            else:
                K[i][b] = max(K[i-1][b], v[i] + K[i-1][b-w[i]])
    return K[n][B]
✎

Try it yourself

worked example + self-test

K(i,b)=max{K(i−1,b), v[i]+K(i−1,b−w[i])}. Answer K(n,B).

Worked full grid — greedy fails here

w = [1, 3, 4, 5] v = [1, 4, 5, 7] B = 7

i\b │ 0 1 2 3 4 5 6 7 ────┼──────────────────────── 0 │ 0 0 0 0 0 0 0 0 1 │ 0 1 1 1 1 1 1 1 2 │ 0 1 1 4 5 5 5 5 3 │ 0 1 1 4 5 6 6 9 4 │ 0 1 1 4 5 7 8 9
Answer: K(4,7) = 9. Items chosen: 2 (w3,v4) + 3 (w4,v5) = weight 7, value 9. (Greedy-by-ratio would pick items 1&4 for only 8 — the point.)
Self-test build the grid, then reveal

w = [2, 3, 4, 6] v = [3, 4, 5, 8] B = 6

Reveal answer
Max value = 8  (items 1 & 3: weight 2+4 = 6, value 3+5 = 8).