0-1 Knapsack Problem in Python

The 0-1 Knapsack problem is a variation on the knapsack problem with one condition: there is only one copy of each item. You may choose to pick it or not. Given this condition, it’s possible to iterate through the items and memoize the decisions sequentially.

At each iteration of i and j:

1. Check if the current item is larger than the capacity. If it is, ignore the item. In this context, ignoring the item means that for this particular combination of i and j, the maximum value is the same as the previous value of i.
2. If the current item can fit in the knapsack, then the maximum value for this combination of i and j is the larger of the values resulting from both outcomes. table[i-1][j] represents the value if you choose to ignore the item, and table[i-1][j-weights[i-1]] + values[i-1] represents the value if you choose to put the item in your knapsack.

 
# 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]
            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