Converting a bounded knapsack problem to 0/1 knapsack problem
- by Ants
I ran across a problem where goal was to use dynamic programming (instead of other approaches). There is a distance to be spanned, and a set of cables of different lengths. What is the minimum number of cables needed to span the distance exactly?
To me this looked like a knapsack problem, but since there could be multiples of a particular length, it was a bounded knapsack problem, rather than a 0/1 knapsack problem. (Treat the value of each item to be its weight.) Taking the naive approach (and not caring about the expansion of the search space), the method I used to convert the bounded knapsack problem into a 0/1 knapsack problem, was simply break up the multiples into singles and apply the well-known dynamic programming algorithm. Unfortunately, this leads to sub-optimal results.
For example, given cables:
1 x 10ft,
1 x 7ft,
1 x 6ft,
5 x 3ft,
6 x 2ft,
7 x 1ft
If the target span is 13ft, the DP algorithm picks 7+6 to span the distance. A greedy algorithm would have picked 10+3, but it's a tie for minimum number of cables. The problem arises, when trying to span 15ft. The DP algorithm ended up picking 6+3+3+3 to get 4 cables, while the greedy algorithm correctly picks 10+3+2 for only 3 cables.
Anyway, doing some light scanning of converting bounded to 0/1, it seems like the well-known approach to convert multiple items to { p, 2p, 4p ... }. My question is how does this conversion work if p+2p+4p does not add up to the number of multiple items. For example: I have 5 3ft cables. I can't very well add { 3, 2x3, 4x3 } because 3+2x3+4x3 5x3. Should I add { 3, 4x3 } instead?
[I'm currently trying to grok the "Oregon Trail Knapsack Problem" paper, but it currently looks like the approach used there is not dynamic programming.]
