Skip to content

Instantly share code, notes, and snippets.

@zhangsen

zhangsen/0-1-knapsack.py

Created June 17, 2012 02:37
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save zhangsen/2943221 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save zhangsen/2943221 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. zhangsen revised this gist Jun 30, 2012. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion 0-1-knapsack.py
    View file
    Original file line number Diff line number Diff line change
    @@ -18,7 +18,7 @@ def knapsack_01_exact_min(weights, values, W):
    choice[i][w] = '|'
    if w >= weights[i]:
    t = K[i-1][w-weights[i]]
    if (w-weights[i]==0 or t) and (K[i][w]==0 or t+values[i] < K[i][w]):
    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
  2. zhangsen created this gist Jun 17, 2012.
    47 changes: 47 additions & 0 deletions 0-1-knapsack.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,47 @@
    # 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]==0 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)