The *knapsack problem* is one of the classic subjects of study in computer science. In this article, we'll outline two versions of the problem, discuss the implementation strategy, walk through a real example, and show full codes in multiple languages.

### The Knapsack Problem

The **Knapsack Problem** reads: **given a set of items, where each item has a weight and value, and a knapsack (bag) which has a maximum weight capacity, find the optimal selection of items which yields the highest total value**. There are multiple versions of this problem, most of which have similar code implementations to solve them. We will be focusing on two versions: the *0-1 Knapsack Problem* and the *Unbounded Knapsack Problem*. In both cases, we will use a dynamic programming approach to split the problem into sub-problems, solve those, and eventually solve the input. The alternative of trying each combination one by one and selecting the best one is not optimal and will take too long for most inputs. We'll cover the implementation details in each section below.

### 0-1 Knapsack Problem

This is the most common version of the Knapsack Problem. In this version, we are given a list of items which have weights and values, and a knapsack (bag) which has a maximum weight capacity, and **we can only select each item zero or one times.**

We will solve this problem using a **matrix** which will represent *sub-problems*. The rows will correspond to items available and the columns will correspond to weights. The first column will hold a weight of 0 and the first row will correspond to having no items to select. This is done for convenience of the algorithm. The remaining rows will correspond to sub-problems which have 1 item, then 2 items, then more items available to select, until the last row, which allows for any item to be selected. The columns indicate a weight of 1, then 2, until the *maxWeight* of the bag itself. Each cell corresponds to a sub-problem of having *row* items available to select in a bag of *column* weight. The last cell on the bottom right will hold the max-value for the full problem: all items available for a knapsack of *maxWeight*.

Before jumping into the code, we'll outline the algorithm in more detail using an example. For this example, we will have the items below available for selection with a knapsack which has a weight of **15**.

**Item One**:- Weight: 2
- Value: 4
**Item Two**:- Weight: 5
- Value: 10
**Item Three**:- Weight: 10
- Value: 11

The steps below outline how to create the matrix of sub-problems:

- Create a 2D array
*matrix*with dimensions of*items.length + 1*by*maxWeight + 1*. Default values should be*0*. - Iterate over the items using
*itemIndex*iterator: - Set
*item*to*items[itemIndex]*. - Iterate over weights from
*weight = 1*to*maxWeight*. - Set
*prevItemValue*to*matrix[itemIndex][weight]*. In other words, grab the best value from the previous sub-problem where the current item was not available. - If
*weight > item.weight*(if our sub-problem bag is big enough): - Set
*subProblemMinus*to*matrix[itemIndex][weight - item.weight]*. In other words, grab the value from the sub problem which doesn't have this item and has a weight*item.weight*smaller. - Add the
*value*of the current item to*subProblemMinus*and put that value in*subProblemPlus*/ - Set
*matrix[itemIndex + 1][weight]*to the max of*subProblemPlus*and*prevItemValue*. In other words, set the solution of this sub problem to the largest value between using this item and not using it. - Otherwise, set
*matrix[itemIndex + 1][weight]*to*prevItemvalue*. This means we're not using the current item and are just carrying over the value from the previous sub-problem.

Once those steps are completed, we will have a matrix which has the optimal values for each sub problem. With the example items specified above, we will have the matrix generated below:

Item Weight + Value | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Empty Row | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 : 4 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |

5 : 10 | 0 | 0 | 4 | 4 | 4 | 10 | 10 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 |

10 : 11 | 0 | 0 | 4 | 4 | 4 | 10 | 10 | 14 | 14 | 14 | 14 | 14 | 15 | 15 | 15 | 21 |

Once the matrix is generated, we can use the last two rows to check which items we've selected and store them in a list:

- We'll use
*maxWeight*, the input to the function, as a weight counter. - Create a new list
*bestItems*which records the optimal item selections. - For each item, starting with the last one, and having
*i = items.length - 1*: - Check if
*matrix[i-1][maxWeight]*is different than*matrix[i][maxWeight]*. In other words, check if this item was selected. If it was, proceed to the next steps: - Add this item to
*bestItems*. - Decrement
*maxWeight*by this item's weight.

With that, we have the list of the best item selections. If we also wanted the sum value, we could iterate over these items and sum them, or have our function return an object which holds the accumulated value and the list of items. In this case, the optimal selection will be the items *(weight: 10, value: 11)* and *(weight: 5, value: 10)*. The full code implementation is shown below.

### Unbounded Knapsack Problem

In this version of the knapsack problem, we can take an item any number of times instead of just once. We can use a different analagy for this problem: you are going to the store and need to maximize the value of the items you purchase. In that case, money would be treated as weight and value would be some measure of the items purchased. We'll still keep the same names of weight and value for the example here. Overall, the approach is very similar to the 0-1 Knapsack Problem: we'll be using a matrix to keep track of subproblems. However, the rules for generating the values in the matrix will be different.

