Knapsack 0/1

knapsack.py

def knapsack(wt, input_):
    arr = [[0 for _ in range(wt + 1)] for _ in range(len(input_))]
    for j in range(1, wt + 1):
        arr[0][j] = input_[0][1] if input_[0][0] <= j else 0
    for i in range(1, len(input_)):
        for j in range(1, wt + 1):
            if input_[i][0] > j:
                # if wt is greater than current wt
                arr[i][j] = arr[i-1][j]
            else:
                # max(value_without_this_wt, value_with_this_wt + value_of_remaining_wt)
                arr[i][j] = max(arr[i-1][j], input_[i][1] + arr[i-1][j - input_[i][0]])
    for e in arr:
        print(e)

knapsack(7, [(1, 1), (3, 4), (4, 5), (5, 7)])