values  = [1, 2, 3, 4, 5]
weights = [3, 2, 1, 9, 6]
max_weight = 12

def knappack():
    n = len(values)
    dp = [[0] * (max_weight+1) for _ in range(n)]
    print(dp)

    for i in range(n):
        for j in range(1, max_weight+1):
            if weights[i] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])

    print(dp[-1][-1])

knappack()