knapsack.py

# pseudo polynomial time, pseudo polynomial space
def solve(vals, weights, limit):
    table = [[0 for w in range(limit+1)]]
    for j in range(1,len(vals)+1):
        curr_item_max_values = []
        for w in range(limit+1):
            if weights[j-1] > w:
                curr_item_max_values.append(table[j-1][w])
            else:
                curr_item_max_values.append(max(table[j - 1][w],
                                            table[j-1][w - weights[j-1]] + vals[j-1]))
        table.append(curr_item_max_values)
    return table[-1][-1]


# pseudo polynomial time, pseudo linear space
def solve(vals, weights, limit):
    memo = [0 for w in range(limit+1)]
    for j in range(1,len(vals)+1):
        curr_item_max_values = []
        for w in range(limit+1):
            if weights[j-1] > w:
                curr_item_max_values.append(memo[w])
            else:
                curr_item_max_values.append(
                    max(
                        memo[w],
                        memo[w - weights[j-1]] + vals[j-1]
                    )
                )
        memo = curr_item_max_values
    return memo[-1]


v = [10, 40, 30, 50]
w = [5, 4, 6, 3]
l = 10
print(solve(v, w, l) == 90)
v = [20, 2, 4, 6, 7, 8, 10]
w = [1, 4, 4, 5, 4, 4, 7]
l = 10
print(solve(v, w, l) == 35)
v = [20, 2, 4, 6, 7, 8, 10]
w = [1, 4, 4, 5, 4, 4, 7]
l = 31
print(solve(v, w, l) == 57)
v = [10, 40, 30, 50]
w = [5, 4, 6, 3]
l = 100
print(solve(v, w, l) == 130)