0/1 Knapsack Problem

Table of Contents +

Imagine you are packing a bag for a trip. Each thing you own has a weight and a worth. Your bag can only hold so much. You want the most worth without going over the weight limit. That is the whole puzzle here. And it shows up everywhere in real code.

🎒 What Is the 0/1 Knapsack Problem?

You are given a set of items. Each item has a weight and a value. You also have a bag with a fixed capacity. Capacity is the most total weight it can carry.

The goal is to pick items so the total value is as big as possible. But you cannot go over the capacity.

The “0/1” part matters. For each item you make one choice:

  • Take the whole item (1).
  • Skip the item completely (0).

So you cannot break an item in half. You cannot take “a bit” of it. It is all or nothing. That all-or-nothing rule is what sets this problem apart.

Here is the kind of pain this solves. Say you have a phone with limited storage. Each app gives you some joy but takes some space. You want the happiest phone that still fits. Picking by hand gets messy fast. The 0/1 knapsack gives you a clean way to find the best pick every time.

🧠 The Choice at Each Item

The trick is to look at one item at a time. Then ask a simple question. For this item, given the space I have left, am I better off taking it or skipping it?

Let me put that choice in plain points.

  • Skip it: the value stays whatever it was without this item.
  • Take it: add this item’s value, but lose its weight from your space. You can only take it if it actually fits.
  • Pick the bigger one: whichever of those two gives more value wins.

That is the heart of it. Every cell in our table answers that one question. It does it for some item and some amount of space.

📊 The 2D DP Table

We build a table. Think of it as a grid you fill in row by row.

  • Rows stand for items. Row i means “we are allowed to use the first i items.”
  • Columns stand for capacity. Column w means “the bag can hold weight w.”
  • Each cell dp[i][w] holds the best value using the first i items with a bag of size w.

The word dp just means dynamic programming. It is a fancy name for a simple idea. You solve tiny cases first. You store the answers. Then you build bigger answers from them.

The rule for filling one cell:

  • If the current item’s weight is greater than w, it does not fit. So copy the value from the row above: dp[i][w] = dp[i-1][w].
  • If it does fit, take the bigger of two choices. You can skip it (dp[i-1][w]). Or you can take it (value[i] + dp[i-1][w - weight[i]]).

Tip

The “row above” is always the answer for the same bag size but with one fewer item. That is why we build the table top to bottom. Each new row only needs the row right above it.

🔍 A Small Worked Example

Let us use three items and a bag that holds weight 5.

Item Weight Value
1 2 3
2 3 4
3 4 5

So which pick wins? Take item 1 and item 2 together. Their weight is 2 + 3 = 5, which fits exactly. Their value is 3 + 4 = 7. No other combo that fits beats 7. So the answer is 7.

The flow below shows the choice we make for a single item that fits.

No

Yes

Look at item i and space w

Does item i fit in w?

Skip it: copy value from row above

Compare skip vs take

Keep the bigger value

📝 Steps to Solve 0/1 Knapsack

Here is the plan we follow in code.

  1. Make a table dp with rows for items (0 to n) and columns for capacity (0 to W).
  2. Fill row 0 and column 0 with zeros. With no items or no space, the best value is 0.
  3. Go through each item i from 1 to n.
  4. For each capacity w from 1 to W, ask: does item i fit?
  5. If it does not fit, copy dp[i-1][w].
  6. If it fits, take the bigger of dp[i-1][w] and value + dp[i-1][w - weight].
  7. The answer sits in the bottom-right cell dp[n][W].

💻 0/1 Knapsack in Code

The code below builds that table and prints the best value for our small example. Read the comments line by line.

knapsack.py
# builds the dp table and returns the best value
def knapsack(weight, value, n, W):
    # table starts filled with zeros (handles the base cases)
    dp = [[0] * (W + 1) for _ in range(n + 1)]


    # fill the table item by item
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weight[i - 1] > w:
                dp[i][w] = dp[i - 1][w]  # does not fit, so skip
            else:
                # best of skip vs take
                dp[i][w] = max(dp[i - 1][w],
                               value[i - 1] + dp[i - 1][w - weight[i - 1]])
    return dp[n][W]




weight = [2, 3, 4]
value = [3, 4, 5]
n = 3
W = 5
print("Best value:", knapsack(weight, value, n, W))

The output of the above code will be:

Best value: 7

Note

Time: O(n * W). We fill one cell for every item and every capacity. So the work is items times capacity. Space: O(n * W) for the table. Note that W is the capacity value, not the number of items. So a huge capacity makes this slow even with few items.

⏱️ Complexity at a Glance

What Cost Why
Time O(n * W) One step for each item and each capacity value.
Space O(n * W) The 2D table holds every item-capacity pair.
Space (rolling) O(W) You can keep just one row since each cell needs only the row above.

Caution

A common slip is mixing up the item index. In the table, row i maps to weight[i - 1] and value[i - 1]. That is because arrays start at 0 but our rows start at 1. Get this off by one and the answer goes wrong without crashing.

🧩 What You’ve Learned

  • ✅ The 0/1 knapsack picks items to get the most value without going over a weight limit.
  • ✅ The “0/1” rule means each item is taken fully or skipped, never split.
  • ✅ At each item you compare two choices: skip it or take it, then keep the bigger value.
  • ✅ A 2D DP table over items and capacity stores the best value for every smaller case.
  • ✅ The final answer sits in the bottom-right cell, and the whole thing runs in O(n * W).

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does the '0/1' in 0/1 knapsack mean?

    Why: The 0/1 rule means every item is all-or-nothing: take the whole thing or leave it.

  2. 2

    When an item's weight is greater than the current capacity w, what does dp[i][w] become?

    Why: If it does not fit, we cannot take it, so we copy the best value from the row above for the same capacity.

  3. 3

    Where does the final answer sit in the DP table?

    Why: dp[n][W] uses all items with the full bag capacity, which is exactly the answer we want.

  4. 4

    What is the time complexity of the table-based 0/1 knapsack?

    Why: We fill one cell for each item and each capacity value, so the work is items times capacity.

Score: 0 / 4

🚀 What’s Next?

Previous Fibonacci with Dynamic Programming Next Longest Common Subsequence

Share & Connect

Share on LinkedIn