Quoting the problem statement from Petr's blog:

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

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

*"The bounded knapsack problem is: you are given n types of items, you have u*_{i}items of i^{th}type, and each item of i^{th}type weighs w_{i}and costs c_{i}. 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.

**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 u_{i}items of the i^{th}type, each of which represents a different item having the same w_{i}& c_{i}as the item of the i^{th}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)***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 i^{th}item type, weighing w_{i}and costing c_{i}. 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 combined Weight Cost 1 1*w _{i}1*c _{i}2 2*w _{i}2*c _{i}4 4*w _{i}4*c _{i}8 8*w _{i}8*c _{i}6 6*w _{i}6*c _{i}

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))*.**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)

Weight 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Item (k-1) 0 5 5 7 15 15 19 20 21 23 30 33 42 42 49 51

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 DP_{k, w}, we consider the possibility of including either 0, 1, 2, 3, 4, ..., u_{i}items of the i^{th}type to the previous best solution including all items from 1 .. (k-1). This gives us the following recurrence:

DP_{k, w}= max (

DP_{(k-1), w},

DP_{(k-1), w-1*wk}+ 1*c_{k},

DP_{(k-1), w-2*wk}+ 2*c_{k},

DP_{(k-1), w-3*wk}+ 3*c_{k},

...,

DP_{(k-1), w-ui*wk}+ u_{i}*c_{k})

An interesting observation here would be that we only deal with every w_{k}^{th}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**instead**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 DP_{k, 12}is represented by taking the maximum of the cells colored in green below.

Weight 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Item (k-1) 0 5 5 7 15 15 19 20 21 23 30 33 42 42 49 51 36 34 37 32 42

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 w_{k}^{th}element from the previous best solution and adding some multiple of c_{k}to it.

We also notice that it doesn't matter what values we add to DP_{(k-1), w}(for the k^{th}item) as long as they are c_{k}apart. Hence, if the weight of the knapsack is*W*and the weight of the k^{th}item is w_{k}, we can add the following to every w_{k}^{th}element in the previous array.

Column to which value is added Value Added 0 (W/w _{k})*c_{k}1*w _{k}(W/w _{k}- 1)*c_{k}2*w _{k}(W/w _{k}- 2)*c_{k}3*w _{k}(W/w _{k}- 3)*c_{k}

If we now reintroduce the requirement that each item type will have only a*bounded*or fixed number of instances (i.e. u_{k}is bounded), then the problem reduces to finding the maximum value in every window of size u_{k}in the array we just computed. This can easily be done by pre-processing the array to maintain the largest element in every window of size u_{k}.

However, the actual value of the cost at any cell needs to be computed by adding back any differential that we may have subtracted to ensure that every entry is c_{k}apart and that the first entry is the one which has the maximum multiple of c_{k}subtracted from it. For the j^{th}array element in the current sub-array we are processing, this value will be (W/w_{k}- j)*c_{k}(since we have subtracted that much*extra*from those elements, we must now add it back).

Hence, we can safely say that we shall have w_{k}different sub-problems that we shall try to solve assuming that we can use a single computation for every w_{k}^{th}element.

This allows us to find the value at every cell of the (k x W) matrix is amortized time O(1) (we have amortized the cost of pre-computing the w_{k}arrays across all the element accesses). This makes the total running time of this algorithm*O(W * n)*.

## No comments:

Post a Comment