Maximum Value

Recently I have been getting a lot of visits (well what I consider a lot) to this blog because of the Knapsack Problem. Since this seems to be so popular, and people don’t want to go to Wikipedia, I suppose I will dedicate at least one post to the topic.

Problem Statememtn

Suppose that you have a collection of objects $a_1, a_2,\cdots, a_n$ , with respective weights $w_1, w_2,\cdots, w_n$ and value $v_1, v_2,\cdots, v_n$ . Your task is to find a subset of these items with maximum value. However, this is one condition, the items you choose must be able to fit in a bag that can only carry a maximum weight of $W$ before breaking.

For those of you that are more mathematically inclined, and want to see the short version of the problem, here it is;

$(1)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }x_i\in\{0,1\}$

Where $x_i=1$ means that you choose to take object $a_i$ , and $x_i=0$ means that you do not.

Solutions

I will present two different approaches to solving this problem. Both these approaches can be applied to a wide range of problems, so the reasoning behind the algorithms is more important than the particular cases that follow.
In the solutions it is assumed that $x\in\mathbb R^n$ , and $0\le x\le 1$ means that $0\le x_i\le 1$ for $i=1, 2,\cdots, n$ .

Branch and Bound

In this approach, instead of solving the problem as it is presented in $(1)$ we consider the relaxation

$(2)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }0\le x\le 1$ .

You should notice that any feasible solution (one that satisfies the constraints) to $(1)$ is also a feasible solution to $(2)$ . The reason we consider the relaxation is because there might be a way to quickly obtain an answer.

So suppose that we find $x^*$ to be the optimal solution to $(2)$ . If it turns out that $x^*_i\in\{0,1\}$ we also have that $x^*$ is optimal for $(1)$ . Well this is not interesting at all, so without loss of generality suppose that $x^*_1\notin\{0,1\}$ . So even though $x^*$ is optimal for $(2)$ it is not feasible for $(1)$ . To fix this small oversight we split $(2)$ into two subcases:

$(2.1)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }0\le x\le 1\mbox{ and }x_1=0$

and

$(2.2)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }0\le x\le 1\mbox{ and }x_1=1$

Now the optimal value of each of these problems will have $x^*_1\in\{0,1\}$ . Furthermore, if we let $V, V_1, V_2$ be the optimal values of $(2), (2.1),\mbox{ and }(2.2)$ it is clear that $V_1\le V$ and $V_2\le V.$ Now suppose we have found $x(1)$ to be the optimal solution to $(2.1)$ and $x(2)$ for $(2.2)$ , and $V_1 > V_2$ .

If $x(1)$ satisfies the constraints of $(1)$ then we are finished. If not, we then split $(2.1)$ into two problems, similar to how we split $(2)$ into two problems. Now these problems give optimal values $V'_1, V'_2$ . We then see which of $V_2, V'_1,\mbox{ and }V'_2$ is largest, and check to make sure that its optimal point satisfies the constraints of $(1)$ . If it does not, we just split it into two problems, solve those problems, and compare our list of optimal values and points.

I’ll leave it to you to show that this process will not only terminate, but also find the optimal solution to $(1)$ .

The reason for the Branch in the name of this approach is obvious. If our optimal solution to is not feasible for $(1)$ we split (branch) it into two subproblems.
To see the reason for Bound is as follows. Suppose that we perform the process and have a set of optimal values $V_1<V_2<\cdots<V_n$ and optimal points $x(1), x(2),\cdots, x(n)$ . Then the solution to $(1)$ has optimal value of at most $V_n$ . However, if we must split because $x(n)$ does not satisfy the necessary constraints, then the optimal values from the subproblems will be at most $V_n$ . So we therefore have a bound on the possible optimal value.

The Branch and Bound approach rest on the assumption that you are able to solve the relaxed problem. Usually it is assumed that solving the relaxed problem is not only possible, but can be done rather quickly.

Dynamic Programming

I won’t go into too much (if any) detail about what dynamic programming is. However, I will say this; the main idea is that the optimal solution for $P(n+1)$ can be built from the optimal solution for $P(n)$ , kind of like induction if you think about it.

In our case we will let $P(i,j)$ be the maximum value we can achieve by only using objects $x_1,\cdots, x_i$ and with maximum weight of $j$ . Thus our desired answer is $P(n,W)$ .

For the sake of simplicity we will define $P(0,j):=0$ for all $j$ . Now how do we determine the value of $P(i,j)?$ Well there are two cases

Case 1: $w_i>j$
In this case it is not possible to add object $a_i$ without exceeding out weight constraint. Thus $P(i,j)=P(i-1,j)$ .

Case 2: $w_i\le j$
In this case we have two choices. We can either take object $a_i$ or we can leave it behind.
If we leave it behind then $P(i,j)=P(i-1,j).$
However, if we choose to take it we must remember that the total weight is equal to $j$ . Therefore, if object $a_i$ is taken we have that $P(i,j)=v_i+P(i-1,j-w_i).$

In this case $P(i,j)=\max\{P(i-1,j),v_i+P(i-1,j-w_i)\}.$

Conclusion

As you can see, the dynamic programming solution is easier to program, but I feel that it is also nice to know the branch and bound approach. After reading the above solutions you should be able to quite easily create your own code. For the dynamic programming approach I suggest using arrays since recursion can be quite expensive. As for the branch and bound solution, I suggest using some sort of heap in order to store the information about the subproblems that you will create.

Other Forms

Here are some other problems that can be though of as variants of the Knapsack problem, even though at first glance they might not appear to be. All of these problems can be solve by adjusting the above solutions to the original Knapsack problem. Although the above solutions might work, they might not be the most efficient.