0-1 Knapsack Problem in Python

April 22, 2016

The 0-1 Knap­sack prob­lem is a vari­a­tion on the knap­sack prob­lem with one con­di­tion: there is only one copy of each item. You may choose to pick it or not. Given this con­di­tion, it’s pos­si­ble to iter­ate through the items and mem­o­ize the deci­sions sequen­tial­ly.

At each iter­a­tion of i and j:

  1. Check if the cur­rent item is larger than the capac­i­ty. If it is, ignore the item. In this con­text, ignor­ing the item means that for this par­tic­u­lar com­bi­na­tion of i and j, the max­i­mum value is the same as the pre­vi­ous value of i.
  2. If the cur­rent item can fit in the knap­sack, then the max­i­mum value for this com­bi­na­tion of i and j is the larger of the values result­ing from both out­comes. table[i-1][j] rep­re­sents the value if you choose to ignore the item, and table[i-1][j-weights[i-1]] + values[i-1] rep­re­sents the value if you choose to put the item in your knap­sack.
# Returns the maximum value of the knapsack

# _0_1_knapsack :: [Int] -> [Int] -> Int -> Int
def _0_1_knapsack(values, weights, capacity):

    number_of_items = len(values)
    table = []

    for i in range(number_of_items):
        table.append([None] * capacity)

    for j in range(capacity):
        table[0][j] = 0

    for i in range(1, number_of_items):
        for j in range(capacity):
            if weights[i-1] > j:
                table[i][j] = table[i-1][j]
                table[i][j] = max(table[i-1][j], table[i-1][j-weights[i-1]] + values[i-1])

    return table[-1][-1]

values  = [3,5,1,2,4,6,3,2,4]
weights = [1,2,4,6,1,6,2,3,4]
capacity = 10

print(_0_1_knapsack(values, weights, capacity)) # 17