Algorithms In Context #2: Dynamic Programming

This story is a direct sequel to my previous post on Greedy Algorithms, so you may want to check that out first. It is still okay if you are only interested in Dynamic Programming and want to skip it since I will be explaining the problem again.

When I was a university student, dynamic programming was the hardest topic in the Algorithms class for me. That was mainly because of being have to read long pages of redundant explanations prior to understanding the actual problem. That’s why in this post, instead of starting with a boring definition, I will directly jump into explaining the first problem of this section.

Knapsack Problem

Unlike the previous post, this time we talk about the 0–1 Knapsack Problem. Being part of the uprising movements against social injustice in government policies, you decided to gang up with some of your nerd friends in order to execute a bank job. Each gang member carries a bag with 50 kg capacity. Each of you hit the vault one by one and when it is finally your turn, you see that there is only one gold, one silver and one platinum bar left to take. You want to increase your gain as much as possible with your limited carrying capacity.

• The gold bar weighs 20 kg and worth 1000 dollars
• The silver bar weighs 30 kg and worth 1200 dollars
• The platinum bar weighs 10 kg and worth 600 dollars

If you calculate the price per kg for each bar, you will see that platinum is the most expensive, then gold, and finally silver is the cheapest. The greedy strategy in the previous post (fractional knapsack problem) tells you to always take the most profitable one per kg first. If you try applying the same strategy in this case, you will end up taking the platinum and gold bar, a total of 1600 dollars.

If you would have taken the gold and silver bars instead, you would have ended up with 2200 dollars, as you can see in the image above. So, the same greedy strategy that worked on the fractional knapsack problem did not give you the optimal solution for the 0–1 knapsack problem.

This is happening because in the fractional case you were able to take as much as possible of each item to fill your bag. So your answer is only depending on a single parameter: money. But in the 0–1 case you have to decide whether to take it or leave for each item and compare the results of each possible permutation in order to find the most profitable one.

You do this through recursion. But before we continue, let’s first consider a much simpler recursive algorithm.

Fibonacci Series

Ugh, this again… In high school, I remember being very impressed with the golden-ratio theories of Ancient Greece. After 10 years into computer science and now I look down on Fibonacci Series. Nevertheless, it is quite useful when you want to talk about recursion. Here is the formula:

Fibonacci series is implemented with a simple recursive function:

