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

def knapsackGreedy(sizes, vals, volume):
    ids = np.argsort([val / size for val, size in zip(vals, sizes)])
    sumVal = 0
    for i in ids:
        if sizes[i] <= volume:
            volume -= sizes[i]
            sumVal += vals[i]
        if volume <= 0:
            break
    return sumVal

if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print(knapsackGreedy(sizes, vals, volume))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, W = list(map(int, input().split(" ")))
dp =  [[0] * (W+1) for _ in range(N+1)]
 
for i in range(0, N):
	weight, value = map(int, input().split(" "))
	for w in range(1, W+1):
		if w >= weight:
			dp[i + 1][w] = max([dp[i][w - weight] + value, dp[i][w]])
		else:
			dp[i + 1][w] = dp[i][w]
print(dp[N][W])

Submission status: Runtime Error

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

dp = [0]*(max_w+1)
dp = np.array(dp)

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

print(max(dp))

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 _ in range(n):
    we,v=map(int,input().split())
    if we > w:
        continue
    else:
        np.maximum(dp[we:],dp[:-we]+v,out = dp[we:])
print(dp[w])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
"""
dp[V][i] represents the minimum weight subset of the subarray arr[i…N-1]
required to get a value of at least V. The recurrence relation will be:

dp[V][i] = min(dp[V][i], w[i] + dp[V – val[i]][i + 1]) 

So, for each V from 0 to the maximum value of V possible, try to find if the
given V can be represented with the given array. The largest such V that can
be represented becomes the required answer.
"""

V_SUM_MAX = 1000
N_MAX = 100
W_MAX = 10000000

dp = [[0] * N_MAX for i in range(V_SUM_MAX + 1)]
v = [[0] * N_MAX for i in range(V_SUM_MAX + 1)]

def solveDp(r, i, w, val):
    n = len()

    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]

def maxWeight(w, val, n, c):
    for i in range(V_SUM_MAX, -1, -1):
        if (solveDp(i, 0, w, val, n) <= c):
            return i
    return 0

if __name__ == '__main__':
    n, C = [int(x) for x in input().split()]
    w, val = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        w.append(s)
        val.append(v)

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

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def knapsack(sizes, vals, volume):
    n = len(sizes)

    # dp[i][j] is the max value at item i while using capacity j
    dp = [[0] * (volume+1) for _ in range(n)] # j is 0...volume

    for i in range(n):
        for j in range(volume+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])

    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print(knapsack(sizes, vals, volume))

Submission status: Runtime Error

Solution code:
def knapsack(sizes, vals, volume):
    n = len(sizes)

    # dp[i][j] is the max value at item i while using capacity j
    dp = [[0] * (volume+1) for _ in range(n)] # j is 0...volume

    for i in range(n):
        for j in range(volume+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i]) if j - sizes[i] >= 0 else max(dp[i][j], dp[i-1][j])

    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print(knapsack(sizes, vals, volume))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
x = []
y = []

for i in range(n):
  a,b = map(int, input().split())
  x.append(b)
  y.append(a)

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

for i in range(n):
  for j in range(w + 1):
    if(j >= y[i]):
      dp[i + 1][j] = max(dp[i][j], dp[i][j - y[i]] + x[i])
    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())
dp = np.zeros((N+1, W+1), dtype=int)

w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])

print(dp[N,-1])

Submission status: Runtime Error

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

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

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

for i, z in enumerate(Z):
    #print(i)
    for w in range(W+1):
        if w -z[0] >= 0:
            dp[i+1][w] = max(dp[i][w-z[0]]+z[1], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
    #print(dp)

print(max(dp[-1]))

Submission status: Runtime Error

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

mem = [-1] * (M+1)

def maxVal(i,C):
            # index i, capacity C
    if mem[C] == -1:
        if i == N:
            return 0
        else:
            skip = maxVal(i+1,C)
            if w[i] <= C:   # w[i] does not exceed capacity
                take = v[i] + maxVal(i+1,C-w[i])
            else:
                take = -1
            mem[C] =  max(skip, take)
    return mem[C]
    

print(maxVal(0,M))

Submission status: Runtime Error

Solution code:
def main():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]

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

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

    print(max(dp[-1]))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n,w=map(int,input().split())
  wv=[tuple(map(int,input().split())) for _ in range(n)]
  dp=[[0]*(w+1) for _ in range(n+1)]
  for i in range(n):
    for j in range(w+1):
      dp[i+1][j]=max(dp[i][j-wv[i][0]]+wv[i][1],dp[i][j]) if j-wv[i][0]>=0 else dp[i][j]
  print(dp[n][w])
