Knapsack Dynamic Programming Algorithm

Problem Description

Given n items of known weights (w1,….,wn) and values (v1,…,vn) and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.

The 0-1 Knapsack Problem can be solved using the brute-force exhaustive search technique where you must find all 2n combinations. However, using Dynamic Programming is much more efficient!

Videos

Video made by Zachariah Threet for Design of Algorithms in May 2020

Video made by Joshua Adams for Design of Algorithms in May 2020

Video made by Jordan Myers for Design of Algorithms in May 2020

Algorithm Steps Explained with Given Input

The knapsack has a total weight capacity (W) of 10 pounds.

There are five items that I would like to put in my knapsack, but if I include them all, I would exceed the weight limit.

The items are described below:

Item 1 is a tennis shoe. It weighs 1 pound and has a value of $5.00
Item 2 is a pineapple. It weighs 2 pounds and has a value of $3.00
Item 3 is a toaster. It weighs 4 pounds and has a value of $5.00
Item 4 is a rack of baby back ribs. It weighs 2 pounds and has a value of $3.00
Item 5 is a 2 liter bottle of mountain dew. It weighs 5 pounds and has a value of $2.00

Step 1: Set up the Memoized Table

With the dynamic programming algorithm, we will memoize (or save) intermediate results in a table, which I demonstrate as a two-dimensional array in the table below. The name of the table is F. The table will have W+1 columns, where W is the weight capacity of the knapsack. So that means there will be 11 columns. The table will have n+1 rows, where n is the number of items. So that means there will be 6 rows. I will label each of the columns in the column header with an index value of the columns and I will label each of the rows in the row header with an index value of the rows. This will add an additional row & column to the table below.

Below is the initial table, with step 1 already done, which is to initialize all elements to zero. I will be using j to indicate the index value of the column, which represents the weight/capacity of the knapsack and using i to indicate the index value of the row, which represents the item.

	0 pounds	1 pound	2 pounds	3 pounds	4 pounds	5 pounds	6 pounds	7 pounds	8 pounds	9 pounds	10 pounds
0	0	0	0	0	0	0	0	0	0	0	0
item 1	0	0	0	0	0	0	0	0	0	0	0
item 2	0	0	0	0	0	0	0	0	0	0	0
item 3	0	0	0	0	0	0	0	0	0	0	0
item 4	0	0	0	0	0	0	0	0	0	0	0
item 5	0	0	0	0	0	0	0	0	0	0	0

Step 2: Repeating Part of the Algorithm until we have a Solution

For each element in the table starting with i=1 and j=1, we will select the value based on a condition. In the calculations listed below, wi is the weight of the item at index i and vi is value of the item at index i.

If (j-wi >= 0) then F[i][j]=max{F[i-1][j] or vi+F[i-1][j-wi]

If(j-wi < 0) then F[i][j] = F[i-1][j]

So, for example, at i=1 and j=1, the weight of item 1 is 1 pound and the value is $5.00. So, j-wi is 1-1, which is 0. So that means F[1][1] = max{F[0][1] or 5+F[0][0]}. 5+F[0][0] is 5 and so F[1][1] will be assigned 5.

You would go through each row and each column in a nested loop and do these same steps until every element in F has a value. The resulting table is below.

	0 pounds	1 pound	2 pounds	3 pounds	4 pounds	5 pounds	6 pounds	7 pounds	8 pounds	9 pounds	10 pounds
0	0	0	0	0	0	0	0	0	0	0	0
item 1	0	5	5	5	5	5	5	5	5	5	5
item 2	0	5	5	8	8	8	8	8	8	8	8
item 3	0	5	5	8	8	10	10	13	13	13	13
item 4	0	5	5	8	8	11	11	13	13	16	16
item 5	0	5	5	8	8	11	11	13	13	16	16

Output

The output of this algorithm is F[i][j], which in my example is F[5][10], which is 16. This means that the maximum value that we can fill our knapsack with is $16.00 when it has a weight limit or capacity of 10 pounds and with the five items described.

One neat thing is that we can find out the maximum value we could have at all weight limits between 0 pounds and 10 pounds with this table. For example, in the column with 7 pounds, the largest value is 13, which means $13 is the highest value we can have if the weight limit were only 7 pounds.

Complexity/Efficiency of the DP Algorithm

Time Efficiency is O(nW).

Complexity does not contradict the fact that the knapsack problem is NP-complete, since W, unlike n, is not polynomial in the length of the input to the problem. The length of the W input to the problem is proportional to the number of bits in W, log W, not to W itself. However, since this runtime is pseudo polynomial, this makes the knapsack problem a weakly NP-complete problem.