## Tuesday, September 20, 2011

### The Integer (0/1) Bounded Knapsack Problem

Quoting the problem statement from Petr's blog:

"The bounded knapsack problem is: you are given n types of items, you have ui items of ith type, and each item of ith type weighs wi and costs ci. What is the maximal cost you can get by picking some items weighing at most W in total?"

Here, we assume that the knapsack can hold a weight at most W.

We shall describe 3 solutions to this problem, each of which reduces the complexity of the solution by a certain amount.

1. O(W*n*M): The first solution is the standard knapsack solution solution, which just involves copying each item instance of every item type to get a total of ui items of the ith type, each of which represents a different item having the same wi & ci as the item of the ith type.

It is easy to see that if we have a mean of M number of items of each type, the complexity of this solution is O(W * n * M)
2. O(W*n*log(M)): The second solution involves rewriting items such that we have a fewer number of items of each type to work with. We shall then solve the transformed problem using the same technique as the standard knapsack problem (as in the solution above).

Suppose we have 21 instance of the ith item type, weighing wi and costing ci. We observe that 21 can be rewritten (using powers of 2) as:
21 = 1 + 2 + 4 + 8 + 6

We basically add powers of 2 till we exceed the sum we want to create (21 in this case). When we exceed the sum, we just add the difference (6 in this case) between the number (21 in this case) and the current sum we have (15 in this case = 1+2+4+8).

Now, the new items are created by combining 1, 2, 4, 8, and 6 items of the original instances. These newly created items will have the following weights and costs:

Number of items of the original type combinedWeightCost
11*wi1*ci
22*wi2*ci
44*wi4*ci
88*wi8*ci
66*wi6*ci

Hence, we have effectively reduced the number of items from 21 to 5. In general, we replace the M in the solution above with log(M) to get a final complexity of O(W * n * log(M)).
3. O(W*n): The third and most efficient solution to this problem is the one that took me almost 3 days to figure out and understand. The short post on petr's blog actually contains all the information needed to understand it, but I'm not that comfortable reading terse explanations; especially when it's a new idea, so here is something more verbose.

There is also a paper and a section in a book dedicate to this problem, but I find them quite hard as well.

Let's assume that this row (in the DP table of Items (rows) v/s Weight (columns)) represents the best configuration (maximum cost) for the knapsack at every weight 0 .. W that includes all item types from 1 .. (k-1)

Weight0123456789101112131415
Item (k-1)0557151519202123303342424951

So, the basic observation is that DP(k-1), w represents the best solution including all items from 1 .. (k-1) (both inclusive) with a knapsack of weight (w).

To compute DPk, w, we consider the possibility of including either 0, 1, 2, 3, 4, ..., ui items of the ith type to the previous best solution including all items from 1 .. (k-1). This gives us the following recurrence:

DPk, w = max (
DP(k-1), w,
DP(k-1), w-1*wk + 1*ck,
DP(k-1), w-2*wk + 2*ck,
DP(k-1), w-3*wk + 3*ck,
...,
DP(k-1), w-ui*wk + ui*ck)

An interesting observation here would be that we only deal with every wkth element from the previous array to decide on any element in the current array.

Let us for a minute ignore the fact that we have only a fixed number of items of each type and assume that we have an infinite number of items of each type. Let us assume that item i weighs 3 and costs 9. If we make that assumption, we see that the best solution at DPk, 12 is represented by taking the maximum of the cells colored in green below.

Weight0123456789101112131415
Item (k-1)0557151519202123303342424951
3634373242

What we have essentially done is added:
0*9 to DP(k-1), 12
1*9 to DP(k-1), 9
2*9 to DP(k-1), 6
3*9 to DP(k-1), 3 and
4*9 to DP(k-1), 0

The problem has reduced to finding the maximum value among all the values of the array that is formed by picking every wkth element from the previous best solution and adding some multiple of ck to it.

We also notice that it doesn't matter what values we add to DP(k-1), w (for the kth item) as long as they are ck apart. Hence, if the weight of the knapsack is W and the weight of the kth item is wk, we can add the following to every wkth element in the previous array.