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: Runtime Error

Solution code:
    import sys,io
    from functools import lru_cache
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10**8)
    def read():
      return int(readline())
    def reads():
      return map(int, readline().split())
    def mp(arg):
      return map(int,arg.split())
    N,W=reads()
    weight,value=[0]*N,[0]*N
    for i in range(N):
        weight[i],value[i]=reads()
    dp=[[ 0 for _ in  range(W+1) ] for _ in range(N+1)]
    for i in range(N):
      for k in range(W+1):
        if (k >= weight[i]) :dp[i+1][k] = max(dp[i][k-weight[i]] + value[i], dp[i][k])
        else :dp[i+1][k] = dp[i][k]
    print("{}".format(dp[N][W]))

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W + 1, dtype = np.int64)

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

print(dp[W])

Submission status: Runtime Error

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [math.inf]*max_value
    return -1
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [math.inf]*max_value
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [math.inf]*max_value
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    #for j in range(max_value):
        #if dp[j] != math.inf:
            #print(j, 'can be achieved with weight', dp[j])
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
def read_int():
    return int(input().strip())
 
 
def read_ints():
    return list(map(int, input().strip().split(' ')))
 
 
def solve():
    """
    OPT[N][W] = maximum value obtained with first N items and weights up to W
    OPT[N][W] = max(OPT[N-1][W-w[N]]+v[N], OPT[N-1][W])
    OPT[0][0] = 0
    """
    N, W = read_ints()
    w, v = [], []
    for _ in range(N):
        w0, v0 = read_ints()
        w.append(w0)
        v.append(v0)
    OPT = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,W+1):
            OPT[i][j]=OPT[i-1][j]
            if j-w[i-1]>=0:
                OPT[i][j]=max(OPT[i][j],OPT[i-1][j-w[i-1]]+v[i-1])
    return OPT[-1][-1]
if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:

import sys
import numpy as np

def a():
    rl = sys.stdin.readline

    N, W = map(int, rl().split())
    dp = np.full(W+1, -1, dtype=np.int64)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, rl().split())
        for i in range(W-w, -1, -1):
            dpi = dp[i]
            if dpi == -1:
                continue
            if dp[i+w] < dpi + v:
                dp[i+w] = dpi + v
    print(max(dp))
a()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

rl = sys.stdin.readline

N, W = map(int, rl().split())
dp = np.full(w+1, -1, dtype=np.int64)
dp[0] = 0
for _ in range(N):
    w, v = map(int, rl().split())
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
rl = sys.stdin.readline

N, W = map(int, rl().split())
dp = [-1 for _ in W+1]
dp[0] = 0
for _ in range(N):
    w, v = map(int, rl().split())
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
rl = sys.stdin.readline

N, W = map(int, rl().split())
dp = [-1]*(W+1)
dp[0] = 0
for _ in range(N):
    w, v = map(int, rl().split())
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys

rl = sys.stdin.readline

N, W = map(int, rl().split())
dp = [-1]*(W+1)
dp[0] = 0
for _ in range(N):
    w, v = map(int, rl().split())
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))

Submission status: Runtime Error

Solution code:
# D Knapsack 1
import copy

n, w = map(int, input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)] # n*2

dp = [float('-Inf')] * (w+2)
dp[0] = 0
buy_list = [[False] * n for j in range(w+2)] # (w+2)*n

for i in range(w):
    for j in range(n):
        if buy_list[i][j]:
            continue
        _w = wv_list[j][0]
        _v = wv_list[j][1]
        if i+_w > w:
            _w = w - i + 1
        if dp[i+_w] < dp[i]+_v:
            dp[i+_w] = dp[i]+_v
            buy_list[i+_w] = copy.deepcopy(buy_list[i])
            buy_list[i+_w][j] = True
            
print(max(dp[:w+1]))

Submission status: Runtime Error

Solution code:
# D Knapsack 1


n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(dp, wv_list, i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(dp, wv_list, i-1, j)
    else:
        _ret = max(dp_solve(dp, wv_list, i-1, j), dp_solve(dp, wv_list, i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(dp, wv_list, n, w))

Submission status: Runtime Error

Solution code:
# D Knapsack 1

from collections import deque

n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(w+1):
        if j-_w < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-_w]+_v)

