Solve Complex Problems in JavaScript with Dynamic Programming

Instructor: [00:00] Dynamic programming is a technique that helps solve a hard problem by breaking it into sub-problems and solving those sub-problems first. It's useful when we're trying to optimize something given a constraint.

[00:12] For our example, let's say that we're going camping, and we have a backpack that can only carry four pounds worth of stuff. Each item is given an arbitrary number value of what it's worth. What is the best-case value of stuff we can get into our backpack given our four-pound constraint?

[00:29] Every dynamic programming solution involves a grid. Each cell is a sub-problem. Let's think about how we can divide this problem into sub-problems.

[00:38] Before we get any further, I want to take a step back and say that dynamic programming is a hard concept. Don't worry if you don't get it right away. It will most likely take you some time to grasp the concept.

[00:50] The way that we can break this problem down into sub-problems is seeing what the max items we can get into smaller sub-backpacks. For example, we'll start by figuring out what is the best case for a backpack that holds just one pound, and working out from there.

[01:05] The first thing we'll do is make our constraint backpack weight of four be in an array weight one through four, and another array with our items -- rope, tent, and food.

[01:16] Let's then make a function to create an empty grid we can see and work with. We'll start with an empty array, and then we'll have two for loops -- one that creates the number of rows or items we have, and the second for loop that adds in the value of columns or constraints we'll have.

[01:32] Once we've created that, we'll return our grid. Let's assign this to a variable called matrix, which we can then console.log out and see what we have to start with. Perfect.

[01:44] By putting our constraint and items into arrays, we can dynamically add arrays and values to our grid. As we see, we have three arrays, and each of those have four values. The three arrays represent a row or an item. Each zero represents a constraint weight one through four.

[02:03] This first zero is at location row 1, column 1, or looking at our grid image above, rope at weight 1. Let's go ahead and create our fill in the grid function that accepts a grid. This is where we're going to use two for loops to step through each row and column combination to solve our sub-problems. We'll also pluck out the value and weight of each item so we can use in our calculations.

[02:29] The first set of sub-problems we're trying to solve is the rope row, which means we're trying to fit the rope inside of a backpack that only holds each corresponding weights one through four. Since the rope is only one pound, it fits in each backpack, which means our first row and column will be 1,500 across each sub-problem.

[02:48] We can do some pseudo code and say if there's not a rope before this current one, meaning this is the first time through, just use the value for this row-column combination. Of course, this only works if rope is the first in the array, but for simplicity's sake, we'll just do this. Then we'll console.log our fill in the grid with our matrix to see what we've got so far. Perfect.

[03:10] Again, since our rope is only one pound, it fits in each backpack weight column. We have 1,500 across the first row. Remember, we're trying to maximize the value of the backpack. This row represents the current best guess for this max.

[03:24] Right now, according to this row, if we had a backpack of capacity four pounds, the max value we can put in there is 1,500.

[03:32] Next, we'll do the tent row, which has a weight of four and a value of 3,000. The tent does not fit in a backpack with a weight capacity of one, two, and three pounds, which means 1,500 or just the rope remains the max value these backpacks can hold. We'll carry 1,500 down.

[03:49] We'll say that grid, row, and column is going to equal the previous row, same column value. Our console.log shows us that these first weight combinations of one, two, and three were carrying along the max we have so far of the rope, 1,500 across.

[04:04] Again, if the weight of the current item is larger than the constraint -- in our case, the tent cannot fit in weights one through three -- we need to take the previous max value calculated for those weight constraints.

[04:16] Then if our current item weight equals a constraint as our tent, which weighs four pounds, and so does our last constraint backpack, we take the greatest value between the previously calculated item at constraint weight, and the current item's value.

[04:31] We see that a console.log shows us that we're getting 3,000 here for this last column, which is correct, because 3,000 is a larger value than the one rope at value 1,500.

[04:42] Let's finish by doing the food row. We can see that our function is already doing some work for us. Since food has a weight of three, it is taking the previously calculated largest value at those two weight constraints, which is just the rope at value 1,500.

[04:58] Then since our food value is larger than the previously calculated value of 1,500, we're inserting 2,000. To calculate the last column will continue this if and say let div equals constraint column, minus one, minus weight.

[05:12] The current grid row-column is equal to the larger of the previously calculated same row-column value, and the value of our current item, plus the max value of the difference between the leftover weight and the current weight.

[05:25] Our console.log shows us that the new max value for our backpack that weighs four is now 3,500. If you missed that calculation, let's review it again.

[05:35] Since our food has a weight of three, there's one pound left over for the four-pound backpack. We found this out and assigned it to this div variable. Next, we're taking whichever of these two are greater.

[05:46] The previously calculated max value at backpack constraint weight four, which is 3,000, and our food at weight three, plus our currently max calculated value of one, which was 1,500. This gets us a value of 3,500, beating out 3,000. Our answer to our question will always be found in the last row, which is 3,500.

[06:10] As a side product, we also now have the answers to what's the max value that could be taken with the smaller backpacks?

[06:18] What's nice about this dynamic programming function we've created is what happens is when we add an item, such as an iPhone, which has a value of 2,000 and a weight of one? We throw that into our items array. We'll see that we now have our grid made up of four rows or four sets of arrays.

[06:35] Our max calculated for our backpacks are 2,000, 2,5000, 3,500, and 4,000 for a backpack at four pounds.

[06:44] Let's conclude with some final thoughts on dynamic programming. Can the value of a column never go down? No. At every iteration, we're restoring the current max value. The value can never get worse than it was before.

[06:55] What happens if we change the order of the items? Each column row would be different, except for that last row, which shows us the max. Remember, we need to go back and iron out that first item logic.

[07:07] Dynamic programming only works when each sub-problem doesn't depend on other sub-problems. If we compare it against other bigger notation algorithms, such as calculating every single combination of items, which is O(2^n), if there were 32 items, that would be four billion possible sets, as opposed to 128 column row cells we need to loop over.