The Knapsack Problem

The 0/1 knapsack problem picks a subset of items with maximum value under a weight limit, solved by dynamic programming.

Pack for maximum value

In the 0/1 knapsack problem you have items, each with a weight and a value, and a knapsack with a weight capacity. You must choose a subset of items whose total weight fits the capacity while maximising total value. Each item is either taken whole or left behind, which is what the 0/1 in the name means.

Why greedy fails here

Selecting items by value-to-weight ratio, the greedy heuristic, does not always give the best answer for 0/1 knapsack because a single high-ratio item can crowd out a better-fitting combination. This is precisely a case where the local choices interact, so dynamic programming is required for an exact optimum.

The DP recurrence

Let best[i][w] be the maximum value using the first i items within capacity w. For each item you either skip it, keeping best[i-1][w], or take it if it fits, adding its value to best[i-1][w - weight]. The table is filled row by row and the answer sits in the last cell.

def knapsack(weights, values, cap):
    n = len(weights)
    dp = [0]*(cap+1)
    for i in range(n):
        for w in range(cap, weights[i]-1, -1):
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
    return dp[cap]

Pseudo-polynomial cost

The algorithm runs in O(n*W) time and space, where W is the capacity. This looks polynomial but is actually pseudo-polynomial: it depends on the numeric value of W, not its number of digits, so it grows exponentially in the input size when capacities are huge. The 0/1 knapsack problem is NP-hard, and no known algorithm is truly polynomial. The related fractional knapsack, where items can be split, is solvable greedily in O(n log n).