Buggy python submission (verdict: Time Limit Exceeded):
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]

def knapsack01rec(i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(i-1, j),
            knapsack01rec(i-1, j-weights[i-1]) + values[i-1])
    return dp[i][j]

res = knapsack01rec(n, W)
print(res)

Fixed submission:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(n, W, weights, values, dp, i-1, j),
            knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1]) + values[i-1])
    return dp[i][j]

n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)

print(res)

Fixed submission:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Buggy python submission (verdict: Runtime Error):
def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(n, W, weights, values, dp, i-1, j),
            knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1]) + values[i-1])
    return dp[i][j]

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)

print(res)

Fixed submission:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]

n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]
dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)
print(res)

Fixed submission:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):

def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
# dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Fixed submission:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
def knapsack01(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01(n, W, weights, values, dp, n, W)
# print(dp)
print(res)

Fixed submission:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
def repeatableKnapsack(n, W, weights, values):
    dp = [0 for _ in range(W+1)]
    dp[0] = 0
    # print(weights, values)
    for i in range(1,W+1):
        for j in range(n):
            if weights[j] <= i:
                dp[i] = max(dp[i], values[j]+dp[i-weights[j]])
    # print(dp)
    print(dp[-1])
    
def knapsack01(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01(n, W, weights, values, dp, n, W)
# print(dp)
print(res)

Fixed submission:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)