Knapsack Problem

Tags

Knapsack Problem

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given a list of items, each with a weight and a value, and a knapsack with a fixed capacity, determine the maximum total value you can fit into the knapsack. Each item can either be included or excluded (0/1 constraint) — you cannot take a fractional part of any item.

Intuition

At each item, we face a binary choice: take it or leave it. A greedy approach fails because selecting the locally best item (by value, weight, or ratio) does not guarantee a globally optimal combination. Dynamic programming works because the problem has optimal substructure (the best solution for capacity c with i items builds on the best solution for smaller sub-problems) and overlapping sub-problems (the same (item index, remaining capacity) state is encountered many times in a naive recursion).

Approach

  1. Create a 2D table dp of size (n+1) x (capacity+1), initialized to 0.
  2. For each item i from 1 to n:
    • For each capacity c from 0 to capacity:
      • If weights[i-1] <= c, set dp[i][c] = max(dp[i-1][c], dp[i-1][c - weights[i-1]] + values[i-1]).
      • Otherwise, set dp[i][c] = dp[i-1][c].
  3. dp[n][capacity] holds the maximum value.
  4. To recover the chosen items, backtrack from dp[n][capacity]: if dp[i][c] != dp[i-1][c], item i was included — add it, subtract its weight from c, and move to row i-1.

Pseudocode

function knapsack(items, capacity):
    n = length(items)
    dp = 2D array of size (n+1) x (capacity+1), filled with 0

    for i from 1 to n:
        weight = items[i-1].weight
        value  = items[i-1].value
        for c from 0 to capacity:
            if weight <= c:
                dp[i][c] = max(dp[i-1][c], dp[i-1][c - weight] + value)
            else:
                dp[i][c] = dp[i-1][c]

    // Backtrack to find chosen items
    result = []
    c = capacity
    for i from n down to 1:
        if dp[i][c] != dp[i-1][c]:
            result.append(items[i-1])
            c -= items[i-1].weight

    return dp[n][capacity], result

Time & Space Complexity

MeasureComplexityJustification
TimeO(n * C)Two nested loops: n items and C capacity values
SpaceO(n * C)Size of the DP table (reducible to O(C) if item recovery is not needed)

Key Insights

  • This is a pseudo-polynomial algorithm — polynomial in n and C, but C is not polynomial in the size of the input (number of bits to represent C).
  • Space can be optimized to a single 1D array of size C+1 by iterating capacity right to left in the inner loop, but this sacrifices the ability to reconstruct which items were chosen.
  • The 0/1 knapsack is NP-Hard in general; the DP solution is efficient only when C is reasonably small.
  • A common variant is the unbounded knapsack where each item can be used multiple times; the recurrence changes to reference the same row (dp[i]) instead of the previous row (dp[i-1]).

Edge Cases

  • Capacity is 0: no items can be taken; answer is 0.
  • All items weigh more than capacity: answer is 0, empty set.
  • Single item: include it if its weight fits, otherwise 0.
  • Multiple items with the same weight and value: each is still treated independently.
  • Very large capacity with small item weights: table can become very large — consider space optimization.

Linked mentions