1
$\begingroup$

I originally posted this question at the programmers section of StackExchange (because that section is supposed to deal with data structures and algorithms), but they suggested posting in the math section. Read the FAQ there didn't mention anything about algorithms, but did suggest this section: cs theory. If this should really live in the math section, I'll repost there and delete from here.

Link to the the original question: https://softwareengineering.stackexchange.com/questions/117136/converting-a-bounded-knapsack-problem-to-0-1-knapsack-problem

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. [I suspect that I just need to tweak my value function, but does the DP algorithm handle value functions that vary depending on what else has been selected? My instincts say no.]

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.]

$\endgroup$
  • $\begingroup$ If I understand your question, this is just the Subset Sum problem with the extra criteria of picking the solution with the least number of weights. One can easily solve this, if the weights are small enough, by constructing a graph whose vertices are the values of partial solutions and then backtracking from the last vertex to find the shortest (unweighted) distance to the origin. $\endgroup$ – user834 Nov 3 '11 at 19:21
  • $\begingroup$ I am not sure if this question is on-topic for cstheory. For non-research level question in TCS you may want to try Math.SE. (ps: this is not a section, each of these sites have separate identities, they are part of SE network but each has its own culture. Please read the FAQ to understand the scope cstheory). $\endgroup$ – Kaveh Nov 4 '11 at 0:32

Your Answer

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

Browse other questions tagged or ask your own question.