# 0/1 Knapsack Problem or: How I Learned to Stop Coding and Rob a House

Ahoy!

It’s been over a week since I posted about another dynamic programming problem. I thought I would be posting more on winter break. Sorry about that.

I have usually written about everyday problems in this blog. Again, I will teach you a very useful, daily life application of computer science: efficient stealing.

Here we go:

Suppose you are a thief and you planned to enter a house. You know that there are only four valuable items in the house that weigh 1, 3, 4, 5 kilograms and cost 1000, 2000, 4000 and 4500 dollars, respectively. You are a very sloppy thief, i.e., you did not plan things ahead, so you brought a knapsack with a capacity of only 7 kilograms. What is the maximum total value of goods that you can steal? (the vase is probably from Beymen lol)

In the above example, you can easily see that the wisest decision would be stealing 6000\$ worth of goods. In some houses though, there will be thousands of objects with very small weights or you will have a bigger knapsack so it will definitely be harder to decide. It’s easier to find the optimum solution with a clever algorithm rather than trying every combination and calculating the values each time.

### In this case, our clever algorithm will be dynamic programming.

Remember that the dynamic programming approach is all about dividing the problem into subproblems. As in the stair-climbing problem, we do not jump directly into the problem of fitting the combination of the items with the maximum total value. Instead, we check for capacities less than 7, store the maximum total value up to that capacity and increase the capacity one by one.

Let’s see this on a table: I inserted the items in non decreasing order and filled the “zeroth” column (I will implement this with arrays, that’s why there is a zeroth column) with all zeros since we cannot fit anything to the knapsack if it has zero capacity. Then, we start with only the first item with weight 1 (camera) and we increase the capacity of the knapsack one by one. For each capacity, the best (by best, I mean the maximum total value) we can do with that item is to include that item if it fits. It seems that weight 1 fits to every capacity greater than or equal to 1, so we fill the table according to that: (the max total value we can get with the camera only)

Then, we consider the second item with weight 3 (laptop) together with the camera. If the capacity of the knapsack is 1 or 2, we can only fit the camera to the knapsack. If the capacity of the knapsack is 3, we can either put the camera or the laptop. We compare their values (we go one row up) and laptop turns out to cost more than the camera, so we choose the laptop. Here comes the trick for capacities bigger than 3 kg: we check for the maximum total value of the goods before adding 3 and add 3 on that value. If we are on column 4, for example, we go up and go 3 columns back and add the value of the laptop to that. If this value we have is bigger than the value when we go one row up, we write that value to that cell.

I know my attempt to explain the algorithm is very confusing, but I am sure that you will understand what I am trying to say: we can fit the item with weight 1 only we choose laptop over camera we check for the maximum before adding the item with weight 3, then choose to add it or not

Next, we include the items with weights 1, 3 and 4. For the capacities less than 4, the best we can do is what we can do without including the item with weight 4 (necklace). Instead of recalculating these, we directly go up one row and write the maximum total values with just including the camera and the laptop. Then, for the capacities greater than or equal to 4, we either do not include item with weight 4 to the solution (go 1 row up and write the value 3000) or we go 4 back, one up, add necklace’s value to that value. For example, for the capacity of 4, we check for maximum total value with capacity of zero and add 4000 to it or we directly write 3000. Since 4000 is greater than 3000, we choose to write 4000. (here, blue arrow means directly including the value above. orange arrow means adding 4000 to the value that the arrow comes from)

For the final row, we apply the same steps: Note that in the last row, we chose to include the value above the 5th column instead of including the one where we go 1 up and 5 back since 5000 is bigger than 0 + 4500 = 4500. Same goes for the 7th column: we chose 6000 over 1000 + 4500 = 5500. The value we want to find is the value on bottom right!

From this table, we can also see that, for example, the maximum value of goods we can steal when we have a knapsack with capacity 6 is 5500, with 5 is 5000, with 4 is 4000, and so on.

~~~~END OF TORTURE~~~~

Now, you may think implementation of this algorithm takes a loooooong time. Well, you will be surprised. All of the text above comes down to this formula:

``````
i = current row/item, j = current column/capacity
if(i == 0 || j == 0)
TABLE[i][j] = 0
else if (j < (i-1).weight)
TABLE[i][j] = TABLE[i-1][j]
else
TABLE[i][j] = max(TABLE[i-1][j], (i-1).value + TABLE[i-1][j-(i-1).weight])
``````

(For all j, TABLE[j] = 0 in the above formula. I did this in order not to manually fill in the first row. That’s also why I am looking for weights and values of i-1 instead of i. I did not show this on the tables, sorry about that.)

TL;DR What we do here is for the capacities less than the weight, we check for the maximum total value we found before, without including that weight. If the capacity is greater than or equal to the weight, we either do not include the weight and directly write the maximum total value we found before that fits that capacity or we include that weight and check for the maximum value subtracting that weight from the capacity and check for the maximum value at that capacity without including that weight.

Easy, right?

Well, maybe it will be easier if you also see a full implementation (in C++ this time):

``````
#include <iostream>
#include <utility>
using namespace std;

int capacity; int numOfItems;

//returns the max value of two integers
int max(int a, int b) { return (a > b) ? a : b; }

int knapsack_01(pair<int, int>* items){
int TABLE[numOfItems+1][capacity+1]; //construct the table

for(int i=0; i<numOfItems+1; i++){
for(int j=0; j<capacity+1; j++){
if(i == 0 || j == 0)
//fill TABLE[j]s and TABLE[i]s with 0s
TABLE[i][j] = 0;
else if (j < items[i-1].second)
TABLE[i][j] = TABLE[i-1][j];
else
TABLE[i][j] = max(TABLE[i-1][j], items[i-1].first + TABLE[i-1][j-items[i-1].second]);
}
}
return TABLE[numOfItems][capacity];
}

