{{ message }}

Instantly share code, notes, and snippets.

# zhangsen/0-1-knapsack.py

Created Jun 17, 2012
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)