Transforming a bounded knapsack to 0/1 knapsack

Question

Could I transform a bounded-knapsack problem into a 0/1 knapsack problem using the following way-:

Example: Lets says I have 3 types of items

$n=3$

$p_j=\{10,15,11\}$

$w_j=\{1,3,5\}$

$b_j=\{6,4,2\}$

$c = 10$

Here $n$ denotes the number of types of items, $p_j$ denotes the profit gained by including 1 item of a that particular type, $b_j$ denotes how many items of a particular are available. And $c$ denotes the total capacity of the knapsack.

So for each item of a particular type I transform the item by including all the various ways of adding it, so for the first item, since there are 6 of them I include in my transformed array all 6 ways of taking them ie. $(1,1*p_j),(2,2*p_j)..$ and so on. Example, the expansion of the first item would be:

$(1,10),(2,20),(3,30)...(6,60)$

So now the expanded array would contain $6+4+2=12$ elements.

Now if I use that against the standard dynamic programming approach for 0/1 knapsack problem would I be able to get the optimal solution ?

This text(page 3) introduces an algorithm that converts a bounded knapsack to 0/1 knapsack by adding $\sum_{j=1}^n \lceil log_2(b_j + 1) \rceil$ terms for each item. I am just wondering why that even works ?

An extract from the text reads the following:

Notice that the transformations introduces $2^q$ binary combinations.

Can someone tell me how that works ? And if the above described way actually can lead to the optimal solution.

Answer 1

The approach you described does not work necessarily.

If you have the following situation (I made it simpler)

          | Profit | Weight | Total |
Object 1  |   5    |   3    |   3   |
Object 2  |   2    |   6    |   2   |

If you transform the problem according to your proposal we get the following situation

            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |   10   |   6    |
Object 1.3  |   15   |   9    |
Object 2.1  |    2   |   6    |
Object 2.2  |    4   |  12    |

If the capacity of the knapsack here is $15$ the 0-1 knapsack algorithm will give you an invalid optimal answer. Taking object 1.2 and object 1.3 with profit $25$ and weight $15$, but this items are supposed to be exclusive (if you take 2 items of element 1 you can't take 3 also).

So another approach to transform it in a 0-1 knapsack is by creating a new item per instance.

            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |    5   |   3    |
Object 1.3  |    5   |   3    |
Object 2.1  |    2   |   6    |
Object 2.2  |    2   |   6    |

The solution of this problem is equivalent to the original problem, but this don't scale very well, because if you have up to $10^9$ (or more) instance of an object, you need to create one item per instance.

Why this model works? and how can we improve it? This model works because we split each object in several group of items (each group of size 1)and it allows us to combine them in order to get any number of objects up to the maximum. For example, if one object appear 7 times we split it in $(1,1,1,1,1,1,1)$ and if we want in the optimal solution only $3$ of them, then we pick any subset of size $3$ of this set.

But we can split them in other ways, keeping the condition that we can take a subset that sums whatever sum we want up to the maximum. For example you can split $10$ like $(1, 2, 3, 4)$, and this partition is useful since you can get any sum up to $10$. There is a canonical way to split a number in $log_2(n)$ numbers that has this property. Split the number in power of 2 starting from $1, 2, ...$ until you can't split it anymore, and add the remainder to the partition too.

For example:

5 -> (1, 2, 2)
10 -> (1, 2, 4, 3)
15 -> (1, 2, 4, 8)
1000 -> (1, 2, 4, 8, 16, 32, 64, 128, 256, 489)

Then if your original problem looks like this

          | Profit | Weight | Total |
Object 1  |   5    |   3    |   7   |
Object 2  |   2    |   6    |   17  |

We split $7=1+2+4$ and $17=1+2+4+8+2$ You transform it into this equivalent 0-1 knapsack problem

            | Profit | Weight |
Object 1.1  |   5    |   3    |
Object 1.2  |  10    |   6    |
Object 1.3  |  20    |  12    |
Object 2.1  |   2    |   6    |
Object 2.2  |   4    |  12    |
Object 2.3  |   8    |  24    |
Object 2.4  |  16    |  48    |
Object 2.5  |   4    |  12    |

The optimal answer here gives you a straight forward way to recover the original answer, and the amount of new elements you create for each different item is at most $O(log(frequency))$, where $freq$ is the instance you have of some particular object.