Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
1  
I would think this is more suitable to math.stackexchange.com or even mathoverflow.net –  Oded Oct 31 '11 at 20:23
3  
I was torn between the generic stackoverflow, and here. Reading the FAQ's on both sites, this site list data structures and algorithms first. Reading the FAQ for the math site, it seemed to be suggest asking at cstheory site instead. –  Ants Oct 31 '11 at 21:26

2 Answers 2

The way that I have seen used to transform a bounded knapsack problem into a 0/1 one is to just have multiple identical items. Say if you have the following items (given as weight, utility):

  • 2 x 1, 2
  • 3 x 2, 3

You would transform it into a 0/1 problem using items with

  • 1, 2
  • 1, 2
  • 2, 3
  • 2, 3
  • 2, 3

And use a 0/1 algorithm to solve it. You will likely have multiple solutions of equal correctness so you select an arbitrary one.


Now about your wire problem: I would have the length of the cable be the wight and the value of each cable being exactly the same (call it 1, though any positive value will work). Now, use your favorite Knapsack solving algorithm but where you would normally select a (partial) solution that maximizes value, select one that minimizes it. Also, disregard all solutions that do not have a total weight that equals the capacity. I can probably (try to) write a more concrete algorithm with actual code if anyone wants it.

share|improve this answer
    
Yup, that is exactly what I doing to fill out weight and value. I was computing for max value, rather than min. I just now changed the code to compute for min as you suggested, and initialized row 0 of the DP table to be the MAXINT. Still the same result, dynamic programming solution for knapsack problems still ends up picking 6+3+3+3 instead of 10+3+2 or 7+6+2. –  Ants Dec 10 '11 at 10:20

It might be some mistake in your code. I wrote the DP program as mentioned by Naryshkin. For the target span 13, it reports 6+7, and for 15, it reports 2+6+7.

# weight: cable length
# total weight: target span
# value: 1 for each cable
# want minimum number of cables, i.e. minimum total value

def knapsack_01_exact_min(weights, values, W):
    # 0-1 knapsack, exact total weight W, minimizing total value
    n = len(weights)
    values = [0] + values
    weights = [0] + weights
    K = [[0 for i in range(W+1)] for j in range(n+1)]
    choice = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            K[i][w] = K[i-1][w]
            choice[i][w] = '|'
            if w >= weights[i]:
                t = K[i-1][w-weights[i]]
                if (w==weights[i] or t) and (K[i][w]==0 or t+values[i] < K[i][w]):
                    choice[i][w] = '\\'
                    K[i][w] = t+values[i]
    return K[n][W], choice

def print_choice(choice, weights):
    i = len(choice)-1
    j = len(choice[0])-1
    weights = [0] + weights
    while i > 0 and j > 0:
        if choice[i][j]=='\\':
            print weights[i],
            j -= weights[i]
        i -= 1
    print

lens = [10, 7, 6] + 5*[3] + 6*[2] + 7*[1]
values = (3+5+6+7)*[1]
span = 13
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

span = 15
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

If you adjust the order of the input lengths, it can give other optimal solutions. For example, lens = 5*[3] + 6*[2] + 7*[1] + [10, 7, 6] will give 15=10+2+3.

share|improve this answer
    
Where did you get the if statement: 'if (w-weights[i]==0 or t) and (K[i][w]==0 or t+values[i] < K[i][w]):' ? If forget now the source of my DP algorithm, but I had no zero checks, only check for '(t+value[i] < K[i][w])' –  Ants Jun 29 '12 at 13:51
1  
You are solving for exact total weight, which means that whenever an item is picked, we need to make sure the exact weight (of the current step) is met. So, when we decide to pick an item, the second clause "t+values[i] < K[i][w]" ensures we'll have a smaller total value; but before that, we also need to fullfil the required weight, i.e. the first i-1 items must be able to fullfil the weight (w-weights[i]), hence the first clause "if K[i-1][w-weights[i]]" (I'm using a temporary variable t for that). –  jsz Jun 30 '12 at 15:15
    
There are two additional check "w==weights[i]" and "K[i][w]==0"; they are necessary and due to how the tables are initialized; I think you'll be able to make it out so I won't go into details. (I changed w-weights[i]==0 to w==weights[i]; it should be more clear). –  jsz Jun 30 '12 at 15:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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