print(dp[n][w])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0]*((n* 10**3) + 1 ) for j in range(3)]
	w_v_list = [read() for i in range(n)]
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		for k in range(w+1):
			dp[(i+1)%3][k] = 0
	for i in dp:
		ans = max(i)
	print(ans)




if __name__ == "__main__":
	solve()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0]*(10**5 + 5) for j in range(3)]
	w_v_list = [read() for i in range(n)]
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		for k in range(w+1):
			dp[(i+1)%3][k] = 0
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [np.array([0]*(w+1), dtype=np.int8) for j in range(3)]
	w_v_list = [read() for i in range(n)]
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		for k in range(w+1):
			dp[(i+1)%3][k] = 0
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Submission status: Runtime Error

Solution code:
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		for k in range(w+1):
			dp[(i+1)%3][k] = 0
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.full(10**5,10**18,dtype=np.int64)
dp[0]=0
for w,v in wv:
    np.minimum(dp[v:],dp[:-v]+w,out=dp[v:])
print(np.where(dp<=W).max())

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.zeros(W+1)
for w,v in wv:
    np.maximum(dp[w:],dp[:-w]+v,out=dp[w:])
print(int(dp.max()))

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.zeros(W+1,dtype=np.int64)
for w,v in wv:
    np.maximum(dp[w:],dp[:-w]+v,out=dp[w:])
print(dp.max())

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
ans = 0
n, w = map(int, input().split())
lst = [[0,0]]
for _ in range(n):
    a, b = map(int, input().split())
    lst.append([a,b])
dp = [[0] * (w+1) for _ in range(n+1)]

for i in range(0, n):
    for sum_w in range(0, w+1):
        if sum_w  >= lst[i+1][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w -  lst[i+1][0]] + lst[i+1][1], dp[i][sum_w])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
        ans = max(ans, dp[i+1][sum_w])    
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

for i in range(N):
    w, v = map(int, input().split())
    dp = np.concatenate([dp[:w], np.fmax(dp[w:], dp[:W+1-w]+v)])
    #print(dp)
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
dp_pv = [0]*(W+1)

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

Submission status: Runtime Error

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
        for j in range(V+1)):
        if j-v>=0 and dp[i-1][j-v]+w<=W:
            dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
DP=[[0]*(W+1) for i in range(N+1)]
for i in range(1, W+1):
    DP[0][i] = float("-inf")
for i in range(1, N+1):
    for j in range(W+1):
        if j-X[i-1][0] >= 0:
            DP[i][j] = max(DP[i-1][j], DP[i-1][j-X[i-1][0]]+X[i-1][1])
        else:
            DP[i][j] = DP[i-1][j]
print(max(DP[N]))
                    
#最後から2行目。
#ありえないのは-INFで選ばれないように

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
N,W=list(map(int,input().split()))
DP=np.zeros(W+1)

for i in range(N):
    w,v=list(map(int,input().split()))
    a=DP[:-w]+v
    b=DP[w:]
    c=np.maximum(a,b)
    DP[w:]=c



print(int(DP[-1]))
# for i in DP:
#     print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
n,W=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l=np.array(l)
s=0
for i in range(n):
  s+=l[i][1]
dp=[0]*(s+1)
dp=np.array(dp)
for ll in range(n):
  dp[ll[1]:]=min(dp[:-ll[1]]+ll[0],dp[ll[1]]):
ans=0
for t in range(s):
  if dp[t]>W:
    break
  else:
    ans=t