if __name__=='__main__':
  main()

Submission status: Runtime Error

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

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

print(int(np.max(dp)))

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
max_v,max_w = 0,0
for i,j in zip(w,v):
    max_w += i
    max_v += j
dp = [[float("inf")]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0#初期値
for i in range(1,N+1):
    for j in range(max_v+1):
        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(1,max_v+2):
    if W >= dp[N][-i]:
        print(max_v+1-i)
        break

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 _ in range(N):
    w,v = map(int,input().split())
    if w > W:
        continue
    else:
        np.maximum(dp[w:],dp[:-w]+v,out = dp[w:])
print(dp[W])

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split(' '))
w=[0]*N ; v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split(' '))
dp=[[0]*(W+1) for _ in range(N+1)]
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(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
print(dp[N][W])

Submission status: Runtime Error

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

dp = [[0]*(W+1) for j in range(n+1)]

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

Submission status: Runtime Error

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

dp = [[0]*(W+1) for j in range(n+1)]

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
dp=[0]*(m+1)

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

Submission status: Runtime Error

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

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

INFTY = -1
MAX_V = 10**5
dp = [[INFTY]*(MAX_V+1) for _ in range(N)]
dp[0][S[0][1]] = S[0][0]

for i in range(1, N):
    w, v = S[i]
    for j in range(v):
        dp[i][j] = dp[i-1][j]

    if dp[i-1][v] == -1:
        dp[i][v] = w
    else:
        dp[i][v] = min(dp[i-1][v], w)

    for j in range(v+1, MAX_V+1):
        if dp[i-1][j] == -1 and dp[i-1][j-v] == -1:
            pass
        elif dp[i-1][j] == -1:
            if dp[i-1][j-v]+w > W:
                pass
            else:
                dp[i][j] = dp[i-1][j-v]+w
        elif dp[i-1][j-w] == -1:
            dp[i][j] = dp[i-1][j]
        else:
            if dp[i-1][j-v]+w > W:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)

for i in range(MAX_V, 0, -1):
    if dp[N-1][i] != -1:
        print(i)
        break

Submission status: Runtime Error

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

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

INFTY = -1*10**7
dp = [[0]*(W+1) for _ in range(N)]
dp[0][S[0][0]] = S[0][1]

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

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

Submission status: Runtime Error

Solution code:
IN = iter(Input.split('\n')).__next__
def input():
    return IN()

# 入力
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
V = sum(v)
dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j >= v[i]: dp[i+1][j] = dp[i][j-v[i]]+w[i]
        else: dp[i+1][j] = dp[i][j]
ans = 0
for i in range(V+1):
    if dp[N][i]<=W: ans=i
print(ans)

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(np.max(dp))

Submission status: Runtime Error

Solution code:
N, W = [int(i) for i in input().split()]
noValue = [[W+1 for j in range(10001)] for i in range(N)]
w,v = [int(i) for i in input().split()]
maxValue = v
noValue[0][v] = w

for i in range(1,N) :
	noValue[i][0] = 0
	w, v = [int(i) for i in input().split()]
	for j in range(1,maxValue+v+1) :
		if j < v  :
			noValue[i][j] = noValue[i-1][j]
		else :
			if noValue[i-1][j - v] == W + 1 :
				if j == v :
					noValue[i][j] = w
					maxValue = max(maxValue, j)
				else :
					noValue[i][j] = noValue[i-1][j]
			elif noValue[i-1][j-v] + w > W :
				noValue[i][j] = noValue[i-1][j]
			else :
				noValue[i][j] = min(noValue[i-1][j - v] + w, noValue[i-1][j])
				maxValue = max(maxValue, j)
print(maxValue)

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
max_v,max_w = 0,0
for i,j in zip(w,v):
    max_w += i
    max_v += j

dp = np.ones(max_v+1, dtype=int) * max_w
for i in range(max_v-1,-1,-1):
    for j in range(N):
        if i+v[j] <= max_v:
            dp[i] = min(dp[i+1],dp[i+v[j]]-w[j])
        else:
            dp[i] = dp[i+1]
l = []
for i in dp:
    if i <= W:
        l.append(i)
