An introduction to dynamic programming

So. 7:30 am on a cold, winter monday morning. What better time to talk about programming?

Today, I’m going to talk about a problem given to our students in the last midterm. Unfortunately, as it was the last exercise in the midterm, its relative easiness did not mean it was solved by many students. This problem is a thinly veiled version of the Knapsack problem:

Karina is going on a diet. She has a list of \(n\) types of food to eat during the day (she may have up to one portion of each, per day). Each type of food has an amount of calories \(c_i\), and a degree of fullness \(s_i\) that it gives Karina when she eats it.

Her nutritionist has told her she can eat whatever she wants off that list, as long as she does not go over the allowed \(k\) calories.

Give an algorithm that uses dynamic programming to help Karina choose her meals for the day, so that she is as full as possible. You need only tell her how full she will be, you may return the actual meals if you want to. Give its asymptotic complexity, and prove its correctness.

Modelling the problem

When faced with a problem, it is often desirable to try to see if we can convert it to something we already know how to solve. It is also important to abstract away the useless information, and leave only the things required to solve the problem.

In this case, we have four important things: Two integers \(n\) and \(k\), and two lists of integers \(c_i\) and \(s_i\). From the problem description, we know that these are all nonnegative integers.

Initial solution

A trivial solution to the problem, would be to try absolutely every possible combination of food, check that it does not exceed \(k\) calories, and pick the combination with the highest fullness degree (the degree of fullness of a meal plan is the sum of the degrees of fullness of each food type in it). Clearly this solution must work. If there is a best meal plan, then it has to be within the combinations we try, it has to have less than \(k\) calories total, and we only keep the best one.

Certainly, this works. The pseudocode for that would go something like this:

best_fullness = 0
for combination in combinations(food_types):
  if calories(combination) <= k:
    best_fullness = max(best_fullness, fullness(combination))
return best_fullness

Here, I am using combinations as a function that, given a set, gives me its power set - that is, a list of all possible subsets of that set. It is easy to see that any meal plan, is a subset of all the possible food types, and viceversa.

Now, let’s analyze this algorithm. If we had a set of size \(n\), its power set has size \(2^n\). So in this algorithm, the loop runs for \(2^n\) iterations. The inner conditions call the calories function, and the fullness function, which we may bound by \(n\), since they’ll just sum a few numbers, less than \(n\) of them (remember that any meal plan has, at most, \(n\) food types). Taking the maximum of two integers is \(O(1)\) in the linear model.

In all, our algorithm is \(O(2^n \times n)\). Clearly, this is a pretty bad algorithm - it is exponential in \(n\).

Can we do better?

Noticing a pattern

In this solution, we are not really exploiting much of the structure of the problem. For instance, because of the way we check every subset, we sometimes check absurd options. If I already know I can’t have food types \(i_1\), \(i_2\), and \(i_3\), because \(c_{i_1} + c_{i_2} + c_{i_3} > k\), then I most certainly won’t be able to have food types \(i_1\), \(i_2\), \(i_3\), and \(i_4\) together!

We see here that this problem exhibits a property of “optimal substructure”. Meaning, parts of a good solution are necessarily the good solutions to a smaller problem. If we had a bad solution to a smaller problem, it can never be part of a good solution to the overall problem.

Re-read that paragraph, make sure you understand it.

Building a solution

How does this help us? Well, if you have a food type \(x\) that you want to eat, then the best you can do to maximize fullness while eating \(x\), is to eat \(k - c_x\) calories, while maximizing the fullness of the rest of your meal. Notice that this is the same problem we had - but now, instead of \(k\) calories, we have a smaller number, \(k - c_x\)! This helps us, because we know, by induction, how to calculate the best meal plan with \(k - c_x\) calories.

So the problem seems to be solved by this function:

\[f(food, k) = \max_{\stackrel{0 \le i < |food|}{c_i \le k}} \left\{s_{x_i} + f(food \setminus \{x_i\}, k - c_{x_i})\right\}\]

Of course, we need a base case. When we have no possible food types to eat, no matter how many calories we are allowed to use, the maximum fullness we can achieve is \(0\). So:

\[f(\emptyset, k) = 0\]

Great. Now we have a function that answers our problem. Please note that we haven’t actually written any code yet. We have simply said that, whatever the solution to the problem, will be the result of this function.

Writing the code

Now, you could write \(f\) in your language of choice, and it will surely work. But it’ll be slow. Very, very slow. Why will it be slow? Because you’re calculating the same things over and over. This function does not take that into account. If you call it twice with the same values, it will recurse through every element of \(foods\) again, even if you already calculated it. And in this particular problem, this is important - there are many times when you may be calculating the same food possibilities over and over.

Another thing you may notice, is that using sets is usually not too performant. We may assume, without loss of generality, that the foods are labeled \(0 \cdots n-1\). So we could turn the problem into:

“Using only the first \(i\) food types, and without going over \(k\) calories, what’s the best fullness we can achieve?”

This is a common way of walking through sets. It also allows us to exploit the optimal sub structure much better, as we will see in a second.

Now, what can we say about this new problem? It’s similar to the old one. In fact, the old one is just this same problem, with \(i = n\). This problem, however, we can rewrite as such:

\[f(i, k) = \begin{cases} 0, & \text{if } i = 0 \\ f(i-1, k), & \text{if } k < c_i \\ \max \{f(i-1, k), s_i + f(i-1, k - c_i)\}, & \text{otherwise} \end{cases} \]

Why is this? Because, as we had this “optimal substructure”, the best way to maximize fullness with the first \(i\) foods, is to either

Both of these questions I know the answer to - they’re just smaller instances of my original function.

