The 0-1 Knapsack problem is a very famous problem that can be solved using dynamic programming in pseudo-polynomial time. A variation of the problem can be defined as follows:
You have a Knapsack that can store M items. You have N items with weights W and values V each respectively. Which items would you choose to maximize your profit.
Before we start discussing the problem, lets talk about what makes this algorithm a pseudo-polynomial time algorithm rather than a polynomial time algorithm aka what is meant by pseudo-polynomial time?
For an instance take my word for it that the running time of this algorithm is O(nW). Now for a 32-bit machine and 64-bit machine, the number of computation we would have can be calculated as follows:
As you can see the running time increases instead of decreasing on a 64-bit machine when compared to a 32-bit machine. This is not expected of an algorithm running in polynomial time since such an algorithm would scale linearly.
Now to the main problem.
Let’s take an example:
If the Knapsack can take a maximum weight of 10, and we have the following 3 items, what would we do.
Item Value Weight
1 $30 6lb
2 $14 3lb
3 $16 4lb
Let K(W) be our final solution. So how would we define K(W)? Our target is to accumulate maximum value in treasure while keeping the total weight <= W.
Thus, K(W) can be defined as:
K(W) = maximum value achievable with capacity W.
Now there are two ways to look at this problem. If you look closely at it, the first thing that will probably come to your mind is, hey, its a maximization problem based on constraints such as the capacity of the Knapsack. And right you are, while solving via DP (Dynamic Programming), it does turn out to be a maximization problem.
So what’s out optimal sub-structure and does it repeat? Let’s take a look at this graph to figure that out:
Let’s have a graph with the weights as columns and the capacity of the Knapsack as rows. At any point of time, an edge has two choices, either choose to pick that item or not choose to do so. If it picks that item, it goes to a certain state, if it doesn’t, well, it goes to a different state. Of course, they cannot go to just about anywhere. For instance, they cannot go to a state where the weight of the Knapsack is smaller than the total weight of the items.
However, please notice that whilst we started off saying that we are trying to solve a maximization problem, we are no longer doing so. The reason behind this is, although we can build a graph that makes it look like a maximization problem, it is much easier to solve as a minimization problem.
Now that we have the graph it is fairly easy to solve. Use any path finding algorithm and find the shortest path from the start to the end. If we sort it topologically and then solve the running time comes to O(V+E) whereas algorithms like Bellman-Form would give a running time of O(VE). I would leave the code for that for another post or if you can be a good guy/girl and post it in the comments.
We are going to figure out how to get our optimal sub-structure from this graph and also turn it from a minimization to a maximization problem.
To do so, let’s figure out which one thing are we repeating at every step. We are deciding at each step whether to select that item or not. At every step, we do not know what we have already selected and we do not know what we are going to select in the future. All we know is that we are either going to select this item or we are not going to select it. That’s all and that is our optional sub-structure. Mathematically, we can define it as:
Like we discussed earlier we have two choices. The first part of the representation defines if we didn’t have to choose the item and the second part vice versa. In the second part, if we do choose an item, we need to add the value of that item and reduce our Knapsack’s capacity.
Now that we got the representation, how are we going to use it? Let’s take a 2D matrix with the sum as rows and the items (weights) as columns with one extra column as we took for our graph representation. Now we can recurse in a topological sort manner where we start from the rightmost column and the topmost row and proceed. With that in mind, here’s the JAVA code for the algorithm:
In a variation of this problem, you might be asked, what if instead of the weight accumulated being less than and equal to the capacity of the Knapsack, you have to find the one with the exact weight as that of the capacity. The difference between the two lies in the fact that if its less than and equal the value might be different from if its exactly equal. What would you do in that case?
I will leave that to be covered in another post. Till then, bye!