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.