Similar to what we did above, we'll walk through the implementation using an example. The items available are:

**Item One**:- Weight: 2
- Value: 4
**Item Two**:- Weight: 5
- Value: 10
**Item Three**:- Weight: 10
- Value: 11

These items are the same as the item's we've used in the 0-1 Knapsack example above. The values in the matrix, however, will be different, as different matrix generation rules apply to allow us to use items more than once. We can generate the matrix with the steps below:

- Create a 2D array
*matrix*with dimensions of*items.length + 1*by*maxWeight + 1*. Default values should be*0*for the accumulated value. - Iterate over the items using
*itemIndex*iterator: - Set
*item*to*items[itemIndex]*. - Iterate over weights from
*weight = 1*to*maxWeight*. - Set
*prevItemValue*to*matrix[itemIndex][weight]*. In other words, grab the best value from the previous sub-problem where the current item was not available. - Set
*thisItemPrevValue*to*matrix[itemIndex + 1][weight - 1]*. In other words, grab the value from the subProblem we've just calculated. - If
*weight > item.weight*(if our sub-problem bag is big enough): - Set
*subProblemMinus*to*matrix[itemIndex][weight - item.weight]*. In other words, grab the value from the sub problem which doesn't have this item and has a weight*item.weight*smaller. - Add the
*value*of the current item to*subProblemMinus*and put that value in*subProblemPlus*/ - If
*subProblemPlus > prevItemChoiceValue*, set*matrix[itemIndex + 1][weight]*to*subProblemPlus*and mark that we've just added*item*. - Otherwise, if
*thisItemPrevValue > prevItemChoiceValue*, set*matrix[itemIndex + 1][weight]*to*thisItemPrevValue*, indicating that the value for the sub-problem we've just solved is also the best choice here. - Otherwise, set
*matrix[itemIndex + 1][weight]*to*prevItemChoiceValue*. - Otherwise, if
*thisItemPrevValue > prevItemChoiceValue*, set*matrix[itemIndex + 1][weight]*to*thisItemPrevValue*, indicating that the value for the sub-problem we've just solved is also the best choice here. - Otherwise, set
*matrix[itemIndex + 1][weight]*to*prevItemChoiceValue*.

In the matrix below, each cell shows the accumulated value so far and the weight of the item just added, or a weight of 0 if no change was made: *accValue,weight*.

Item Weight + Value | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Empty Row | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 |

2 : 4 | 0,0 | 0,0 | 4,2 | 4,2 | 8,2 | 8,2 | 12,2 | 12,2 | 16,2 | 16,2 | 20,2 | 20,2 | 24,2 | 24,2 | 28,2 | 28,2 |

5 : 10 | 0,0 | 0,0 | 4,2 | 4,2 | 8,2 | 10,5 | 12,2 | 14,5 | 16,2 | 18,5 | 20,2 | 22,5 | 24,2 | 26,5 | 28,2 | 30,5 |

10 : 11 | 0,0 | 0,0 | 4,2 | 4,2 | 8,2 | 10,5 | 12,2 | 14,5 | 16,2 | 18,5 | 20,2 | 22,5 | 24,2 | 26,5 | 28,2 | 30,5 |

Once the matrix is generated, we can use the last row to check which items we've selected and store them in a list:

- We'll use
*maxWeight*, the input to the function, as a weight counter. - Create a new list
*bestItems*which records the optimal item selections. - While
*maxWeight*> 0: - Get the entry in
*matrix[items.length][maxWeight]*. - If that entry has an item marked (in other words, if we've added an item at this point):
- Add the item added to
*bestItems*. - Decrement
*maxWeight*by the item's weight. - Otherwise, stop looping.

In this example, the optimal solution is to pick the item *(weight: 5, value: 10)* once and the item *(weight: 2, value: 4)* 5 times, for a total value of 30. Note that the ability to select an item more than once gave us a higher value than we got in the 0-1 Knapsack version.

In the code below, we'll be using a matrix of *KnapsackEntry* instead of numbers. Each instance will hold the accumulated value so far and the item which was just added, or a previous *KnapsackEntry* reference if no item was just added. The matrix will be initialized to *KnapsackEntry* instances which have a null *Item* reference and accumulated value of 0.

### Space and Time Complexity

In our complexity analysis, *n* will refer to the number of items and *w* will refer to the max-weight input. The complexity is the same for both versions of the problem discussed above.

Complexity | Notes | |
---|---|---|

Space | `O(n * w)` | Our matrix will store n+1 rows and w+1 columns. |

Time | `O(n * w)` | Each cell is processed once and read a constant number of times. |