ans = len(l)-1
print(ans)

Submission status: Runtime Error

Solution code:
def main():
  N,W = map(int,input().split())  #nは入力回数
  num_list = [list(map(int, input().split())) for _ in range(N)]
  dp = [[0] * (W+1) for i in range(N+1)]
  weight=[row[0] for row in num_list]
  value=[row[1] for row in num_list]
  for i in range(0,N):
    for sum_w in range(0,W+1):
      if(sum_w-weight[i]>=0):
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])
      #iを選ばない場合
      dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
  print(int(dp[N][W]))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(int(dp[-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1,np.int64)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
import math

MAX_VALUE = 10 ** 5 + 100

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

def main():
    N,W = map(int,input().split())
    goods = [list(map(int,input().split())) for _ in range(N)]
    
    dp = [[math.inf for _ in range(MAX_VALUE+1)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(MAX_VALUE):
            if v >= goods[i][1]:
                dp[i+1][v] = min(dp[i][v-goods[i][1]]+goods[i][0],dp[i][v])
            else:
                dp[i+1][v] = dp[i][v]
    for v in range(MAX_VALUE):
        if dp[N][v] <= W:
            ans = v
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


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

def main():

    # i have too make index as weight and value as value
    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())
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
        # print(dp[:-w],dp[w:] )


    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

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



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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

    # dp = [[0] * (W + 1) for _ in range(N + 1)]
    dp = np.zeros(W + 1, dtype=np.int64)

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

    # print(w, v, dp)
    print(dp.max())


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

dp = [[0]*(101) for i in range(N+1)]

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


print(dp)

Submission status: Runtime Error

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

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


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


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

Submission status: Runtime Error

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

# dp用配列
dp=[]
for k in range(N+1):
    dp.append([0]*(W+1))


for i in range(N):
    w_i,v_i = map(int,input().split())
    for w in range(W+1):
        if w>=w_i:
            dp[i+1][w] = max(dp[i][w-w_i] + v_i , dp[i][w])
        else:
            dp[i+1][w] =dp[i][w]

# print(*dp,sep="\n")

print(dp[N][W])

Submission status: Runtime Error

Solution code:
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 = [[0]*(W+1) for _ in range(N+1)]
for k in range(W+1):
  dp[0][k] = 0
for i in range(N):
  for j in range(W+1):
    if j -w[i] <0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[-1][W])

Submission status: Runtime Error

Solution code:
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 = [[0]*(W+1) for _ in range(N+1)]
for k in range(W+1):
  dp[0][k] = 0
for i in range(N):
  for j in range(W+1):
    if j -w[i] <0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[-1][W])

Submission status: Runtime Error

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

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

print(max(dp[-1]))

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())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])

print(dp[-1])

Submission status: Runtime Error

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

def solve(values, _nb, max_capacity):
    dp = {}
    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: Runtime Error

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


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


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


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


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


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


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


if __name__ == "__main__":
    import doctest

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

Submission status: Runtime Error

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

x, y  = map(int, input().split())
li =[]
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(1, y+1):
        if j - li[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j - li[i][0] ]+ li[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[x][y])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j < w:
            dp[i][j] = max(dp[i][j], dp[i - 1][j])
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
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 円以下で買える商品の最大価値
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:
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 円以下で買える商品の最大価値
for i in range(N):
    DP[w[i]:] = np.maximum(DP[:-w[i]]+ v[i], DP[w[i]:])
    print(DP)
print(DP[-1])

Submission status: Runtime Error

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

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

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

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

def solve_fast(n_items, max_w, weights, values):
    dp =  [[0]*(max_w+1) for _ in range(n_items)]
    dp[0] = [values[0] if i >= weights[0] else 0 for i in range(max_w+1)]

    for r in range(1, n_items):
        cw, cv = weights[r], values[r]
        for c in range(max_w+1):
            if cw > c:
                dp[r][c] = dp[r-1][c]
            else:
                dp[r][c] = max(dp[r-1][c], dp[r-1][c-cw] + cv)

    #for r in dp:
        #print(r)

    return dp[-1][-1]


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

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
w_ls, v_ls = [0] * n, [0] * n
for i in range(n):
    w_ls[i], v_ls[i] = map(int,input().split())
V = sum(v_ls)
dp = [[float("inf")] * (V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(V+1):
        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(V+1):
    if dp[N][j] <= W:
        ans = j

print(ans)