The knapsack problem is an old and popular optimization problem. In this tutorial, we’ll look at different variants of the Knapsack problem and discuss the 0-1 variant in detail.
2. General Definition
Given a knapsack with a weight limit of , a collection of items with values and weights , the knapsack problem is defined as the optimization problem:
Now, the question is, what is the maximum value of the items that can be added to the knapsack such that the weight does not exceed the weight limit ?
3. Variants of Knapsack Problem
There are three variants of the above knapsack problem depending on how are defined. In this section, we’ll discuss these variants of this problem.
3.1. 0-1 Knapsack Problem
In this variant, the items are defined as:
Here, there is only one of each item available. So if is , that means the item is not added to the knapsack. If is , that means the item is added to the knapsack.
3.2. Bounded Knapsack Problem
In this case, the items are bounded by the condition:
The variable denotes the number of available copies of each item.
3.3. Unbounded Knapsack Problem
Here, the items are in the form:
In unbounded knapsack, there is no bound on the number of items. There are unlimited copies of each item available.
4. Why 0-1 Knapsack Problem Is NP-Complete?
The decision version of the 0-1 knapsack problem is an NP-Complete problem. Let’s see why.
Given weights and values of items, and , respectively, can a subset of items be picked that satisfy the following constraints:
A ‘Yes’ or ‘No’ solution to the above decision problem is NP-Complete. Solving the above inequalities is the same as solving the Subset-Sum Problem, which is proven to be NP-Complete. Therefore, the knapsack problem can be reduced to the Subset-Sum problem in polynomial time.
Further, the complexity of this problem depends on the size of the input values , . That is, if there is a way of rounding off the values making them more restricted, then we’d have a polynomial-time algorithm.
This is to say that the non-deterministic part of the algorithm lies in the size of the input. When the inputs are binary, it’s complexity becomes exponential, hence making it an NP-Complete problem.
5. Dynamic Programming Algorithm
In this section, we’ll discuss a dynamic programming approach for solving the 0-1 knapsack problem.
Let’s start by presenting its pseudocode:
Here, first, the algorithm creates a matrix of size .
Every entry denotes the maximum value the knapsack can take with a particular weight limit and items. We iterate over all possible weights (along the column) up to the weight limit and then pick a new item (next row) to see how the value of the knapsack increases.
To compute the maximum value at any given position in the matrix:
- If :
- If :
The function denotes the value at the position right above the current position , to check without adding the item , and presents the value of the knapsack if the current item is added.
A general idea is to pick the current item, which is the item (for a given weight limit if the first term in the function above is more than the second). The second term represents the total value at weight capacity if we do not pick the item.
6. An Example
Now, as we are done discussing the dynamic approach for the 0-1 knapsack problem, let’s run the algorithm on an example:
We can only carry in our grocery bag. We’re interested in finding what would be the maximum value (say calories here) of all the items in the bag combined.
For this example, we’ve already defined the weights and values:
Now, according to the algorithm, the first step is to initialize the matrix, , with the first row and the first column entries to zeros.
After the initialization of the matrix , it’s time to start the iteration step.
Let’s start the first loop. For the values: :
It can be verified that for because in that interval:
Let’s discuss the result in the table. Our first column is . It denotes that if the total weight is , no matter what item we choose, the maximum knapsack value is always .
Next, we choose the weight equals . With the value of , the maximum we can get is . So we filled all the rows with a maximum knapsack value of .
Now, let’s start the second loop.
For the values :
For the other values, we’ll increase the value of and keep everything else unchanged. We’ll start the loop with the values :
Inside the function were two choices – to either pick item # (in such case, the value of item # gets added) or to leave it.
Again, for :
because in that interval:
In this table, when the capacity is and the weight of the item is , we can’t choose the item. Therefore, the maximum knapsack value won’t update when capacity is equal to . For the rest of the capacity values, the maximum knapsack capacity values are updated by the formula.
Let’s continue the iteration and increase the value of . For the values :
Now, we need to increase the value of and run the loop :
Here, the weight . Therefore, we choose this item and update all the values in the row.
Let’s continue the iteration. Now, for the values :
Again, for the values :
The current weight here is . So, for the capacity values and , we can’t select this item. Hence, for capacity and , the maximum knapsack capacity values are unchanged. For the other capacity values, we do select the item and change the maximum capacity values.
It’s time to increase the value of and run the iteration. Therefore, the values in the loop :
We need to increase the value of , and everything else is unchanged. Hence, for :
Lastly, when the weight of the item is , we can update the values for which capacity value .
Finally, we’re done with the iterations. We end up with the result that when the weight limit is kgs, the maximum knapsack value is .
7. Time Complexity Analysis
Let’s analyze the time complexity of the dynamic programming algorithm in this section.
The first two initializations of function can be done in time. The for loop that iterates from to takes time. Under this, there is another for loop which goes from to . It takes time. Finally, the can be computed in time.
Therefore, a 0-1 knapsack problem can be solved in using dynamic programming. It should be noted that the time complexity depends on the weight limit of .
Although it seems like it’s a polynomial-time algorithm in the number of items , as W increases from say 100 to 1,000 ( to ), processing goes from bits to bits. The time complexity increases exponentially with the number of bits.
For example, if the weight is not large, then the complexity can be perceived as polynomial time in the number of input items, hence the term “pseudo-polynomial”.
In this article, we’ve discussed the 0-1 knapsack problem in depth. We’ve explained why the 0-1 Knapsack Problem is NP-complete.
For solving this problem, we presented a dynamic programming-based algorithm. We ran the algorithm on an example problem to ensure the algorithm is giving correct results. Finally, we analyzed the time taken by the dynamic algorithm.