What is the time complexity of 0/1 knapsack?

Worst case O(n × W). Space complexity is O(n × W), or O(W) with the 1-D trick. The 1-D version needs a reversed inner loop, or it becomes unbounded knapsack.

0/1 knapsack

medium

Leaving an item inherits the row above; taking it looks back at reduced capacity and adds the value. The arrows show which, and following them back recovers the bag's contents.

Worst O(n × W)Space O(n × W), or O(W) with the 1-D trick

Loading the 0/1 knapsack engine…

Where to go next

Fractional knapsack

medium

Densest first, and split the last item.

Coin change (DP)

medium

One subproblem per amount, and no first choice can trap it.

Subsets (power set)

medium

One binary decision per element - and a bitmask does the same job.