print(ans-1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.full(N*10**3+1, W+1, dtype=int)

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
 
N, W = map(int,input().split())
 
dp = np.zeros(W+1, dtype=int)
 
for i in range(N):
    w, v = map(int,input().split())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m

print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(W+1, dtype=int)

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(W+1, dtype=int)

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # ではなく...
    # dp[i][v] := 荷物0~iの中から荷物を選んで価値vを超える時の重さ合計の最小値
    # 初期値dp[0][v] = 0の重さ(もし0の価値がvを超えないならINF)
    V = 1000*100
    INF = float("inf")
    dp = [[INF]*(V+1) for i in range(N)]
    for x in range(V+1):
        dp[0][x] = INF if v[0]<x else w[0]
    for i in range(N-1):
        for j in range(V+1):
            if j>=v[i+1]:
                # i+1番目を選ぶ
                dp[i+1][j] = min(dp[i+1][j], (dp[i][j-v[i+1]])+w[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    # dpのうちW以下であるものの価値の最大値
    for val in range(V,,-1):
        if dp[-1][val]<=W:
            print(val)
            break

main()

Submission status: Runtime Error

Solution code:
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # 初期値dp[0][W] = 0の価値(もし0の重さがMAXを超えるなら選べない)
    dp = [[0]*(W+1) for i in range(N)]
    for x in range(W+1):
        dp[0][x] = 0 if w[0]>x else v[0]
    for i in range(N-1):
        for j in range(W+1):
            if w[i+1]<=j:
                # i+1番目を選ぶ
                dp[i+1][j] = max(dp[i+1][j], (dp[i][j-w[i+1]])+v[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[-1][W])

main()

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype = "int64")
for i in range(N):
    w, v = map(int, input().split())
    dp[i,-w:] = dp[i-1, -w:] #残りの重さW-w以上にするためには、荷物を入れられない。
    dp[i, :W-w+1] = np.fmax(dp[i-1, :W-w+1], dp[i-1, w:]+v)
print(dp[N-1, 0])

Submission status: Runtime Error

Solution code:
import numpy as np
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv=np.array(wv)
dp=[0]*(W+1)
dp=np.array(dp)
for w,v in wv:
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[W])

Submission status: Runtime Error

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

Ws = []
Vs = []

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

Ans = [[0 for _ in range(N * max(Vs))+1] for _ in range(N)]

Ans[0][Vs[0]] = Ws[0]

for i in range(1, N):
  for v in range(N*max(Vs)+1):
    if v-Vs[i] >= 0:
      Ans[i][v] = max(Ans[i-1][v-Vs[i]] + Ws[i], Ans[i-1][v], Ans[i][v])
    else:
      Ans[i][v] = max(Ans[i-1][v], Ans[i][v])

AnsW = Ans[N-1]
AnsW.sorted()
for i in range(len(AnsW)-1):
  if AnsW[i+1] > W:
    print(AnsW[i])
    break

Submission status: Runtime Error

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

dp = [[-1] * (W + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(W + 1):
        if dp[i][j] == -1:continue
        w, v = wv[i]
        if w + j <= W:
            dp[i + 1][w + j] = max(dp[i + 1][w + j], dp[i][j] + v)

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
ma=999999999
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=[[ma for j in range(n+1)] for i in range(sum(v)+1)]
for i in range(len(dp)):
    dp[i][0]=0
for i in range(1,sum(v)+1):
    for j in range(n):
        if v[j]>i:
            continue 
        elif v[j]<=i and j==0:
            if i==v[j]:
                if dp[i][j]==0:
                    dp[i][j]=ma
                dp[i][j]=min(w[j],dp[i][j])
                print(i,j,w[j])
                print(dp[30])
        elif v[j]<=i and j!=0:
            if dp[i-v[j]][j-1]!=ma:
                dp[i-v[j]][j-1]=min(dp[i-v[j]][j-1]+w[j],dp[i][j])
print(dp[30])
print(dp[60])
print(dp[110])
print(dp[90])
print(dp[80])
print(dp[140])

ans=0
for i in range(1,sum(v)+1):
    for j in range(n):
        if dp[i][j]!=ma or dp[i][j]!=0:
            if dp[i][j]<=W:
                ans=i 
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
MaxW=int(1e5)
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[1e30 for i in range(MaxW+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[WV[i][1]:]=np.minimum(dp[WV[i][1]:],dp[:MaxW-WV[i][1]+1]+WV[i][0])
for i in reversed(range(MaxW+1)):
    if dp[i]<=W:
        print(i)
        break

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = lambda: sys.stdin.buffer.readline().rstrip()
    n, w_max = map(int, input().split())
    import numpy as np

    dp = np.zeros(w_max+1, dtype=int)
    v,w = [],[]
    for i in range(n):
        w_, v_ = map(int, input().split())
        v.append(v_)
        w.append(w_)
    for i in range(n):
        print(np.maximum(dp[w[i]:], v[i]+dp[:-w[i]]))
        dp[w[i]:] = np.maximum(dp[w[i]:], v[i]+dp[:-w[i]])
    print(dp[-1]) 

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = lambda: sys.stdin.buffer.readline().rstrip()
    n, w_max = map(int, input().split())
    import numpy as np

    dp = np.zeros(w_max+1, dtype=int)
    v,w = [],[]
    for i in range(n):
        v_, w_ = map(int, input().split())
        v.append(v_)
        w.append(w_)
    for i in range(n):
        dp[w[i]:] = np.maximum(dp[w[i]:], v[i]+dp[:-w[i]])
    print(dp[-1]) 

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
dp = [-1]*(W+1)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W-w, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i+w] < dp[i] + v:
            dp[i+w] = dp[i] + v
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

    # dp[i][v] = i番目まで見て価値vを達成できる最小の重さ
    dp = [[float("inf")] * (10001) for _ in range(N+1)]
    dp[0][0] = 0

    max_value = 0
    for i, item in enumerate(item_list, 1):
        for v in range(10001):
            # もし品物iが入れられる
            if dp[i-1][v] + item[0] <= W:
                dp[i][v+item[1]] = min(dp[i][v+item[1]], dp[i-1][v]+item[0])
                max_value = max(max_value, v+item[1])
            # 入れないパターン
            dp[i][v] = min(dp[i][v], dp[i-1][v])
    print(max_value)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout


def solve(mw, iw, iv):
    vs = sum(iv)
    A = [[float('inf') for i in range(vs+1)] for i in range(len(iv) + 1)]        
    A[0][0] = 0
    for i in range(1, len(iv) + 1):
        for j in range(vs + 1):
            if j < iv[i-1]: A[i][j] = A[i-1][j]
            else: A[i][j] = min(A[i-1][j], A[i-1][j-iv[i-1]] + iw[i-1])
    ans = 0
    for i in range(len(A[0])-1, -1, -1):
        if A[-1][i] != float('inf') and A[-1][i] <= mw:
            return i

def test():
    f = open('a.txt', 'r')
    t = int(f.readline())
    count, error = 1, 0
    for _ in range(t):
        try:
            n, mw = f.readline().split()
            iw, iv = [], []
            for _ in range(int(n)):
                w, v = f.readline().split()
                iw.append(int(w))
                iv.append(int(v))
            ans = int(f.readline())
            output = solve(int(mw), iw, iv)
            if ans != output:
                error += 1 
                stdout.write(f"Case #:{count} (WA) | Ans: {ans} Output: {output}\n")
            else:
                stdout.write(f"Case #:{count} Pass\n")
        except RuntimeError:
            error += 1
            stdout.write(f"Case #{count} (RE)")
        count += 1
    if error == 0: stdout.write("All test cases passed")
    else: stdout.write(f"Passed: {count-error-1} | Errors: {error}")

def main():
    iw, iv = [], []
    n, mw = [int(i) for i in stdin.readline().split()]
    for _ in range(n):
        w,v = [int(i) for i in stdin.readline().split()]
        iw.append(w)
        iv.append(v)
    print(solve(mw, iw, iv))

main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout


def solve(mw, iw, iv):
    vs = sum(iv)
    A = [[float('inf') for i in range(vs+1)] for i in range(len(iv) + 1)]        
    A[0][0] = 0
    for i in range(1, len(iv) + 1):
        for j in range(vs + 1):
            if j < iv[i-1]: A[i][j] = A[i-1][j]
            else: A[i][j] = min(A[i-1][j], A[i-1][j-iv[i-1]] + iw[i-1])
    for i in range(len(A[0])-1, -1, -1):
        if A[-1][i] != float('inf') and A[-1][i] <= mw:
            return i

def test():
    f = open('a.txt', 'r')
    t = int(f.readline())
    count, error = 1, 0
    for _ in range(t):
        try:
            n, mw = f.readline().split()
            iw, iv = [], []
            for _ in range(int(n)):
                w, v = f.readline().split()
                iw.append(int(w))
                iv.append(int(v))
            ans = int(f.readline())
            output = solve(int(mw), iw, iv)
            if ans != output:
                error += 1 
                stdout.write(f"Case #:{count} (WA) | Ans: {ans} Output: {output}\n")
            else:
                stdout.write(f"Case #:{count} Pass\n")
        except RuntimeError:
            error += 1
            stdout.write(f"Case #{count} (RE)")
        count += 1
    if error == 0: stdout.write("All test cases passed")
    else: stdout.write(f"Passed: {count-error-1} | Errors: {error}")

def main():
    iw, iv = [], []
    n, mw = [int(i) for i in stdin.readline().split()]
    for _ in range(n):
        w,v = [int(i) for i in stdin.readline().split()]
        iw.append(w)
        iv.append(v)
    print(solve(mw, iw, iv))

main()
# test()

Submission status: Runtime Error

Solution code:
import math
n, W = map(int, input().strip().split())
values = []
weights = []
total = 10
for _ in range(n):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    total += v
dp = [[math.inf]*total for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(1,n+1):
    for v in range(1,total):
        if v < values[i-1]:
            dp[i][v] = dp[i-1][v]
        else:
            dp[i][v] = min(dp[i-1][v],dp[i-1][v-values[i-1]]+weights[i-1]) 
res = 0
for i in range(total):
    if dp[n][i] <= W:
        res = i
print(res)

Submission status: Runtime Error

Solution code:
import math
n, W = map(int, input().strip().split())
 
values = []
weights = []
total = 10
for _ in range(n):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    total += v

dp = [[math.inf for j in range(total)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(1,n+1):
    for v in range(1,total):
        if v < values[i-1]:
            dp[i][v] = dp[i-1][v]
        else:
            dp[i][v] = min(dp[i-1][v],dp[i-1][v-values[i-1]]+weights[i-1]) 
res = 0
for i in range(total):
    if dp[n][i] <= W:
        res = i
print(res)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * 100
    
    dp = np.full(V, V+100)
    # print(len(dp))
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

# print(dp)
print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
n, W = map(int, input().strip().split())

values = []
weights = []
total = 10
for _ in range(n):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    total += v

dp = [[[0, math.inf] for j in range(total)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = [1, 0]
for i in range(1,n+1):
    for v in range(1,total):
        exclude = dp[i-1][v]
        include = [0, math.inf]
        if v >= values[i-1]:
            if dp[i-1][v-values[i-1]][1] + weights[i-1] <= W:
                include = dp[i-1][v-values[i-1]]
        dp[i][v] = [exclude[0] or include[0], min(exclude[1], weights[i-1] + include[1])]
res = 0
for i in range(total):
    if dp[n][i][0] == 1:
        res = i
print(res)

Submission status: Runtime Error

Solution code:
import math
n, W = map(int, input().strip().split())

values = []
weights = []

for _ in range(n):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)

dp = [[[0, math.inf] for j in range(1001)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = [1, 0]
for i in range(1,n+1):
    for v in range(1,1001):
        exclude = dp[i-1][v]
        include = [0, math.inf]
        if v >= values[i-1]:
            if dp[i-1][v-values[i-1]][1] + weights[i-1] <= W:
                include = dp[i-1][v-values[i-1]]
        dp[i][v] = [exclude[0] or include[0], min(exclude[1], weights[i-1] + include[1])]
res = 0
for i in range(1001):
    if dp[n][i][0] == 1:
        res = i
print(res)

Submission status: Runtime Error

Solution code:
def main():
    n, w_max = map(int, input().split())
    dp = [[0] * (w_max + 1) for _ in range(n + 1)]
    items = [tuple(map(int, input().split())) for _ in range(n)]
    for i1 in range(1, n + 1):
        w, v = items[i1 - 1][0], items[i1 - 1][1]
        for col in range(1, w_max + 1):
            if w <= col:
                dp[i1][col] = max(dp[i1 - 1][col], dp[i1 - 1][col - w] + v)
            else:
                dp[i1][col] = dp[i1 - 1][col]

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

if __name__ == '__main__':
    main()