Knapsack Problem Step by Step with a DP Table

The knapsack problem is where most students meet dynamic programming for the first time. And it is where many of them panic. The code fills in a mysterious table, and nobody explains what the table actually means.

Let me fix that. Behind every cell in that table is one small question. Once you see the question, the whole method stops being scary.

What is the knapsack problem?

The knapsack problem gives you a bag that can hold only so much weight. You have a set of items, each with its own weight and its own value. Your job is to pick the items that fit in the bag and give you the most total value.

This post covers the 0/1 knapsack. The 0/1 part means each item is all or nothing. You either put the whole item in the bag or you leave it out. You cannot take half of it. That single rule is what makes the problem interesting, because now you have to choose.

It is one of the most common dynamic programming questions in placements. If you are new to this idea, our guide on how recursion works is a useful warm-up, because dynamic programming grows out of recursion.

The one choice that solves it

The whole problem comes down to one question, asked again and again. For each item, you have two options. Take it, or skip it.

If you skip the item, your best value is whatever you could already get without it. If you take the item, you gain its value, but you use up some of the bag’s weight, so you have less room for the rest. Dynamic programming simply tries both options and keeps the better one.

That is the heart of it. Every cell in the table you are about to see answers this exact question for one item and one weight limit. Nothing more.

How does the knapsack DP table work step by step?

Reading the rule is not enough. You have to watch the table fill in. So let’s solve a small example by hand.

Say the bag holds a weight of 5. We have three items: item 1 weighs 2 and is worth 3, item 2 weighs 3 and is worth 4, item 3 weighs 4 and is worth 5.

We build a table. Each column is a weight limit from 0 up to 5. Each row adds one more item to the choice. A cell holds the best value you can reach with that item set and that weight limit. Here is the finished table.

Look at one cell to see the take or skip choice in action. Take the cell for items 1 and 2 with a weight limit of 5, which holds a 7. Skipping item 2 leaves the value at 3, what item 1 alone could manage. Taking item 2 gives its value of 4, plus the best value for the leftover weight of 2, which is another 3. That adds to 7. Since 7 beats 3, the cell stores 7.

The answer is the green cell in the bottom right, also a 7. It means the best you can do with all three items and a bag of weight 5 is a value of 7. That comes from taking item 1 and item 2, whose weights of 2 and 3 fill the bag exactly.

Knapsack problem code in Python and C++

The code is just the table written in two loops. The outer loop walks the items. The inner loop walks the weight limits. Here it is in Python.

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

The line with max is the take or skip choice. The first option skips the item. The second option takes it and adds the best value for the remaining weight. Here is the same logic in C++, the language most Indian placement tests expect.

int knapsack(int weights[], int values[], int n, int capacity) {
    int dp[n + 1][capacity + 1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (weights[i - 1] <= w)
                dp[i][w] = max(dp[i - 1][w],
                               values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            else
                dp[i][w] = dp[i - 1][w];
        }
    }
    return dp[n][capacity];
}

Both versions build the same table and return the bottom-right cell. That last cell is your answer.

What is the time and space complexity of the knapsack problem?

The time is O(n times W), where n is the item count and W is the bag’s capacity. You fill one cell for every item and every weight limit, and each cell takes constant work. The space is also O(n times W) for the table, though you can cut it to O(W) by keeping only the current row and the one above it.

Here is the catch nobody mentions. That O(n times W) looks fast, but it hides a trap. The W is the value of the capacity, not the number of items. So if the capacity is a huge number, the table is huge too, even with only a few items. Experts call this pseudo-polynomial, which is a fancy way of saying it is only fast when the capacity stays reasonable. You can read the formal details on Wikipedia’s knapsack page.

0/1 knapsack vs fractional knapsack

There are two famous knapsack problems, and people mix them up. The 0/1 knapsack in this post forces a whole item or none, and it needs dynamic programming. The fractional knapsack lets you take a piece of an item, like half a bag of rice. That version is easier. You just grab the items with the best value per weight first, which is a greedy method, not dynamic programming. Knowing which one you face is half the battle. Both show up in the wider world of dynamic programming study.

FAQ

What is the 0/1 knapsack problem?

It is a problem where you fill a weight-limited bag for the most value, and each item must be taken whole or skipped. You cannot take a fraction of an item. It is solved with dynamic programming.

Why does the knapsack problem use dynamic programming?

Because the same smaller problems come up over and over. Dynamic programming stores those answers in a table so each one is solved only once, which avoids slow repeated work.

What is the time complexity of the knapsack problem?

O(n times W), where n is the number of items and W is the bag’s capacity. It is called pseudo-polynomial, because the speed depends on the size of the capacity value, not just the item count.

What is the difference between 0/1 and fractional knapsack?

The 0/1 version takes whole items only and needs dynamic programming. The fractional version allows pieces of items and is solved by a simpler greedy method that picks the best value per weight first.

Can the knapsack problem be solved with recursion alone?

Yes, but plain recursion repeats the same work and gets slow. Adding a table to store results, which turns it into dynamic programming, is what makes it fast.

How do I find which items were chosen, not just the value?

Walk the table backward from the last cell. If a cell’s value differs from the one directly above it, that item was taken. Keep stepping back to rebuild the full list.

So what should you remember?

The knapsack problem is one question asked many times. For each item, take it or skip it, then keep the better result.

The table is just a place to store those answers so you never repeat one. Build the small cells first. The big answer falls out of the last one.

Now try the table yourself with a bag of weight 6 and the same three items. What value lands in the final cell?