0/1 Knapsack

01-20-2026

Description

This version of Knapsack problems deals in absolutes. As given by the name 0 or 1, each item can either be completely included in the bag or not. Thinking back to the broader description of knapsack problems, this makes a lot of sense. In fact, this is the most frequent type of knapsack problem you will find.

Algorithmically, this binary choice means we can't revisit an item once we've moved past it in our DP state; each item gets exactly one chance to be selected. This constraint shapes our recurrence relation and requires careful attention to loop direction when space-optimizing.

How To Identify

The hallmark signal of dynamic programming are the keywords maximize or minimize. Typically, to achieve an absolute it requires perfect decisions across the board, a perfect use-case for dynamic programming. For knapsack specifically, we typically see a clear constraint. For example, this means that we have a capacity, a weight limit, a cost associated with performing an action. Then, for 0/1 Knapsack, the final hint is that there are a collection of items that must either be included or not included. In other words, each item can be taken at most once. So, a thought process would be

  1. DP?
  2. Is there a clear constraint
  3. Items?
  4. Binary inclusion of items?

General Template and Approach

Once you've realized that the problem requires an 0/1 Knapsack solution, here are the steps to find the solution. First, identify what you are iterating over9 times out of 10 this will be the items in the problem. Then, identify the constraint(s). In the case of multiple constraints, each constraint will become its own dimension in the dp array. Finally, identify what your objective is.

This is already the majority of the solution. The next step is to identify your dp state, where dp[i][c1][c2][...] is best result using the first i items with remaining capacities c1, c2, ....

The transition is also simple. You have 2 realistic options:

  1. Skip
  2. Consume
python
initialize dp[...] = 0

for each item:
    for capacities in reverse:
        if item fits:
            dp[...] = max(
                dp[...],
                value(item) + dp[... - cost(item)]
            )

return dp[full capacities]

Solved Problems