Dynamic Programming – Knapsack Problem

Dynamic Programming has two key attributes:

  1. Recursive Substructure
  2. Memo-ization

A recursive substructure is a basic programming concept in which you break down your problem into smaller sub-problems, and that solution to the problem can be constructed using solution to the sub-problems. After find the recursive substructure, we can then keep track of the intermediate result of the sub-problems, and then solve intermediate sub-problems in a specific order to optimize the efficiency of the algorithm.

Here is a youtube video that does a great job explaining the concepts.

To illustrate the power of dynamic problem, I am going to solve the classic knapsack problem. Basically, you are given a backpack with limited capacity, and a list of items with various weight and values. Your algorithm should return a list of quantities of items that you can fit in your backpack to yield the highest value. You will see that this is the general pattern for most dynamic programming problems, in which you are given a constraint and different attributes, and then optimize for a specific attributes.

Instead of start with a bag of 0 items, like we would do in a recursive-backtracking approach, we should imagine starting with a bag with optimal values, and then reverse engineer to an empty bag. Here is the first question we need to ask ourselves.

Pretend we already have the solution, what was the last step we took to get to the solution?

In this case, the last step we took was putting one of the items in our backpack. Following this logic, we can then assume:

//best is a function that yields best value based on given capacity
//n is total capacity
//i is weight of current item
//P(i) is value of the current item
Best(n) = Maximum of ( P(i) + Best(n-i) )
//Where i iterates from first to last items;

So now, with a mental model, our solution will be:

See it on GitHub
function knapsack(capacity,items){
 //Object to store optimal values of different capacity
 var best = {};

 //Find optimal value based on given capacity
 var recurse = function(cap){
   //Base case
   if(cap <= 0 ) return 0;

   //Iterate over items
   items.forEach(function(item){
     //Return if cap is negative after subtracting item weight
     if(cap - item[0] < 0) return;

     //Set value equal to item value + recurse(new capacity)
     var value = item[1] + recurse(cap-item[0]);

     //Ternary operation 
     //IF best[cap] doesn't exit, 
     // set value
     //otherwise set greater of value OR best[cap]
     best[cap] = !best[cap] ? value : value > best[cap] ? value : best[cap];
   })

 return best[cap]
 };

 recurse(capacity);
 return best[capacity];
};

Our algorithm is functional now. Let’s test it!

var things = [[1,1],[2,3],[3,6],[4,10],[5,13]];
console.log(knapsack(1,things));  // 1
console.log(knapsack(13,things)); // 33
console.log(knapsack(22,things)); // 56
console.log(knapsack(56,things)); // .... NOTHING!

My Macbook Pro won’t return anything for 56 because the algorithm is too expensive. Here is the awesome part of dynamic programming! We simply have to add one line of code to memo-ize the result.

See it on GitHub
function knapsack(capacity,items){
 //Object to store optimal values of different capacity
 var best = {};

 //Find optimal value based on given capacity
 var recurse = function(cap){
 //Base case
 if(cap <= 0 ) return 0;

 // Return Memo-ized
 if(best[cap]) return best[cap];

 //Iterate over items
 items.forEach(function(item){
 //Return if cap is negative after subtracting item weight
 if(cap - item[0] < 0) return;

 //Set value equal to item value + recurse(new capacity)
 var value = item[1] + recurse(cap-item[0]);

 //Ternary operation 
 //IF best[cap] doesn't exit, 
 // set value
 //otherwise set greater of value OR best[cap]
 best[cap] = !best[cap] ? value : value > best[cap] ? value : best[cap];
 })

 return best[cap]
 };

 recurse(capacity);
 return best[capacity]
};

Now if you test the algorithm again:

var things = [[1,1],[2,3],[3,6],[4,10],[5,13]];
console.log(knapsack(1,things));    // 1
console.log(knapsack(13,things));   // 33
console.log(knapsack(22,things));   // 56
console.log(knapsack(56,things));   // 144
console.log(knapsack(77,things));   // 199
console.log(knapsack(2123,things)); // 5519

So just how much time did we save? Let’s look at the table below:

Screen Shot 2015-03-18 at 6.45.05 PM

So what caused the dramatic improvement? By returning the memo-ized result and skipping the rest of the recursive call, we saved a lot of repeated work. I will illustrate the call stack of the example below.

// Find B(5), List of 3 Items [1,1],[2,3],[3,5]
// P(1) is Value of item 1
// W(1) is Weight of item 1
// B(5) is Optimal value with capacity of 5
i = 0, B(5) = P(1) + B(4)  // this is triggered B(4)
i = 0, B(4) = P(1) + B(3)  // B(3)
i = 0, B(3) = P(1) + B(2)  // B(2)
i = 0, B(2) = P(1) + B(1)  // B(1)
i = 0, B(1) = P(1) + B(0)  // B(0) return 0, memo-ized B(1) = 1
i = 1, B(1) = P(2) + B(-1) // B(-1) hit negative, stop B(1)
i = 0, B(2) = P(1) + B(1)  // B(1) return 1, memo-ized B(2) = 1
i = 1, B(2) = P(2) + B(0)  // B(0) return 0, memo-ized B(2) = 3
i = 2, B(2) = P(3) + B(-1) // B(-1) hit negative, stop B(2)
i = 0, B(3) = P(1) + B(2)  // B(2) return 3, memo-ized B(3) = 3
i = 1, B(3) = P(2) + B(1)  // B(1) return 1, memo-ized B(3) = 4
i = 2, B(3) = P(3) + B(0)  // B(0) return 0, memo-ized B(3) = 5
i = 0, B(4) = P(1) + B(3)  // B(3) return 5, memo-ized B(4) = 6
i = 1, B(4) = P(2) + B(2)  // B(2) return 3, no change to B(4)
i = 2, B(4) = P(3) + B(1)  // B(1) return 1, no change to B(4)
i = 0, B(5) = P(1) + B(4)  // B(4) return 6, memo-ized B(5) = 7
i = 1, B(5) = P(2) + B(3)  // B(3) return 5, memo-ized B(5) = 8
i = 2, B(5) = P(3) + B(2)  // B(2) return 3, no change to B(5)

For all the highlighted lines, since we had already memo-ized the intermediate results, the algorithm would return the intermediate results without continue the iteration. Had we not used memo-ization, each of the highlighted lines would result in another iteration of the list of items. We effectively saved 5 * 3 = 15 iterations!

Now, if you want to challenge yourself, the original knapsack question asked for an array of quantities as output, instead of just optimal value. For example, B(1) in the previous example would return [1,0,0]. The complete solution is posted here on my GitHub page.

Happy Hacking!