PROBLEM: Imagine you are given $7, and in a store with 5 items, each item has a numerical cost and satisfaction (Yes, satisfaction can be quantified. Deal with it.) as follows:

What is the greatest amount of satisfaction you can get without blowing your budget? This is in fact an occurrence of the 0/1 Knapsack problem and can be solved with dynamic programming, which is a way of solving the problem by storing sub-calculations for sub-problems for later use. We’ll take a look at why storing sub-solutions works for the knapsack problem, before diving in and looking at the code.

Recurrence Relation

Say on your last trip to the store, there were only 4 items available: A, B, C, D, and you’ve already figured out what your favourite items are for all budgets ranging from $1 to $7. With the new item E in the picture, how would this knowledge make your decision simpler? Well, since item E only costs a dollar, and the best items to buy with a budget of $7 – $1 = $6 are B and C, we can increase our satisfaction and remain under budget if we buy item E.

This is the intuition we need to formalise what is called the recurrence relation for the algorithm. \(w_i\) denotes the cost of  item \(i\), while \(v_i\) denotes its satisfaction. Try to imagine \(M\) as a table, and \(i\) and \(j\) as co-ordinates on the table. \[ M[i,j] = \left\{ \begin{array}{l l} 0 & \quad \text{if } i=0 \text{ or } j=0\\ M[i-1,j] & \quad \text{if } w_i > j\\ \max \left( M[i-1,j-w_i] + v_i, M[i-1,j] \right)& \quad \text{if } w_i \leq j\\ \end{array} \right. \] With this recurrence relation, all that remains is to implement the algorithm. To do this, however, we first need to figure out which direction to start filling our table. Top-down-left-right, bottom-up-right-left, or even diagonal (top-left corner to bottom-right corner) methods have been seen in dynamic programming solutions to different problems. In this case, the value at the \((i,j)\)-th cell depends on \((i-1,j)\), and \((i-1,j-w_i)\), if it exists. This tells us that the table should be filled from the left to the right, top to bottom.

The Algorithm

This behaviour of the algorithm can be seen in the animation. The rows represent the \(i\) indices and the columns represent the \(j\) indices. The first column shows the Name, Cost and Satisfaction of each item. A read from a cell in the table shows up as a red indicator, while a write shows up as yellow. Finally, when the table is completely filled, the steps are retraced in order to determine the items to be bought in order to get at the maximum satisfaction. This is is represented by the cell being highlighted as orange.

The main part of the code is shown below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

for(var i=0;i<items.length+1;i++){
	for(var j=0;j<capacity+1;j++){
		if(i==0||j==0) M.$(i,j,0);
		else {
			var w = items[i-1].weight;
			if(w > j) M.$(i,j,M.$(i-1,j));
			else {
				M.$(i,j,
					Math.max(
						M.$(i-1,j-w) + items[i-1].value,
						M.$(i-1,j)
					)
				);
			}
		}
	}
}

Too simple?

NEW PROBLEM: What if every item had a type, and you were limited to only one of each type in your selection? How would that change the recurrence relation? I’ll cover that variation of the knapsack problem in part 2.

DPTable.js

If you liked the animation for the table used to demonstrate the algorithm, the code can be found here. This would allow you to write a dynamic programming algorithm as you normally would, and using M.$(i,j) to access values and M.$(i,j,value) to assign values.