backpack

def backpack_bottom_up(values,weights,max_weight_constraint,cache):
    for total_items in range(len(values)+1):
        for max_weight in range(max_weight_constraint+1):
            current_item = total_items - 1
            if total_items == 0 and max_weight == 0:
                cache[total_items][max_weight] = 0
            elif weights[current_item] > max_weight:
                cache[total_items][max_weight] = cache[total_items - 1][max_weight]
            else:
                with_item = values[current_item] + cache[total_items - 1][max_weight - weights[current_item]]
                without_item = cache[total_items - 1][max_weight]

                cache[total_items][max_weight] = max(with_item, without_item)

    return cache[len(values)][max_weight_constraint]

def print_cache(cache):
    for row in cache[:-1]:
        print(row)

values = [40,20,60,100]
weight = [1,2,3,4]

max_weight = 5

cache = [[0 for c in range(max_weight+1)] for c in range(len(weight)+2)]

print(backpack_bottom_up(values, weight, max_weight, cache))

print_cache(cache)