Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
0-1 knapsack with exact total weight and minimal total value
# http://programmers.stackexchange.com/questions/117136/converting-a-bounded-knapsack-problem-to-0-1-knapsack-problem
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.