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 numpy as np
N, W = map(int, input().split())

items = [tuple(map(int, input().split())) for _ in range(N)]

dp = np.zeros(W+1)

for i, (w, v) in enumerate(items):
    tmp = np.zeros(W+1)
    tmp[w:] = dp[:W-w+1] + v
    dp[w:] = np.fmax(tmp[w:], dp[w:])

print(int(dp[-1]))

Submission status: Runtime Error

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

items = [tuple(map(int, input().split())) for _ in range(N)]

dp = np.zeros(W+1)

for i, (w, v) in enumerate(items):
    tmp = np.zeros(W+1)
    tmp[w:] = dp[:-w] + v
    dp[w:] = np.fmax(tmp[w:], dp[w:])

print(int(dp[-1]))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, log
from collections import defaultdict as dd, deque, Counter as C, OrderedDict as od
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
inf = int(1e20)
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, weight = sp()
mat = []
for i in range(n):
    mat.append(l())
dp = dd(lambda: dd(lambda: inf))
dp[n-1][0] = 0
dp[n-1][mat[n-1][1]] = mat[n-1][0]
for i in range(n-2, -1, -1):
    for j in range(100001):
        dp[i][j] = dp[i+1][j]
        if mat[i][1] <= j:
            dp[i][j] = min(dp[i][j], dp[i+1][j-mat[i][1]] + mat[i][0])
for i in range(100000, -1, -1):
    if dp[0][i] <= weight:
        out(i)
        exit()

Submission status: Runtime Error

Solution code:
import numpy as np
 
N, W = map(int, input().split())
 
items = [tuple(map(int, input().split())) for _ in range(N)]
dp = np.zeros(W+1)

for x, (w, v) in enumerate(items):
	tmp = np.zeros(W+1)
	tmp[w:] = dp[:-w] + v
	dp = np.maximum(tmp,dp)
print(int(max(dp)))

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
a,b=[0]*n,[0]*n
for i in range(n):a[i],b[i]=map(int,input().split())
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 j<a[i-1]:dp[i][j]=dp[i-1][j]
		else:dp[i][j]=max(dp[i-1][j],b[i-1]+dp[i-1][j-a[i-1]])
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

def solve(N, W):
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp[i][:wi] = dp[i-1][:wi]
        dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)
    return dp[N-1][W]

print(solve(N, W))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

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

dp = np.zeros((N, W+1), dtype='int64')

for i in range(N):
    wi, vi = map(int, input().split())

    dp[i][:wi] = dp[i-1][:wi]
    dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)

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

Submission status: Runtime Error

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
w=np.array(w)
v=np.array(v)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
    #print(n,":",w,":",len(dp),":",len(dp[n]))
    x=dp[n][w]
    if x!=-1:
        return x
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n-1]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n-1],weight,value,dp)+value[n-1]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2  
def main():
    n,W=map(int,input().split())
    weight=[]
    value=[]
    for i in range(n):
        a,b=map(int,input().split())
        weight.append(a)
        value.append(b)
    dp=[[-1]*(W+1)]*(n+1)
    print(knap(n,W,weight,value,dp))
    return 0
