Knapsack: Complete Guide with 0/1 and Unbounded Examples

The knapsack pattern solves optimization problems where you must choose a subset of items while staying inside a budget. A brute-force approach that checks every subset costs

Definition: given n items, each with a weight w[i] and a value v[i], plus a capacity W, choose items so the total weight stays at or below W and the total value is maximized. Two variants dominate interviews. In the 0/1 knapsack, each item is used at most once. You take it or you leave it. In the unbounded knapsack, each item can be used any number of times. A third family, subset sum, asks whether some subset adds up to exactly a target value, which is the same table with the weights doing double duty as values.

Real-World Analogy

You are packing for a flight with a strict weight limit. Every item has a weight and a value to you. A camera weighs 2 kg and is worth $300. A laptop weighs 5 kg and is worth $2,000. A jacket weighs 4 kg and is worth $400. Shoes weigh 3 kg and are worth $500. The limit is 15 kg.

A casual packer grabs the most expensive things first. That instinct fails in a specific way. Take an item that weighs 10 kg and is worth $60, and another that weighs 20 kg and is worth $100, with a 30 kg limit. The first item looks better per kilogram, but taking it leaves 20 kg of room, which cannot fit the second item, so you walk away with $60. Skipping the first item and taking the second earns $100. Value per kilogram only tells you which item is cheapest to carry, not which combination is best. You have to consider the combination, and that is what the DP table does.

Visual Explanation

The DP table has one row per item and one column per capacity value from 0 to W. Every cell holds the best value you can carry using only the items seen so far, with exactly this much capacity.

    graph TD
    C{"Fill cell (i, w)"} --> D{"Does item i fit in capacity w?"}
    D -->|No| S["dp[i][w] = dp[i-1][w]"]
    D -->|Yes| T["dp[i][w] = max of two options"]
    T --> T1["skip: dp[i-1][w]"]
    T --> T2["take: value[i] + dp[i-1][w - weight[i]]"]
    S --> N["After the last row, dp[n][W] holds the answer"]
    T1 --> N
    T2 --> N
  

Here is the table for three items, (2 kg, $3), (3 kg, $4), and (4 kg, $5), with capacity 5.

Each row adds one new item to the menu. Row 1 copies zeros until capacity 2, then every column from 2 onward carries the $3 value, because the first item fits everywhere from there. Row 2 shows the decision at capacity 5. Taking the second item leaves capacity 2, and the previous row says capacity 2 is worth $3, so 4 + 3 = 7 beats the skip value of 3. Row 3 never beats row 2 at capacity 5, because the third item weighs 4 kg and the leftover capacity is not worth enough. The answer 7 lives in the bottom-right corner.

The take branch deserves attention. It does not look at the current row. It looks at the previous row at w - weight[i], which is the best value using the earlier items with the leftover capacity. That is what keeps every item from being counted twice.

When to Use This Pattern

• The problem asks for a subset of items where each item is either fully in or fully out, and a budget limits the total. The budget can be weight, cost, time, or a count.
• You maximize a value or minimize a cost under that budget, and ordering items by value per unit of budget does not give the right answer. Greedy fails exactly where the leftover budget matters.
• The problem asks whether a subset can reach a target sum, or how many subsets reach it. This is Partition Equal Subset Sum .
• An expression with plus and minus signs hides a subset sum. Target Sum is a counting problem wearing a disguise.
• Items can be reused any number of times, like picking coins. Coin Change is the unbounded form.
• More than one budget constrains the choice, like a cap on zeros and a cap on ones. Ones and Zeroes adds a second dimension to the table.

The pattern does not fit when items can be split into fractions. That variant is greedy , not DP, and the fractional problem gives the greedy approach its most famous success story.

Complexity Analysis

The time comes from the table itself. There are N rows and W+1 columns, and filling each cell takes constant work, so the total is

Common Mistakes

Iterating capacity forward in the 0/1 knapsack. With a single array, a forward loop reads dp[w - weight[i]] after that slot has already been updated with the current item. The item effectively gets used twice, and the answer inflates. The fix is to walk capacity from W down to the item weight. To catch it during practice, run one item with weight 2 and value 5 against capacity 2. A forward loop returns 10. The correct answer is 5.

Forgetting the +1 padding in the table. The table needs N+1 rows and W+1 columns because row 0 and column 0 represent “no items” and “zero capacity”. When the item index i maps to weights[i-1], an off-by-one error silently reads the wrong item or the wrong capacity. Trace a single item with capacity 1 on paper before writing code, and check that the answer lands in dp[n][W], not dp[n-1][W] or dp[n][W-1].

Skipping the feasibility checks in disguised subset sums. Partition Equal Subset Sum must reject odd totals immediately. Target Sum must reject targets with magnitude above the total and totals that make (total + target) odd. These checks keep the table from being built on a false premise. An odd total cannot split evenly, and a fractional target cannot be a subset sum of integers. Test with an odd-total input and an impossible target before trusting the table.

Initializing the count table wrong. In value problems, dp[0] = 0 says an empty knapsack holds zero value. In counting problems, dp[0] = 1 says there is exactly one way to make the value zero, which is to pick nothing. Swapping these flips every answer by exactly one. A quick test: with target or amount 0, the answer should be 1 for counting and 0 for value.

Related Patterns

• Dynamic Programming . Knapsack is a DP pattern where the state carries the remaining budget as an extra dimension. The dynamic programming page covers the general approach that knapsack builds on.
• Greedy Algorithms . The fractional knapsack is solved greedily by value per weight. The 0/1 version is the standard counterexample that shows when greedy stops working.
• Backtracking . The brute-force alternative enumerates every subset recursively. Knapsack DP is what backtracking grows into once you notice the same subproblems repeat.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.