unsigned int fibonacci(unsigned int n) {
    if (n < 2) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Easy… This short function solves the Fibonacci series but there is a problem with this approach. Can you spot it? Go ahead and think for a while.

Did you find it? Good. If you couldn’t, do not worry. I’m sure you know the answer on some unconscious level: It is the recurring calculations. You calculate the result of the same subproblem over and over again, ending up with an exponential-time algorithm that makes me shiver to my bones when I consider larger inputs.

But why would you that? Why would you want to calculate the same result over and over and over again? I mean, that’s just plain stupid. Instead, why not store the result for fibonacci(x) and just use that value when you need it again? Now slap your face and scream dynamic programming!

We will apply this strategy to our code and store the results in an array. You can use any data structure depending on your needs. This technique is called memoization - why they didn’t just call memorization will forever haunt me.

You can approach the overlapping subproblems from two sides: top-down or bottom-up. Here it the algorithm for the top-down approach:

// Note: Size is n + 1 because we store the values from 0 to n
unsigned int lookup[n + 1] = {0};
unsigned int fibonacci(unsigned int n) {
    if (n < 2) {
        return n;
    } else if (lookup[n] != 0) {
        return lookup[n];
    }
    lookup[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return lookup[n];
}

All we have changed in the code was to introduce the lookup array and return the stored value if one such exists. Next, we see the bottom-up approach that turns the algorithm into an iterative function.

unsigned int fibonacci(unsigned int n) {
    unsigned int lookup[n + 1] = {0};
    lookup[0] = 0;
    lookup[1] = 1;
    for (unsigned int i = 2; i <= n; i++) {
        lookup[i] = lookup[i - 1] + lookup[i - 2];
    }
    return lookup[i];
}

Which method you will use is entirely up to you but the bottom-up approach generally performs better since there are no additional function calls. The top-down approach can be preferable if you don’t need to calculate the result for every single index in the array or your storage of preference. But if you need to calculate each one like in this example, I would go with the bottom-up approach. In any case, dynamic programming greatly increases the performance of the algorithm.

Now let’s turn our attention back on the Knapsack Problem. We already saw that we need to go through all possibilities to find the optimum solution. Just like in Fibonacci series, we will use a divide and conquer method by recursively solving the problem for smaller bag sizes.

The recursive algorithm for the 0–1 knapsack problem is a little bit more complicated, so let me elaborate first. The function has 3 parameters:

• vector<Item> items: The list of items waiting to be taken
• int size: Remaining size (weight) of the bag
• int index: Index of the last processed Item in items

We will process each item on the list one by one. For each item to be processed there are two possible cases: Either we take it or leave it behind. This means that there will be two recursive calls for each item representing whether or not we are taking it.

• If we take the item, we need to subtract its weight from the remaining capacity of the bag and add its price to our final profit.
• If we don’t take it, we will move on to the next item without any changes to the remaining capacity or profit.

There is also an extra case where we cannot steal the item since it is heavier than the remaining bag capacity. Finally, the algorithm stops either when

• There is no more capacity left in the bag
• All items are already processed

The final C++ code is something like this:

int knapsack(vector<Item> items, int size, int index) {
    // Base case: either bag is full or we tried all items
    if (size == 0 || index == items.size()) {
        return 0;
    }
    // Current item weighs more than the remaining bag size
    Item current = items[index];    
    if (current.weight > size) {
        return knapsack(items, size, index + 1);
    }
    int weight = current.weight;
    int price = current.price;
    // a is the price when current item is taken
    // b is when it is not taken
    int a = price + knapsack(items, size - weight, index + 1);
    int b = knapsack(items, weight, index + 1);
    return max(a, b);
}

It might be a little hard to read this recursion at first. If you are having a hard time understanding, just write it down and it will be clear.

Now, this is just a recursive solution and it makes recurring calculations just like our Fibonacci function once did. In order to avoid that, we need to store the already calculated results in a 2D array.

The most complicated part of this algorithm is how to store the results. An element lookupTable[i][j] corresponds to the result for the first i items processed for a bag with j kg capacity. You are going to read this sentence multiple times.

We can use the top-down recursive or bottom-up iterative approach. Remember when I said to use the top-down approach when you don’t really need to calculate every single case? It seems appropriate for this problem.

// Note: This is not valid in C++ but you got the point
int lookupTable[count + 1][size + 1] = {-1};
int knapsack(vector<Item> items, int size, int index) {
    // Base case: either bag is full or we tried all items
    if (size == 0 ||index == items.size()) {
        return 0;
    }
    // Result already calculated
    if (lookupTable[index][size] != -1) {
        return lookupTable[index][size];
    }
    // Current item weighs more than the remaining bag size
    Item current = items[index];    
    if (current.weight > size) {
        lookupTable[index][size] = knapsack(items, size, index + 1);
        return lookupTable[index][size];    
    }
    int weight = current.weight;
    int price = current.price;
    // a is the price when current item is taken
    // b is when it is not taken
    int a = price + knapsack(items, size - weight, index + 1);
    int b = knapsack(items, weight, index + 1);
    
    lookupTable[index][size] = max(a, b);    
    return lookupTable[index][size];
}

The only thing that’s different from the recursive solution is the part we store the calculated values in a 2D array and simply return it if one such exists. For any DP problem, I strongly advise you to write the recursive algorithm first and then the memoization step should be easy.

That’s it. I know this one is a little bit complicated but just try to understand the idea behind it and you will be doing okay.

Oh, wait! I forgot to define what dynamic programming is. Dynamic programming is a technique that allows you to divide your problem into smaller subproblems and store the result of the subproblems in order to be able to use them at recurring calculations.

It is not helpful at this point, huh? Well then, see you in the next part…