Problem p03164 (python)

Fixed submission:
# coding: utf-8

"""
20191120
93分
test:
6 8
2 3
1 2
3 6
2 1
1 3
5 85
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())
    V = sum(vs)

    # initialize
    dp = [[None for _ in range(V+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    dp[0][vs[0]] = ws[0]
    existance[0].add(vs[0])

    for n in range(N-1):
        for v in existance[n]:
            # not-use-update
            if dp[n+1][v] is None:
                dp[n+1][v] = dp[n][v]
            else:
                dp[n+1][v] = min(dp[n][v], dp[n+1][v])
            existance[n+1].add(v)

            # use-update
            if dp[n+1][v+vs[n+1]] is None:
                if dp[n][v] + ws[n+1] <= W:
                    dp[n+1][v+vs[n+1]] = dp[n][v] + ws[n+1]
                    existance[n+1].add(v+vs[n+1])
            else:
                dp[n+1][v+vs[n+1]] = min(dp[n][v] + ws[n+1], dp[n+1][v+vs[n+1]])
                # existance[n+1].add(v+vs[n+1])

    ans = 0
    for v in range(V, 0, -1):
        if dp[-1][v] is not None:
            ans = v
            break

    return ans


def miss_main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
# coding: utf-8

import numpy as np

"""
20191120
test:
6 8
2 3
1 2
3 6
2 1
1 3
5 85
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())
    V = sum(vs)

    # initialize
    dp = [[None for _ in range(V+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    dp[0][vs[0]] = ws[0]
    existance[0].add(vs[0])

    for n in range(N-1):
        for v in existance[n]:
            # not-use-update
            # if dp[n+1][v] is None:
            #     dp[n+1][v] = dp[n][v]
            # else:
            #     dp[n+1][v] = min(dp[n][v], dp[n+1][v])
            dp[n+1][v] = dp[n][v]

            existance[n+1].add(v)

            # use-update
            if dp[n+1][v+vs[n+1]] is None:
                if dp[n][v] + ws[n+1] <= W:
                    dp[n+1][v+vs[n+1]] = dp[n][v] + ws[n+1]
                    existance[n+1].add(v+vs[n+1])
            else:
                dp[n+1][v+vs[n+1]] = min(dp[n][v] + vs[n+1], dp[n+1][v+vs[n+1]])
                existance[n+1].add(v+vs[n+1])

    ans = 0
    for v in range(V, 0, -1):
        if dp[-1][v] is not None:
            ans = v
            break

    return ans


def miss_main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
# coding: utf-8

import numpy as np

"""
20191120
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


if __name__ == "__main__":
    print(main())