int main(){
capacity = 7;
numOfItems = 4;

//a pair holds one item
//items[item].first = value of item, items[item].second = weight of item

pair<int, int> items [numOfItems] = {make_pair(1000, 1), make_pair(2000, 3), make_pair(4000, 4), make_pair(4500, 5)};//array of pairs (items)

cout << knapsack_01(items) << endl;
}

``````

Aaand that’s pretty much it. If you have a computer with you while stealing (…or you can steal one from the house), you can copy and paste the code above to a C++ shell and see the result. You can always change the capacity and the items. (formal attire is not required)

(If you get caught in the act, you don’t know me and you didn’t read this post.)

Advertisements

# Stairs Climbing Puzzle (Dynamic Programming) (Done with finals!!!)

Yello,

Today, I will introduce you a very efficient algorithm called dynamic programming.

### “Why didn’t they give it a boring name like Kruskal’s Algorithm, for example? (no offense)”

The term dynamic programming was originally used by Bellman in 1940. He says he chose the word dynamic because the output characteristics of the solution depend upon time… and simply because it sounds cool. The word programming refers to the use of the method to find an optimal program.

Let’s see the problem first before actually talking about the algorithm (one of the easiest problems):

Suppose you are climbing up a staircase with a friend. Your friend is talking about how much he likes his pet goldfish for the fifth time that day. You do not want to hear that story again, so you want to keep your mind busy with counting how many possible ways you can jump up the stairs if you can just hop 1 or 2 step(s) at a time (you know how many steps the staircase has).

Here are some examples:

Do you see a pattern here? (Hint: It’s a very famous sequence).

The answer is…

(♫♫ drum roll ♫♫)

FIBONACCI SEQUENCE!

#### So, how does it work?

For n = 0, there is only one way to climb the staircase (which is no way). For n = 1, you could do only one hop of one. For n = 2, you can either directly hop two steps or you can jump from first step to second step with a single hop of one. For n = 3, you first have to reach step 1 somehow and add a hop of 2 steps or you first reach step 2 somehow and add a hop of 1 step. For n = 4, either you reach step 3 and add a hop of one or you reach step 2 and add a hop of two. Note that I did not include reaching step 2 and adding two hops of one since it is already included in reaching step 3 and adding one more step (think about it).

(F(n) is the number of ways to reach the nth step).

We can define our solution recursively from now on: The sequence is exactly the same as Fibonacci except that F(0) = 1 and F(1) = 1 are the base cases here whereas in Fibonacci, F(0)=0 and F(1)=1 are the base cases.

Speaking of implementation, let’s implement this in Java (because I miss coding in Java 😦 )

```public class StaircaseProblem {

public long numOfWays(int numOfSteps) {
if(numOfSteps == 1 || numOfSteps == 0)
return 1;
return numOfWays(numOfSteps-2) + numOfWays(numOfSteps-1);
}

public static void main(String[] args) {
StaircaseProblem sp = new StaircaseProblem();
int steps = 5;
System.out.println(sp.numOfWays(steps));
}

}```

This simple, naive recursive program gives an output of 8, as it was supposed to do. However, suppose you are climbing to a staircase of 100 steps. …or Risshakuji Temple in Japan (good luck with your boring friend lol)

If you try this program with numOfSteps = 100, then your program will take strangely long to run.

Why? I said we need to calculate F(4) and F(3) in order to calculate F(5). In order to calculate F(4) we need to calculate F(3) and F(2), and to calculate F(3), we need to calculate F(2) and F(1). Calculating F(4) and F(3) have nothing to do with each other, so we calculate F(3) once for F(4) and once for F(3) itself.

Imagine how many multiple calculations occur in n steps: a tree for showing the number of calculations (n=6)

If there was just a way to calculate each subproblem only once…

But wait! There is one!

This is where dynamic programming comes in. In dynamic programming, we compute a subproblem the first time we encounter it. The key is to store the solutions. The next time the subproblem occurs, instead of recomputing its solution, we simply look up the previously computed solution. Instead of time, we use space for storage. The technique of storing solutions instead of recomputing them is called memoization (no it’s not a typo, WordPress, stop underlining it). eliminating a certain number of calculations using dynamic programming
```
import java.util.Arrays;
public class StaircaseProblem {

static long[] memoization; //new line of code
public long numOfWays(int numOfSteps) {
if(numOfSteps == 1 || numOfSteps == 0)
return 1;
//start of new lines of code
if (memoization[numOfSteps] != -1)
return memoization[numOfSteps];

long currentResult = numOfWays(numOfSteps-2) + numOfWays(numOfSteps-1);
memoization[numOfSteps] = currentResult;
return currentResult;
//end of new lines of code
}

public static void main(String[] args) {
StaircaseProblem sp = new StaircaseProblem();
int steps = 5;

memoization = new long[steps+1]; //new line of code
Arrays.fill(memoization, -1); //new line of code

System.out.println(sp.numOfWays(steps));
}

}
```
``````

The two codes I wrote are basically the same lines of code except some few modifications about storage. However, it had a huge effect on the run time. For n = 100, the dynamic code took between 200000 ns to 300000 ns each time (about 0.25 milliseconds in average) whereas I waited for more than 5 minutes for the naive code to run before terminating!

What if you could hop 1, 2 or 3 steps at a time? You would simply modify the formula as F(n) = F(n-1) + F(n-2) + F(n-3), since you can also start with hopping 3 steps at the same time now.

I guess I will be writing about dynamic programming from time to time since I think it is a very cool algorithm. It makes you use a mathematical approach to any problem in real life, and after finding a pattern and the formula for the problem, it is quite easy to implement.

Hope you enjoyed my first blog post with (serious) source code!