main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4000000000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(40000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit("4000000")
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Runtime Error

Solution code:
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Runtime Error

Solution code:
# import bisect
# from collections import Counter, deque, OrderedDict
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    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．ナップサックとかはこの一種
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E9%A1%9E%E9%A1%8C-3
    
    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    
    I = N
    # dpテーブル dp[i][j]:=i番目以下で価値j以上の時の，重さの最小値
    J = 100010
    dp = [[0]*(J+1) for _ in range(I+1)]
    # 初期条件
    dp[0][0] = 0
    # ループ
    for i in range(1, I+1):
        for j in range(J+1):
            if j-V[i-1] >= 0:
                dp[i][j] = min(dp[i][j],dp[i-1][j-V[i-1]]+W[i-1])
            else:
                dp[i][j] = min(dp[i][j],dp[i-1][j])
    ans=0
    for j in range(J+1):
        if dp[I][j]<=w:
            ans=j
    print(ans)
    
# resolve()

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 8
3 30
4 50
5 60"""
        output = """90"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1 1000000000
1000000000 10"""
        output = """10"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6 15
6 5
5 6
6 4
6 6
3 5
7 2"""
        output = """17"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

Submission status: Runtime Error

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

dp = [[float("inf") for _ in range(10 ** 3 + 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(10 ** 5 + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

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

Submission status: Runtime Error

Solution code:
import sys
# import numpy as np

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

N, W = IL()
v_list = [0] * N
w_list = [0] * N
v = 0
w_total = 0
for i in range(N):
	w_list[i], v_list[i] = IL()
# dp = np.zeros((N+1, W+1))
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
	for j in range(W+1):
		if j >= w_list[i]:
			dp[i+1][j] = max(dp[i][j-w_list[i]] + v_list[i], dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
import numpy as np

N,W = map(int, input().split())
items = []
for i in range(N):
    array = list(map(int, input().split()))
    items.append(array)

dp = np.zeros(W+1,np.int64)

for w,v in items:
    a = dp[w:]
    b = dp[:-w]
    c = dp[:-w].copy()+v
    np.maximum(dp[w:],dp[:-w].copy()+v,out=dp[w:])

answer = dp.max()
print(answer)

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n, W = rli()
	weight = [0 for _ in range(n)]
	val = [0 for _ in range(n)]
	for i in range(n):
		w, v = rli()
		weight[i], val[i] = w, v
	#dp(i, j) = max val using items 1,...,i at 
	#			weight j

	dp = [[NINF for c in range(W+1)] for r in range(n+1)]
	for r in range(n+1):
		dp[r][0] = 0
	for c in range(W+1):
		dp[0][c] = 0
	for r in range(1, n+1):
		w, v = weight[r-1], val[r-1]
		for c in range(1, W+1):
			if c - w < 0:
				dp[r][c] = max(dp[r][c], dp[r-1][c])
			else:
				dp[r][c] = max(dp[r][c], dp[r-1][c], v + dp[r-1][c-w])
	print(dp[-1][-1])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

dp = [0]*(W+1)
L = []
for i in range(N):
    w,v = map(int,input().split())
    L.append([v,w])

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

Submission status: Runtime Error

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

dp = [0]*(W+1)
L = []
for i in range(N):
    v,w = map(int,input().split())
    L.append([w,v])

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

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, np.int64)
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:

import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, np.int64)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)
    print(dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

items = [tuple(map(int, input().split())) for _ in range(N)]
dp = np.zeros(W+1, dtype=np.int64)

for i, (w, v) in enumerate(items):
  tmp = np.zeros(W+1, dtype=np.int64)
  tmp[w:] = dp[:-w] + v
  dp = np.maximum(dp, tmp)
print(dp[W])

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

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

for i, (w, v) in enumerate(items):
  tmp = dp[:-w] + v
  dp[w:] = np.maximum(dp[w:], tmp)
print(dp[W])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

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

print(dp)

for i in range(N):
  weight, value = map(int, input().split())
  dp[i + 1] = dp[i]
  dp[i + 1, weight:] = np.maximum(dp[i + 1,weight:], dp[i,:W - weight + 1] + value)

print(dp[N][W])

Submission status: Runtime Error

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

dp = [0] * (W + 1)
cnt = 0

for w, v in L:
  cnt = cnt + w
  ##3,8-5,...15-7
  for i in range(min(cnt, W), w - 1, -1):
    if dp[i] < dp[i - w] + v:
      dp[i] = dp[i - w] + v

print(max(dp))

Submission status: Runtime Error

Solution code:
## coding: UTF-8
import sys
#import time

#start = time.time()
N, W = map(int,input().split())
l = [list(map(int, input().split())) for _ in range(N)]


dp = [ [sys.maxsize] * (N * 1000) for _ in range(N) ]
for i in range(N):
    for j in range(N * 1000):
        w = l[i][0]
        v = l[i][1]
        if(j == 0):
            dp[i][j] = 0
        elif(j <= v):
            dp[i][j] = min(dp[i-1][j], w)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w)
#for k in range(N):
    #print(dp[k][:20])


cnt = 0
i = 0
while cnt <= W:
    cnt = dp[-1][i]
    i += 1
print(i-2)#0-index , while分の構造上、iが2多くなる

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,W=map(int,input().split())
    #H=[list(map(int,input().split())) for _ in range(n)]
    dp=[[] for _ in range(n)]
    for i in range(n):
        wi,vi=map(int,input().split())
        dp[i].append((wi,vi))
        if i==0:
            continue
        ans=vi
        for wn,vn in dp[i-1]:
            dp[i].append((wn,vn))
            if wn+wi>W:
                continue
            else:
                dp[i].append((wi+wn,vi+vn))
                ans=max(ans,vi+vn)
    print(ans)
    
        
    
main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,W=map(int,input().split())
    #H=[list(map(int,input().split())) for _ in range(n)]
    dp=[[] for _ in range(n)]
    for i in range(n):
        wi,vi=map(int,input().split())
        dp[i].append((wi,vi))
        if i==0:
            continue
        ans=vi
        for wn,vn in dp[i-1]:
            if wn+wi>W:
                continue
            else:
                dp[i].append((wi+wn,vi+vn))
                ans=max(ans,vi+vn)
    print(ans)
    
        
    
main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,W=map(int,input().split())
    #H=[list(map(int,input().split())) for _ in range(n)]
    dp=[[] for _ in range(n)]
    for i in range(n):
        wi,vi=map(int,input())
        dp[i].append((wi,vi))
        if i==0:
            continue
        ans=vi
        for wn,vn in dp[i-1]:
            if wn+wi>W:
                continue
            else:
                dp[i].append((wi+wn,vi+vn))
                ans=max(ans,vi+vn)
    print(ans)
    
        
    
main()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
Wl, Vl = [], []
for i in range(N):
    w, v = map(int, input().split())
    Wl.append(w); Vl.append(v)

dp = [[10**9+1]*(10**7) for _ in range(N+2)]
dp[0][0] = 0

ans = 0
for i in range(N):
    w, v = Wl[i], Vl[i]
    for j in range(10**5+100):
        if j+v < 10**7+1:
            dp[i+1][j+v] = min(dp[i+1][j+v],
                                dp[i][j]+w)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i+1][j+v] <= W: ans=max(ans, j+v)
        if dp[i+1][j] <= W: ans=max(ans, j)
print(ans)

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
Wl, Vl = [], []
for i in range(N):
    w, v = map(int, input().split())
    Wl.append(w); Vl.append(v)

dp = [[10**9+1]*(10**5+100) for _ in range(N+2)]
dp[0][0] = 0

ans = 0
for i in range(N):
    w, v = Wl[i], Vl[i]
    for j in range(10**5):
        if j+v < 10**9+1:
            dp[i+1][j+v] = min(dp[i+1][j+v],
                                dp[i][j]+w)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i+1][j+v] <= W: ans=max(ans, j+v)
        if dp[i+1][j] <= W: ans=max(ans, j)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,W = [int(e) for e in input().split()]
v = np.zeros(n,dtype='int64')
w = np.zeros(n,dtype='int64')
 
for i in range(n):
    w[i],v[i] = [int(e) for e in input().split()]
 
dp = np.zeros(W+1,dtype='int64')
 
for i in range(n):
    dp[w[i]:] = np.maximum(dp[:W-w[i]+1]+v[i],dp[w[i]:])
 
print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np

n,W = [int(e) for e in input().split()]

w = np.zeros(n+1,dtype='int64')
v = np.zeros(n+1,dtype='int64')

for i in range(n):
    w[i+1],v[i+1] = [int(e) for e in input().split()]

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

for i in range(n):
    dp[w[i+1]:] = np.maximum(dp[:W-w[i+1]+1] + v[i+1],dp[w[i+1]:])

print(dp[-1])

Submission status: Runtime Error

Solution code:
## coding: UTF-8


N, W = map(int,input().split())
l = [list(map(int, input().split())) for _ in range(N)]

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

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

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, W = map(int, input().split())
    B = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        w = B[i][0]
        v = B[i][1]
        for j in range(W + 1):
            if j >= w:
                dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
inf = 2**60
'''
def table(size, init): #配列生成
  x = len(size)
  l = [init for i in range(size[x-1])]
  for i in range(x-1):
    l = [l for k in range(size[x-2-i])]
  return l
'''

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

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

for i in range(n):
  for j in range(100010):
    if dp[i][j] != -1:
      dp[i+1][j] = max(dp[i][j], dp[i+1][j])
      if dp[i][j]+w[i] <= W:
        dp[i+1][j+v[i]] = max(dp[i][j] + w[i], dp[i+1][j+w[i]])

for i in range(100010):
  if dp[n][100010-i] != -1:
    print(100010-i)
    break

Submission status: Runtime Error

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007
inf = 10**12
#+++++

def main():
	#a = int(input())
	n, max_w = IN()
	#s = input()
	dp_v = [inf] * (10**5)
	dp_v[0] = 0
	for _ in range(n):
		add_v = []
		w, v = IN()
		for i, cv in enumerate(dp_v):
			if dp_v[i] == inf:
				continue
			if dp_v[i] + w < dp_v[i+v]:
				add_v.append((i+v, dp_v[i] + w))
		for i, nv in add_v:
			dp_v[i] = nv
	for i, min_w in enumerate(dp_v[::-1]):
		if min_w <= max_w:
			v=len(dp_v)-i-1
			return v
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
maxValue = N*1000
dp = [[float("inf") for i in range(maxValue+1)] for j 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,maxValue+1):
        dp[i][v] = dp[i-1][v]
        if value[i] > v: continue;
        dp[i][v] = min(dp[i][v],weight[i] + dp[i-1][v-value[i]])
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = np.zeros(W + 1, dtype='int64')

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
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 = np.zeros((N+1,W+1), dtype=np.int16)

for i in range(N):
    DP [i+1] = np.array(DP[i])
    DP[i+1][w[i]:] = np.maximum(DP[i][:-w[i]]+ v[i], DP[i][w[i]:])

#print(DP)
print(DP[-1][-1])

Submission status: Runtime Error

Solution code:
import numpy as np
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 = np.zeros((N+1,W+1), dtype=np.int64)

for i in range(N):
    DP [i+1] = np.array(DP[i])
    DP[i+1][w[i]:] = np.maximum(DP[i][:-w[i]]+ v[i], DP[i][w[i]:])

#print(DP)
print(DP[-1][-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.zeros(W+1, dtype=int)
# i 円以下で買える商品の最大価値
# TLE案件のやつ
for i in range(N):
    DP[w[i]:] = np.maximum(DP[:-w[i]]+ v[i], DP[w[i]:])
print(DP[-1])

Submission status: Runtime Error

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

for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
if sum(Weight) <= W:
    print(sum(Value))
    exit()

DP = [[0] * (W + 1) for i in range(N + 1)]
for n in range(1, N + 1):
    for wei in range(W + 1):
        if Weight[n] > wei:
            DP[n][wei] = DP[n - 1][wei]
        else:
            DP[n][wei] = max(DP[n - 1][wei], DP[n - 1][wei - Weight[n]] + Value[n])
print(DP[N][W])

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
array = [0] + [[int(x) for x in input().split()] for x in range(n)]
v_max = 100000
dp = [[float("inf") for x in range(v_max+1)] for x in range(n+1)]
for v in range(1,v_max+1):
    for i in range(1,n+1):
        if(array[i][1]>=v):
            dp[i][v] = dp[i-1][v]
        else:
            dp[i][v] = min(dp[i-1][v],array[i][0]+dp[i-1][v-array[i][1]])
for v in range(v_max+1):
    if(dp[n][v] <= w):
        ans = v
print(ans)

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
array = [[int(x) for x in input().split()] for x in range(n)]
v_max = 10000
dp = [[float("inf") for x in range(v_max+1)] for x in range(n+1)]
for v in range(1,v_max+1):
    for i in range(1,n+1):
        if(array[i-1][1]>=v):
            dp[i][v] = min(dp[i-1][v],array[i-1][0])
        else:
            dp[i][v] = min(dp[i-1][v],array[i-1][0]+dp[i-1][v-array[i-1][1]])
ans = 0
for v in range(v_max+1):
    if(dp[n+1][v] <= w):
        ans = v
print(ans)

Submission status: Runtime Error

Solution code:
for i in range(N) :
  b=input().split()
  w=int(b[0])
  v=int(b[1])

  wv_list.append([w,v])

n_list=  [[0 for i in range(W+1)] for j in range(N)]


if wv_list[0][0]<=W :
    n_list[0][wv_list[0][0]]=wv_list[0][1]

for i in range(1,N) :
    for j in range(W) :
        s=j+wv_list[i][0]
        if s<=W :
            n_list[i][s]=max(n_list[i-1][j]+wv_list[i][1],n_list[i][s])

        n_list[i][j] = max(n_list[i - 1][j],n_list[i][j])

print(max(n_list[-1]))

Submission status: Runtime Error

Solution code:
'''

0-1 Knapsack Problem DP Bottom up solution
'''
def knapsack(N, W, w, v):
    dp = []
    for i in range(N + 1):
        dp.append([-1] * (W + 1))
    for i in range(N + 1):
        dp[i][0] = 0
    for i in range(W + 1):
        dp[0][i] = 0

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

for i in range(N):
    x, y = map(int, input().split())
    w.append(x)
    v.append(y)

ans = knapsack(N, W, w, v)

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 10] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
    dp[:v] = np.minimum(dp[:v] , w)
  
for v in range(V + 1):
    if dp[v] <= W:
        ans = v
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = np.zeros(W+1 , np.int64)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:] , dp[:-w] + v)
 
print(dp[-1])