Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    a,b = map(int,input().split())
    value.append(b)
    weight.append(a)
dp =[[0 for i in range(W+1)] for t in range(N+1)]
for i in range(0,N):
    for w in range(W+1):
        if weight[i]<= w:
            dp[i+1][w] = max((dp[i][w-weight[i]]+value[i]),dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
w, v = [], []
for _ in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(0, W+1):
        if j - w[i-1] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(N):
    w, v = map(int, input().split())
    for sum_w in range(W+1):
        # i番目の品を取る
        if w <= sum_w:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w] + v)
        # i番目の品を取らない
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N, W = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=np.int64)

for i in range(N):
    w, v = map(int, input().split())
    for sum_w in range(W+1):
        # i番目の品を取る
        if w <= sum_w:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w] + v)
        # i番目の品を取らない
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

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

Submission status: Time Limit Exceeded

Solution code:
n,w_lim = map(int,input().split())
dp = [[0 for i in range(w_lim+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())

w=[]
v=[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

dp=[[0 for i in range(W+1)] for _ in range(N+1)]

for i in range(0,N):
    for j in range(0,W+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = map(int, input().split())
    dp = [[0] * (W+1) for _ in range(N+1)]

    for i in range(1, N+1):
        w, v = map(int, input().split())
        dp_pre = dp[i-1]
        for j in range(w):
            dp[i][j] = dp_pre[j]
        for j in range(w, W+1):
            dp[i][j] = max(dp_pre[j-w] + v, dp_pre[j])

    print(max(dp[N]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#dp[i+1][w]:i番目までの品物を選んだ時の重さがw以下の最大値
#dp[0][0] = 0
#dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w]) (w >= weight[i])
#dp[i+1][w] = dp[i][w] (w < weight[i])

N, W = map(int, input().split())
dp = [[0 for i in range(W+1)] for j in range(N+1)]
wei = []
val = []
for i in range(N):
    w, v = map(int, input().split())
    wei.append(w)
    val.append(v)
for i in range(N):
    for w in range(W+1):
        if w >= wei[i]:
            dp[i+1][w] = max(dp[i][w-wei[i]]+val[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        for j in range(max_capacity, w - 1, -1):
            if dp[j] < dp[j - w] + v:
                dp[j] = dp[j - w] + v
    return dp[max_capacity]


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        for j in range(max_capacity, w - 1, -1):
            dp[j] = max(dp[j - w] + v, dp[j])
    return dp[max_capacity]


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[-1]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for _ in range(N):
        w, v = map(int, input().split())
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    print(dp[-1])


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[-1]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp = dp[:w] + [
            max(dpj, dpjw + v)
            for dpj, dpjw in zip(dp[w:], dp[: (max_capacity + 1 - w)])
        ]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        # for j in range(1, max_capacity + 1):
        #     if w <= j:
        #         dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        #     else:
        #         dp[i][j] = dp[i - 1][j]
    return dp[max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, nb, max_capacity):
    dp = [0 for _ in range(max_capacity + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        # for j in range(1, max_capacity + 1):
        #     if w <= j:
        #         dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        #     else:
        #         dp[i][j] = dp[i - 1][j]
    return dp[max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        dp[i] = [dp[i - 1][j] for j in range(w)] + [
            max(dp[i - 1][j], dp[i - 1][j - w] + v) for j in range(w, max_capacity + 1)
        ]
        # for j in range(1, max_capacity + 1):
        #     if w <= j:
        #         dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        #     else:
        #         dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
weights, values = [], []
for _ in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

def solve(n, w ,weights, values):
    def rec_solve(cw, cv, max_w, i):
        nonlocal weights, values
        #print(cw, cv, i)
        if i == -1:
            return cv
        
        # take
        if weights[i] + cw <= max_w:
            return max(rec_solve(cw+weights[i], cv + values[i], max_w, i-1),
                        rec_solve(cw, cv, max_w, i-1))

        else:
            # dont take
            return rec_solve(cw, cv, max_w, i-1)

    return rec_solve(0, 0, w, n-1)


print(solve(N, W, weights, values))

Submission status: Time Limit Exceeded

Solution code:
N, W = (int(x) for x in input().split())
A = [[int(x) for x in input().split()] for i in range(N)]
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
  w, v = A[i]
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j >= w:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j - w] + v) 
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
cost=[[0 for i in range(w+1)] for j in range(n+1)]
value=[tuple(map(int,input().split())) for i in range(n)]
for i in range(1,n+1):
  for j in range(w+1):
    weight_=value[i-1][0]
    value_=value[i-1][1]
    if j < weight_:
      cost[i][j]=cost[i-1][j]
    else:
      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])
print(cost[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, w = map(int, input().split())
shina = np.array(tuple(tuple(map(int, input().split())) for _ in range(n)))

dp = np.array([[0 for i in range(w+1)] for j in range(n+1)])

for i, wv in enumerate(shina):
    wi = wv[0]
    vi = wv[1]
    dpi = dp[i]

    for sum_w in range(w+1):
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dpi[sum_w - wi] + vi)

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dpi[sum_w])

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
shina = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i, wv in enumerate(shina):
    wi = wv[0]
    vi = wv[1]
    dpi = dp[i]

    for sum_w in range(w+1):
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dpi[sum_w - wi] + vi)

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dpi[sum_w])

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
shina = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i in range(n):
    wi = shina[i][0]
    vi = shina[i][1]
    for sum_w in range(w+1):
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - wi] + vi)

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

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

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
dp = [-1] * (w + 1)
dp[0] = 0
for i in range(n):
  weight,value = map(int,input().split())
  for j in range(w,-1,-1):
    if dp[j] != -1 and weight + j <= w:
      dp[weight+j] = max(dp[weight+j],dp[j] + value)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
dp = {(0,0)}
for i in range(n):
  weight,value = map(int,input().split())
  gone=set()
  for noww,nowv in dp:
    if noww + weight <= w:
      gone.add((noww + weight,nowv + value))
    gone.add((noww,nowv))
  dp = gone
ans = 0
for lastw,lastv in dp:
  ans = max(ans,lastv)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[-1]*(W+1) for i in range(N+1)]
def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    else:
        if i == N:
            work = 0
        elif j < w[i]:
            work = rec(i+1, j)
        else:
            work = max(rec(i+1, j), rec(i+1, j-w[i])+v[i])
        dp[i][j] = work
        return work
result = rec(0, W)
print(result)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv_list = [[int(i) for i in input().split()] for _ in range(N)]

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

w = wv_list[0][0]
v = wv_list[0][1]
dp[0][w] = v

for i in range(1, N):
    w = wv_list[i][0]
    v = wv_list[i][1]
    
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        elif j == w:
            dp[i][j] = max(dp[i-1][j], v)
        else:
            if dp[i-1][j-w] == -1:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
# メモ化再帰
 
n,W = map(int, input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
 
done = [[False]*(W+1) for j in range(n+1)]
memo = [[0]*(W+1) for j in range(n+1)]
    
    
def search(i, u):
    if done[i][u]:
        return memo[i][u]
    
    else:
 
        if i == n:
            return 0
 
        elif u < w[i]:
            done[i][u] == True
            memo[i][u] == search(i+1, u)
            return search(i+1, u)
 
        else:
            res1 = search(i+1, u)
            res2 = search(i+1, u-w[i]) + v[i]
            res = max(res1, res2)
            done[i][u] == True
            memo[i][u] == res           
            return res
 
print(search(0, W))

Submission status: Time Limit Exceeded

Solution code:
# メモ化再帰

n,W = map(int, input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

done = [[False]*(W+1) for j in range(n+1)]
memo = [[0]*(W+1) for j in range(n+1)]
    
    
def search(i, u):
    if done[i][u]:
        return memo[i][u]
    
    else:

        if i == n:
            return 0

        elif u < w[i]:
            done[i][u] == True
            memo[i][u] == search(i+1, u)
            return search(i+1, u)

        else:
            res1 = search(i+1, u)
            res2 = search(i+1, u-w[i]) + v[i]
            res = max(res1, res2)
            done[i][u] == True
            memo[i][u] == res           
            return res

print(search(0, W))

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(0,w+1):
        if j < wv[i-1][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
# 全探索の考え方

n,W = map(int, input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

def search(i, u):
    if i == n:
        return 0
    
    elif u < w[i]:
        return search(i+1, u)
    
    else:
        res1 = search(i+1, u)
        res2 = search(i+1, u-w[i]) + v[i]
        return max(res1, res2)

print(search(0, W))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    dp = []
    for _ in range(N):
        l = [0]*(W + 1)
        dp.append(l)
    
    # dp[0][]だけ初期化
    for j in range(W + 1):
        dp[0][j] = v[0] if j >= w[0] else 0

    for i in range(1, N):
        for j in range(W + 1):
            if j >= w[i]:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
                
    print(dp[N - 1][W])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [{} for i in range(n + 1)]

    for i, item in enumerate(items):
        for i_w in range(w + 1):
            if i_w >= item[0]:
                dp[i + 1][i_w] = max(dp[i].get(i_w - item[0], 0) + item[1], dp[i].get(i_w, 0))
            else:
                dp[i + 1][i_w] = dp[i].get(i_w, 0)

    print(dp[n][w])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [[0] * (w + 1) for i in range(n + 1)]

    for i, item in enumerate(items):
        for i_w in range(w + 1):
            if i_w >= item[0]:
                dp[i + 1][i_w] = max(dp[i][i_w - item[0]] + item[1], dp[i][i_w])
            else:
                dp[i + 1][i_w] = dp[i][i_w]

    print(dp[n][w])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110000 for i in range(110)]
#print(dp)

for i in range(1,n+1):
  for j in range(W+1):
    dp[i][j]=dp[i-1][j]
    if j-wv[i-1][0]>=0:
      dp[i][j]=max(dp[i][j],
                   dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
      
print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
N,W = [int(v) for v in input().split()]
items = [[int(v) for v in input().split()] for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    w,v = items[i-1]
    for cap in range(W+1):
        if cap - w >= 0:
            dp[i][cap] = max(dp[i][cap],dp[i-1][cap-w]+v)
        dp[i][cap] = max(dp[i][cap],dp[i-1][cap])

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

Submission status: Time Limit Exceeded

Solution code:
N,W = [int(v) for v in input().split()]
items = [[int(v) for v in input().split()] for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i,(w,v) in enumerate(items,1):
    for cap in range(W+1):
        if cap - w >= 0:
            dp[i][cap] = max(dp[i][cap],dp[i-1][cap-w]+v)
        dp[i][cap] = max(dp[i][cap],dp[i-1][cap])

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int,input().split())
  dp[n][:] = dp[n-1][:]
  for w in range(W+1):
    if w + wn > W: break
    dp[n][w+wn] = max(dp[n][w+wn],dp[n-1][w]+vn)
print(max(dp[N]))