Algorithms – How to Convert a Bounded Knapsack Problem to 0/1 Knapsack Problem

algorithms

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, 2×3, 4×3 } because 3+2×3+4×3 > 5×3. Should I add { 3, 4×3 } 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.]

Best Answer

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.

Related Topic