This function is one you can code right away, and it’ll be faster than using sets. But if you run it, you’ll notice it’s still too slow. Why? Because we haven’t taken care of the repeated calls to the same function. Indeed, our function will call two instances of itself - each of these, might share subproblems with the other. But we’re not taking advantage of this, we’re recalculating it every time.

You may be wondering why I chose to turn the problem into one of the sort “… using the first \(i\) foods.” This is simply a matter of practice - with enough of it, you start to see that all dynamic programming exercises are the same. You always want to try to exploit the optimal substructure of the problem. For now, we’ll call it “magic”, but as you do more and more exercises in dynamic programming, you’ll see it’s really nothing too clever.

Now comes the part of doing this dynamic programming style.

Using dynamic programming: Top-bottom

The first technique I’ll show you is called “top-bottom” dynamic programming. It is the easiest of them, and requires the least amount of modifications to your code.

It’s nothing fancy. It is just introducing a cache to your function.

Specifically, our function has two parameters, \(i\) and \(j\). Their ranges are \(n\) and \(k\), respectively. So we create a table of dimensions \(n \times k\), filled with some value we know cannot be a result of our function. Since our function returns fullness, and this is never negative, -1 is a good choice.

So we create a table, say \(T\), of dimensions \(n \times k\), filled with -1.

Our function, when coded, looked like this:

def f(i, j):
  if i == 0: return 0
  if j < c[i]: return f(i-1, j)
  return max(f(i-1, j), s[i] + f(i-1, j - c[i]))

Now, we simply wrap a cache around it, like so:

def F(i, j):
  if cache[i][j] != -1: return cache[i][j]
  if i == 0: return 0
  if j < c[i]: return cache[i][j] = F(i-1, j)
  return cache[i][j] = max(F(i-1, j), s[i] + F(i-1, j - c[i]))

Notice that the function still looks remarkably like the original. But, the first time it calculates a particular \((i, j)\), it’ll cache it. Next time that same \((i, j)\) is asked, cache[i][j] will not be -1, but some value, and the function will return immediately.

Now, the asymptotic performance of this function is easy to analyze: Each time you call the function with \((i, j)\), you take some time. But you only take that time the first time you call the function with that input - next time, you will take \(O(1)\). Another way to see it is, you’re filling up entries in your cache. It takes you \(O(1)\) work to fill each one, and you won’t fill each one more than once.

So you can bound the runtime of this function, by \(O(n \times k)\).

Take some time to convince yourself that no matter how messy the recursion actually gets, since you’re only solving smaller instances of your problem, you’re never going in circles, and you’re going to fill at most \(n \times k\) entries in the cache.

Using dynamic programming: Bottom-up

The second technique is similar in concept to the first one, but more clearly shows that we’re just filling up a matrix. The idea is to take matters into our own hands, and do the calculations in a specific order. In the top-bottom case, the recursion itself handled the “dependencies”. However, we already know that we’ll be asking for the entries in this cache matrix in a given order - so why not use this information?

We know that, in order to solve the \(f(i, j)\), we will first need to solve \(f(i-1, j')\) for some \(j'\). So we can solve by rows: First, solve everything in row 0. Then, everything in row 1, and so on. This will be clearer in code:

matrix T[n][k+1] = {0}; // a matrix filled with 0s
for (i = 0; i < n; ++i) {
  for (j = 0; j <= k; ++j) {
    if(j < c[i]) T[i][j] = T[i-1][j];
    else T[i][j] = max(T[i-1][j], s[i] + T[i-1][j - c[i]]);
  }
}
return T[n-1][k];

If you look at the top-bottom version, you’ll see that it’s very similar. However, in this case, we calculate all of the possible \((i, j)\) pairs, since we know the order in which we’ll need them. In other words, we only use entries in the matrix which we have already solved before.

(It is clear to see, now, that the runtime is \(O(n \times k)\).)

This form of dynamic programming has some advantages, and some disadvantages. The main advantage is that you avoid the overhead of recursion. This type of loop is pretty “tight”, as in, it can be implemented efficiently in a processor (as an exercise, try to remove the conditional, for a faster execution).

However, you lose two key things:

  1. The code now looks different than the original, abstract function \(f\) which you had.
  2. You’re filling every entry in the matrix, even the ones you won’t need.

You’ll have to decide in each case which tradeoff you want.

Proof

Now, to prove that what we coded does really solve the problem we were asked to solve. Our dynamic programming was just fancy ways to optimize this function:

def f(i, j):
  if i == 0: return 0
  if j < c[i]: return f(i-1, j)
  return max(f(i-1, j), s[i] + f(i-1, j - c[i]))

It is easy to see that, if i == 0, then our function does give the correct answer, since the best possible fullness using no food is 0.

If j < c[i], it means we are trying to consume less calories than this food type (the ith one) provides. This is not possible if we consume it. So the best way to maximize fullness, using the first i food types and at most j calories, does not use the ith element, and so is equal to the best way to maximize fullness, using the first i-1 food types, and at most j calories. By induction, we assume our function can calculate this result, and so out function works for the case j < c[i].

We enter the last line if i isn’t 0, and if j is greater than or equal to c[i]. If we are presented with the choice to eat this food type or not, then the best way to maximize the fullness of the diet, using the first i food types, is to either eat this food type, in which case the solution lies in maximizing the fullness of using the first i-1 foods, using at most j - c[i] calories, and adding the fullness s[i], or we can not eat this, and try using the extra calories for the first i-1 food types. This is precisely what the max statement does. By induction, our function calculates the correct results for smaller values of i, and so our function is correct for all inputs in the range.

Conclusion

I hope this was useful. If you have any questions, you can shoot me an email and I’ll try to clarify them.

Happy coding!