Solving 0–1 knapsack problem using dynamic programming
This is a classic problem that many computer science students and software engineers will face. Given content is, given a list of items with their values and weights, retrieve the maximum value of the items whose weight w is less than the overall capacity allowed.
To do this, there are a few ways to approach problem:
- Brute force solution: find all possible subsets of the items that has a weight that fits into the overall capacity and select the subset that contains the maximum value. While this works, the runtime will be O(2^N) which is not feasible.
- Dynamic programming: we can create a 2 dimensional table that keeps track of the values of different subsets. The rows will represent the weight of the items, and the columns will represent the maximum weight that can be contained. We will proceed to populate the table, where each entry in the table is the value of the optimal subset with the given weight allowed at the column.
With this article, we will proceed with the dynamic programming solution.
If our weight in the current iteration is lower than the given capacity value j in the table, we simply take the number right above us, which is a part of sub-solution that was solved as part of dynamic programming. This number is the optimal value that is calculated previously.
On the other hand, if the capacity value j is greater than current weight[i], we take the maximum of the two possible values:
- the number right above us. This might contain the optimal value we can get from the knapsack.
- the current value that is in the knapsack plus the optimal value that can be retrieved from the table as long as the overall value does not exceed the allowed capacity. This will be represented as dp[i — 1][j — weights[i — 1]] + values[i — 1]
Here is an example of how the code works:
Over here, we create a dp table that is a 2 dimensional array. The first dimension, i, is a representation of all the values. We have an empty first row for the ease of the algorithm. The second dimension, j, represents the current weight we are at. If the current item weight is greater than the given capacity j, we simply fill in the current value with dp[i- 1][j], the previously calculated optimal solution. Else, we need to take dp[i- 1][j], compare that with dp[i- 1][j- weights[i — 1] + values[i -1].
What is dp[i — 1][j — weights[i — 1]] + values[i — 1] mean? It means we take the current value and out of the remaining capacity available(j — weights[i — 1), we choose the remaining optimal solution that was recorded in the table and add it together. If this is greater than the optimal solution above us, we choose this new value, etc.
After populating the whole table, we can take the value of the last row and last column, as this is the overall optimal value that we can get from our knapsack.
Let’s work through the following example:
