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^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

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

1 1000000000
1000000000 10

Sample Output 2

10

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: Wrong Answer

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float("inf")] * 1001 for _ in range(N + 1)]

    for i in range(N):
        dp[i+1][v[i]] = w[i]

    for n in range(N):
        for kati in range(1, 1001):
            if dp[n][kati] != float("inf"):
                dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati])
            if v[n] <= kati:
                dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati-v[n]] + w[n])

    ans = 0
    for i in range(1001):
        if dp[-1][i] <= W:
            ans = i

    print(ans)


# 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: Wrong Answer

Solution code:
N,W = map(int,input().split())
w_v = [list(map(int,input().split())) for i in range(N)]
INF = float("inf")
dp = [[INF]*1001 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
  for j in range(1001):
    if j >= w_v[i][1]:
      dp[i+1][j] = min(dp[i][j],dp[i][j-w_v[i][1]]+w_v[i][0])
    else:
      dp[i+1][j] = dp[i][j]
    
ans = 0
for j in range(1001):
  if dp[-1][j] <= W:
    ans = max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w_v = [list(map(int,input().split())) for i in range(N)]
INF = float("inf")
dp = [[INF]*1001 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
  for j in range(1,1001):
    if j >= w_v[i][1]:
      dp[i+1][j] = min(dp[i][j],dp[i][j-w_v[i][1]]+w_v[i][0])
    else:
      dp[i+1][j] = dp[i][j]
    
ans = 0
print(dp[N])
for j in range(1,1001):
  if dp[-1][j] <= W:
    ans = max(ans,j+1)
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w_v = [list(map(int,input().split())) for i in range(N)]
INF = float("inf")
dp = [[INF]*1001 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
  for j in range(1,1001):
    if j >= w_v[i][1]:
      dp[i+1][j] = min(dp[i][j],dp[i][j-w_v[i][1]]+w_v[i][0])
    else:
      dp[i+1][j] = dp[i][j]
    
ans = 0
for j in range(1,1001):
  if dp[-1][j] <= W:
    ans = max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w_v = [list(map(int,input().split())) for i in range(N)]
INF = float("inf")
dp = [[INF]*1001 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
  for j in range(1,1001):
    if j >= w_v[i][1]:
      dp[i+1][j] = min(dp[i][j],dp[i][j-w_v[i][1]]+w_v[i][0])
    else:
      dp[i+1][j] = dp[i][j]
    
ans = 0
for j in range(1,1001):
  if dp[-1][j] <= W:
    ans = max(ans,j-1)
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w_v = [list(map(int,input().split())) for i in range(N)]
INF = float("inf")
dp = [[INF]*1001 for i in range(N+1)]
for i in range(N+1):
  dp[0][i]=0

for i in range(N):
  for j in range(1001):
    if j >= w_v[i][1]:
      dp[i+1][j] = min(dp[i][j],dp[i][j-w_v[i][1]]+w_v[i][0])
    else:
      dp[i+1][j] = dp[i][j]
    
ans = 0
for j in range(1001):
  if dp[-1][j] <= W:
    ans = max(ans,j-1)
print(ans)

Submission status: Wrong Answer

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=[[float("inf") for i in range(10100)] for _ in range(110)]
dp[0][0]=0

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

ans=0

for j in range(0,10100):
    if dp[N][j]<=W:
        ans=max(ans,j)

print(ans)

Submission status: Wrong Answer

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=[[float("inf") for i in range(10100)] for _ in range(110)]
dp[0][0]=0

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

ans=0

for j in range(0,10100):
    if dp[N][j]<=W:
        ans=max(ans,j)

print(ans)

Submission status: Wrong Answer

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=[[float("inf") for i in range(10100)] for _ in range(110)]
dp[0][0]=0

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

ans=0

for j in range(0,10100):
    if dp[N][j]<=W:
        ans=max(ans,j)

print(ans)

Submission status: Wrong Answer

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=[[float("inf") for i in range(10100)] for _ in range(110)]
dp[0][0]=0

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

ans=0
for i in range(0,N+1):
    for j in range(0,10100):
        if dp[i][j]<=W:
            ans=max(ans,j)

print(ans)

Submission status: Wrong Answer

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=[[float("inf") for i in range(1010)] for _ in range(110)]
dp[0][0]=0

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

ans=0
for i in range(0,N+1):
    for j in range(0,1010):
        if dp[i][j]<=W:
            ans=max(ans,j)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())

dp = np.full(N * 1000, W + 10000)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[:-v] + w, dp[v:])

ans = np.max(np.where(dp <= W))
print(ans)

Submission status: Wrong Answer

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=[[float("inf") for i in range(10100)] for _ in range(N+1)]
dp[0][0]=0

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

ans=0
for i in range(0,N+1):
    for j in range(0,10100):
        if dp[i][j]<=W:
            ans=max(ans,j)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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[i][v] = i番目までのお菓子で価値がちょうどvとなる選び方の重さの最小値
'''
dp = [[float('inf')]*(n*101)for i in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(n*100):
        if j < v[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i])

ans = 0
for i in range(n*100-1,-1,-1):
    if dp[n][i] <= W:
        ans = i
        break
print(ans)

Submission status: Wrong Answer

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
from collections import defaultdict

MAX_N = 100001


def solve(values, _nb, max_capacity):
    dp = defaultdict(lambda: MAX_N)
    dp[0] = 0
    for w, v in values:
        keys = sorted(dp.keys(), reverse=True)
        for vk in keys:
            dp[vk + v] = min(dp[vk + v], dp[vk] + w)
    result = 0
    for v, w in dp.items():
        if w <= max_capacity and v > result:
            result = v
    return result


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: Wrong Answer

Solution code:
INF = 10**9 + 1
MAV_V = 10 ** 3

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

    for i in range(1, N+1):
        w, v = map(int, input().split())
        pre_dp = dp[i-1]
        for j in range(v):
            dp[i][j] = min(pre_dp[j], w)
        for j in range(v, MAV_V):
            if pre_dp[j-v] + w <= W:
                dp[i][j] = min(pre_dp[j-v] + w, pre_dp[j])
            else:
                dp[i][j] = pre_dp[j]

    ans = [i for i, v in enumerate(dp[-1]) if v != INF]
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
INF = 10**9 + 1
MAV_V = 10 ** 3

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

    for i in range(1, N+1):
        w, v = map(int, input().split())
        pre_dp = dp[i-1]
        for j in range(v):
            dp[i][j] = min(pre_dp[j], w)
        for j in range(v, MAV_V):
            if pre_dp[j-v] + w <= W:
                dp[i][j] = min(pre_dp[j-v] + w, pre_dp[j])
            else:
                dp[i][j] = pre_dp[j]

    ans = [i for i, v in enumerate(dp[-1]) if v != INF]
    print(max(ans))

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
INF = 10**9 + 1
MAV_V = 10 ** 3

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

    for i in range(1, N+1):
        w, v = map(int, input().split())
        pre_dp = dp[i-1]
        for j in range(v):
            dp[i][j] = pre_dp[j]
        for j in range(v, MAV_V):
            if pre_dp[j-v] + w <= W:
                dp[i][j] = min(pre_dp[j-v] + w, pre_dp[j])
            else:
                dp[i][j] = pre_dp[j]

    ans = [i for i, v in enumerate(dp[-1]) if v != INF]
    print(max(ans))

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dp = [[float("inf") for i in range(1000*N+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for v in range(1000*N+1):
        if wv[i][1] <= v:
            dp[i+1][v] = min(dp[i][v], dp[i][v-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][v] = dp[i][v]
ans = 0
for min_w in dp[N]:
    if min_w<=W:
        ans = min_w
print(ans)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

for i in range(n):
    dp[i][0] = 0

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


ans = 0
for i in range(v_max + 1):
    w_ = dp[n][i]
    if w_ <= w:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

for i in range(n):
    dp[i][0] = 0

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


ans = 0
for i in range(v_max + 1):
    w_ = dp[-1][i]
    if w_ <= w:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

for i in range(n):
    dp[i][0] = 0

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


for i in range(v_max + 1):
    w_ = dp[-1][i]
    if w_ <= w:
        ans = i
print(i)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

for i in range(n):
    dp[i][0] = 0

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


for i in reversed(range(len(dp[-1]))):
    if dp[-1][i] <= w:
        print(i)
        exit(0)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

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

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j])


for i in reversed(range(len(dp[-1]))):
    if dp[-1][i] <= w:
        print(i)
        exit(0)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

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

for i in range(1, n + 1):
    for j in range(v_max + 1):
        w_ = wv[i-1][0]
        v_ = j - wv[i-1][1]
        if v_ >= 0:
            dp[i][j] = min(dp[i-1][v_] + w_, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]


for i in reversed(range(len(dp[-1]))):
    if dp[-1][i] <= w:
        print(i)
        exit(0)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]
dp[0][0] = 0

for i in range(1, n + 1):
    for j in range(v_max + 1):
        if 0 == j:
            dp[i][j] = 0
        else:
            w_ = wv[i-1][0]
            v_ = j - wv[i-1][1]
            if v_ >= 0:
                dp[i][j] = min(dp[i-1][v_] + w_, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]


for i in reversed(range(len(dp[-1]))):
    if dp[-1][i] <= w:
        print(i)
        exit(0)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n)]
dp[0][0] = 0

for j in range(v_max + 1):
    dp[0][j] = wv[0][0] if j == wv[0][1] else w_max

for i in range(1, n):
    for j in range(v_max + 1):
        if 0 == j:
            dp[i][j] = 0
        else:
            w_ = wv[i][0]
            v_ = j - wv[i][1]
            if v_ >= 0:
                dp[i][j] = min(dp[i-1][v_] + w_, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]


for i in reversed(range(len(dp[-1]))):
    if dp[-1][i] <= w:
        print(i)
        exit(0)

Submission status: Wrong Answer

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    INF = 10**10
    VMAX=10**3*N
    dp=[[INF for j in range(VMAX)] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(VMAX):
            if j-v[i-1] >=0:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
            else:
                dp[i][j] = dp[i-1][j]

    for i in range(VMAX-1,-1,-1):
        if dp[-1][i] <= W:
            print(i)
            break
    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: Wrong Answer

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    INF = 10**10
    VMAX=10**2*N
    dp=[[INF for j in range(VMAX)] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(VMAX):
            if j-v[i-1] >=0:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
            else:
                dp[i][j] = dp[i-1][j]

    for i in range(VMAX-1,-1,-1):
        if dp[-1][i] <= W:
            print(i)
            break
    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: Wrong Answer

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 = [[1000000] * 100001 for i in range(n + 1)]
    dp[0][0] = 0

    for i, item in enumerate(items):
        for i_v in range(100001):
            if item[1] - i_v > 0:
                dp[i + 1][i_v] = dp[i][i_v]
            else:
                dp[i + 1][i_v] = min(dp[i][i_v - item[1]] + item[0], dp[i][i_v])

    result = 0
    for sum_v, weght in enumerate(dp[-1]):
        if weght <= w:
            result = sum_v
    print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,w = map(int,readline().split())
WV = []
for i in range(n):
	WV.append(list(map(int,readline().split())))

dp = [[10**12]*(10**2+1) for _ in range(n+1)]
dp[0][0] = 0

#価値j以上で重さがwを満たすようなものの最大値
for i in range(n):
	for j in range(10**2+1):
		if WV[i][1] - j > 0:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = min(dp[i][j],dp[i][j-WV[i][1]]+WV[i][0])

ans = 0
for idx,i in enumerate(dp[-1]):
	if i <= w:
		ans = idx

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W = map(int,input().split())
V_sum = 0
w_l = []
v_l = []
for i in range(N):
    w,v = list(map(int,input().split()))
    V_sum+=v
    w_l.append(w)
    v_l.append(v)
dp = np.full(V_sum+1,10**6)
dp[0] = 0
for i in range(N):
    dp[v_l[i]:] = np.minimum(dp[v_l[i]:],dp[:-v_l[i]]+w_l[i])
for i in range(V_sum,-1,-1):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    MAX_V = 10 ** 3 + 1

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

    for mv in range(MAX_V):
        for i, (w, v) in enumerate(items):
            if mv - v >= 0:
                dp[i+1][mv] = min(dp[i][mv], dp[i][mv - v] + w)
            else:
                dp[i+1][mv] = dp[i][mv]

    print(max([v for v, w in enumerate(dp[N]) if w <= W]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# Python3 implementation of the approach 
V_SUM_MAX = 10**2*10**3
N_MAX = 100
W_MAX = 10**9
  
# To store the states of DP 
dp = [[ 0 for i in range(N_MAX)] 
          for i in range(V_SUM_MAX + 1)] 
v = [[ 0 for i in range(N_MAX)] 
         for i in range(V_SUM_MAX + 1)] 
  
# Function to solve the recurrence relation 
def solveDp(r, i, w, val, n): 
      
    # Base cases 
    if (r <= 0): 
        return 0
    if (i == n): 
        return W_MAX 
    if (v[r][i]): 
        return dp[r][i] 
  
    # Marking state as solved 
    v[r][i] = 1
  
    # Recurrence relation 
    dp[r][i] = min(solveDp(r, i + 1, w, val, n),  
            w[i] + solveDp(r - val[i], i + 1, 
                            w, val, n)) 
    return dp[r][i] 
  
# Function to return the maximum weight 
def maxWeight( w, val, n, c): 
  
    # Iterating through all possible values 
    # to find the the largest value that can 
    # be represented by the given weights 
    for i in range(V_SUM_MAX, -1, -1): 
        if (solveDp(i, 0, w, val, n) <= c): 
            return i 
  
    return 0
  
n,C = map(int, input().split())
w = [] 
val = [] 
for i in range(n):
    wei,vv = map(int, input().split())
    w.append(wei)
    val.append(vv)    

print(maxWeight(w, val, n, C))

Submission status: Wrong Answer

Solution code:
# Python3 implementation of the approach 
V_SUM_MAX = 1000
N_MAX = 100
W_MAX = 10000000000
  
# To store the states of DP 
dp = [[ 0 for i in range(N_MAX)] 
          for i in range(V_SUM_MAX + 1)] 
v = [[ 0 for i in range(N_MAX)] 
         for i in range(V_SUM_MAX + 1)] 
  
# Function to solve the recurrence relation 
def solveDp(r, i, w, val, n): 
      
    # Base cases 
    if (r <= 0): 
        return 0
    if (i == n): 
        return W_MAX 
    if (v[r][i]): 
        return dp[r][i] 
  
    # Marking state as solved 
    v[r][i] = 1
  
    # Recurrence relation 
    dp[r][i] = min(solveDp(r, i + 1, w, val, n),  
            w[i] + solveDp(r - val[i], i + 1, 
                            w, val, n)) 
    return dp[r][i] 
  
# Function to return the maximum weight 
def maxWeight( w, val, n, c): 
  
    # Iterating through all possible values 
    # to find the the largest value that can 
    # be represented by the given weights 
    for i in range(V_SUM_MAX, -1, -1): 
        if (solveDp(i, 0, w, val, n) <= c): 
            return i 
  
    return 0
  
n,C = map(int, input().split())
w = [] 
val = [] 
for i in range(n):
    wei,vv = map(int, input().split())
    w.append(wei)
    val.append(vv)    

print(maxWeight(w, val, n, C))

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout

print = stdout.write
input = stdin.readline
INF = 1e10
n,W = map(int,input().split())

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

max_val=sum(val)    
dp=[[INF for x in range(max_val+1)] for x in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    vi = val[i];wi = wgt[i]
    for V in range(1,max_val+1):
        if vi<= V:
            dp[i][V] = min(wi+dp[i-1][V-vi],dp[i-1][V])
        else:
            dp[i][V]=dp[i-1][V]
res = 0
for i in range(max_val,-1,-1):
    if dp[n][i] <= W:
        res = i
        break
print(str(res))

Submission status: Wrong Answer

Solution code:
#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値

N,W=map(int,input().split())

w,v=[0],[0]

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=[[10**12 for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for sum_v in range(N*max(v)+1):
        if sum_v-v[i]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v-v[i]]+w[i],dp[i][sum_v])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
#print(dp)

ans=0

for sum_v in range(N*max(v)+1):
    if dp[N][sum_v]<=W:
        ans=max(ans,sum_v)
print(ans)

Submission status: Wrong Answer

Solution code:
#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値

N,W=map(int,input().split())

w,v=[0],[0]

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=[[10**12 for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for sum_v in range(N*max(v)+1):
        if sum_v-v[i]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v-v[i+1]]+w[i+1],dp[i][sum_v])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
#print(dp)

ans=0

for sum_v in range(N*max(v)+1):
    if dp[N][sum_v]<=W:
        ans=max(ans,sum_v)
print(ans)

Submission status: Wrong Answer

Solution code:
#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値

N,W=map(int,input().split())

w,v=[0],[0]

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=[[10**12 for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for sum_v in range(N*max(v)+1):
        if sum_v-v[i]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v-v[i+1]]+w[i+1],dp[i][sum_v])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
#print(dp)

ans=0
for i in range(N+1):
    for sum_v in range(N*max(v)+1):
        if dp[i][sum_v]<=W:
            ans=max(ans,sum_v)
print(ans)

Submission status: Wrong Answer

Solution code:
#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値

N,W=map(int,input().split())

w,v=[0],[0]

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=[[10**11+1 for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for sum_v in range(N*max(v)+1):
        if sum_v-v[i]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v-v[i+1]]+w[i+1],dp[i][sum_v])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
#print(dp)

ans=0
for i in range(N+1):
    for sum_v in range(N*max(v)+1):
        if dp[i][sum_v]<=W:
            ans=max(ans,sum_v)
print(ans)

Submission status: Wrong Answer

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

VMAX = 10**5 + 100
ans = 0
dp = [[float('inf')] * (VMAX+1) for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
    for v in range(VMAX):
        if dp[n][v] != float('inf'):
            dp[n+1][v] = dp[n][v]
            dp[n+1][v+V[n]] = min(dp[n+1][v+V[n]], dp[n][v] + W[n])

            if dp[n+1][v+V[n]] <= L:
                ans = max(ans, v+V[n])
# print(*dp, sep='\n')
print(ans)

Submission status: Wrong Answer

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

VMAX = 10**5 + 100
ans = 0
dp = [[float('inf')] * (VMAX+1) for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
    for v in range(VMAX):
        if dp[n][v] != float('inf') and v + V[n] <= VMAX:
            dp[n+1][v] = dp[n][v]
            dp[n+1][v+V[n]] = min(dp[n+1][v+V[n]], dp[n][v] + W[n])

            if dp[n+1][v+V[n]] <= L:
                ans = max(ans, v+V[n])
# print(*dp, sep='\n')
print(ans)

Submission status: Wrong Answer

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

VMAX = 10**4 + 10
ans = 0
dp = [[float('inf')] * (VMAX+1) for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
    for v in range(VMAX):
        if dp[n][v] != float('inf') and v + V[n] <= VMAX:
            dp[n+1][v] = dp[n][v]
            dp[n+1][v+V[n]] = min(dp[n+1][v+V[n]], dp[n][v] + W[n])

            if dp[n+1][v+V[n]] <= L:
                ans = max(ans, v+V[n])
# print(*dp, sep='\n')
print(ans)

Submission status: Wrong Answer

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

VMAX = 10**3 + 10
ans = 0
dp = [[float('inf')] * (VMAX+1) for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
    for v in range(VMAX):
        if dp[n][v] != float('inf') and v + V[n] <= VMAX:
            dp[n+1][v] = dp[n][v]
            dp[n+1][v+V[n]] = min(dp[n+1][v+V[n]], dp[n][v] + W[n])

            if dp[n+1][v+V[n]] <= L:
                ans = max(ans, v+V[n])
# print(*dp, sep='\n')
print(ans)

Submission status: Wrong Answer

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

VMAX = 10**3 + 10
ans = 0
dp = [[float('inf')] * (VMAX+1) for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
    for v in range(VMAX):
        if dp[n][v] != float('inf') and v + V[n] < VMAX:
            dp[n+1][v] = dp[n][v]
            dp[n+1][v+V[n]] = min(dp[n+1][v+V[n]], dp[n][v] + W[n])

            if dp[n+1][v+V[n]] <= L:
                ans = max(ans, v+V[n])
# print(*dp, sep='\n')
print(ans)