# 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[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]
else:
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``````