1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi Marcelo, great explanation, but can you give a little more information as to why breaking a number into $log_2(n)$ parts is considered canon. If there is a formal name in mathematics to this solution you can link that too, so I can study it for my self. $\endgroup$ – ng.newbie Jan 11 '18 at 5:04
  • $\begingroup$ Also when you are splitting the value according to $log_2(n)$ how are you splitting the weight? Are you using the same principle for the weight? Please add the info on how the weight is split. $\endgroup$ – ng.newbie Jan 11 '18 at 5:13
  • $\begingroup$ Forget it, I just understood how you broke the weight. But is this the only way to solve the bounded knapsack problem ? $\endgroup$ – ng.newbie Jan 11 '18 at 6:45
  • $\begingroup$ @ng.newbie I believe it is not the only way to solve the bounded knapsack problem, it has been deeply studied and there are a lot of heuristics (many of them pseudo polynomial, i.e. polynomial in the number of items and the capacity), I just try to explain the $log$ technique to solve the problem. $\endgroup$ – Marcelo Fornet Jan 11 '18 at 16:31
  • $\begingroup$ When you make a new item group with $n$ old items you need to multiply both the profit and the weight of the original item times $n$ to really model what is happening if you take that item. $\endgroup$ – Marcelo Fornet Jan 11 '18 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.