Dynamic Programming: 0–1 Knapsack

Dynamic Programming Problem #1 : 0–1 Knapsack

Photo by Emile Perron on Unsplash

Before starting up with the Knapsack Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Knapsack problem.

With that being said let’s begin !

What is 0–1 Knapsack ?

The problem of 0–1 Knapsack goes something like this.

We are given an empty bag that can hold maximum of W weight. We have a set of N items. Each item has an associated value v and an associated weight w. Given these information, find the maximum profit you can make by carrying away as many items as you want, given that the sum of weights of the items does not exceed W.

So, for the sake of this example let’s assume :

W = 10kg

N = 5

value = [2, 4, 6, 1, 9]

weight = [3, 2, 8, 7, 4]

Possible Approach

Since the problem is more or less about inclusion or exclusion of an item from the entity set thus we can say that we should check all possible combinations of the items and see which one has the maximum value.

So, a pseudo code would be something like :

• Pick one item
• See if it’s weight exceeds the current limit
• if it does, then we do not include that item and move onto the next item
• If it doesn’t then, we consider all the subsets where that item is included and where that item is excluded. Then we just simply return the one which has a higher value

Seems a bit confusing right ? Let’s look at the code for better understanding.

Recursive Approach

Remember that we should always think of a Recursive approach first in order to make our work easier for thinking a DP based solution. The recursive code looks something like this

This would be a simple recursive solution for the 0–1 Knapsack Problem. But we all know that this isn’t the best possible way to solve it because of the issues that a recursive solution causes. Thus we move onto writing a memoized solution next using the same recursive code.

Memoized Solution

Let’s recall the key concepts that we need in order to build a memoized solution from a recursive solution.

• Store the computed values so that the next time the same call occurs, we won’t need to compute it again.
• There are two changing parameters : W and N. Thus the store will be a two dimensional matrix.
• Thus, store[N][W] will contain the answer for the function call knapsack(W, N, value, weight)

With these two rules in mind let’s see how a memoized solution looks like

Thus with the help of store variable to store the computed values for later use, we are easily able to derive a memoized solution from the recursive solution. Now, let’s have a look at the Bottom-up approach for the same.

Bottom-up Approach (Tabulation)

We must remember that the key to writing the tabulated solution is having a proper understanding of the following points

• store[N][W] : This holds the answer for the function call given by knapsack(W, N, value, weight)
• The dimensions of store depends on the number of changing parameters. Which in this case are 2 : W and N.
• We must have a relation between n-th computation and previous computation(s) so that we can build the store without actually having to call the function recursively.
• The base condition of the recursive approach is used to initialize the store so that we can fill up the rest of it using the relation derived from recursive solution.

With these points in mind, coding a tabulated solution is a piece of cake.

1. Dimension of store

Since values of W range from 0 to W and that of N range from 0 to N. Thus we have a total of W+1 * N+1 possible combinations.

Thus the dimensions of store will be (N+1) x (W+1) or vice versa (as per our own implementation wish).

2. Relation between entities

While writing these relations we must keep in mind that store[N][W] is same as knapsack(W, N, value, weight) since that’s how we have mapped them.

• Inclusion Case : When the item is included then the value of the current function call knapsack(W, N, value, weight) is same as

max(knapsack(W, N-1, value, weight), knapsack(W-weight[N-1], N-1, value, weight))

Where we take the max of inclusion and exclusion case.

• Exclusion Case : When the item isn’t included the value of the current function call knapsack(W, N, value, weight) is same as the function call knapsack(W, N-1, value, weight)

3. Initializing the Store

We must keep in mind that the store is initialized using the logic of base condition from the recursive solution. Thus all the entries where either of the index is 0 (i.e. either W = 0 or N = 0), the value of store[w][n] will also be equal to 0.

Now that we have all the basic ideas needed for Tabulated solution, let’s see how the coded solution looks like

That’s how we can derive a tabulated solution with a few points in mind and the proper recursive solution.

With this we have come to an end of 0–1 Knapsack Problem. I hope the article was informative and helped you to properly understand the concept of DP and what should be the approach for writing a memoized and tabulated solution for 0–1 Knapsack Problem.