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: Accepted

Solution code:
import sys

n, W = map(int, input().split())
V = n * 1000
dp = {0: 0}
for line in sys.stdin.readlines():
    w, v = map(int, line.split())
    ndp = dp.copy()
    for i, x in dp.items():
        if i + v in dp:
            ndp[i + v] = min(dp[i + v], x + w)
        else:
            ndp[i + v] = x + w
    dp = ndp

print(max(i for i, x in dp.items() if x <= W))

Submission status: Runtime Error

Solution code:
n, w = list(map(int, raw_input().split()))
weights = []
values = []

for _ in range(n):
    wi, vi = list(map(int, raw_input().split()))
    weights.append(wi)
    values.append(vi)

dp = [[0 for __ in range(w+1)] for _ in range(n+1)]

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
def main():
    MAX_N = 100
    MAX_V = 10 ** 3 + 1
    INF = 10 ** 9 + 1
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    dp = [[INF] * MAX_V for _ in range(MAX_N)]
    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(MAX_V):
            if (sum_v - wv[i][1]) >= 0:
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - wv[i][1]] + wv[i][0])
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])

    res = 0
    for sum_v in range(MAX_V):
        if dp[n][sum_v] <= w:
            res = sum_v

    print(res)


if __name__ == '__main__':
    main()

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 = [0] * (w + 1)
    for wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print(dp[w])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

    for j in range(W, w-1, -1):
        dp[j] = max(dp[j-w] + v, dp[j])
print(dp[-1])

Submission status: Runtime Error

Solution code:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
        ans = 1
        for i in range(1, x+1): ans = (ans * i) % mod
        return ans
def arr2D(n, m, default=0):
        lst = []
        for i in range(n): temp = [default] * m; lst.append(temp)
        return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, W, weight, value):
    dp = arr2D(n+1, W+1)

    for i in range(1, n+1):
        for j in range(1, W+1):
            # print(i, j)
            val = max(dp[i][j-1], dp[i-1][j])
            if j >= weight[i-1]:
                dp[i][j] = max(val, dp[i-1][j-weight[i-1]] + value[i-1])
            else: dp[i][j] = val
    return dp[n][W]

n, W = list(map(int, input().split()))
weight = []
value = []
for i in range(n):
        a, b = list(map(int, input().split()))
        weight.append(a)
        value.append(b)
print(solve(n, W, weight, value))

Submission status: Runtime Error

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

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 >= w_list[i-1]:
            dp[i][j] = max(dp[i-1][j], v_list[i-1]+dp[i-1][j-w_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i])    

print(dp[N][W])

Submission status: Runtime Error

Solution code:
def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 1000
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

dp = [[INF] * V for _ in range(N)]

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv >= V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/15

@author: harurun
'''
import sys
pin=sys.stdin.readline


N,W=map(int,pin().split())
dp=[[0]*(W+1) for _ in [0]*(N+1)]

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
DP = [float('inf')] * 10 ** 5
DP[0] = 0
for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if w + d > W:
            continue
        D[i + v] = min(DP[i + v], w + d)
    DP = D
ans = 0
for i, d in enumerate(DP):
    if d == float('inf'):
        continue
    ans = i
print(ans)

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
weight=[]
value=[]
for i in range(N):
    n,m=map(int,input().split())
    weight.append(n)
    value.append(m)
    
dp = [0]*(W+1); 

for i in range(N): 
    for j in range(W,weight[i],-1): 
        dp[j] = max(dp[j] , value[i] + dp[j-weight[i]])
print(dp[W])

Submission status: Runtime Error

Solution code:

N,W=map(int,input().split())
weight=[]
value=[]
for i in range(N):
    n,m=map(int,input().split())
    weight.append(n)
    value.append(m)
# print(solve(N-1,W,weight,value))
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 weight[i-1]<=j:
            dp[i][j]=max(dp[i-1][j-weight[i-1]]+value[i-1],dp[i-1][j],dp[i][j-weight[i-1]]+value[i-1])
        else:
            dp[i][j]=dp[i-1][j]
    # print(dp[i])
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:



N,W=map(int,input().split())
weight=[]
value=[]
for i in range(N):
    n,m=map(int,input().split())
    weight.append(n)
    value.append(m)
# print(solve(N-1,W,weight,value))
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 weight[i-1]<=j:
            dp[i][j]=max(dp[i-1][j-weight[i-1]]+value[i-1],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
    # print(dp[i])
print(dp[-1][-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)
dp = [[0]*(W+1) for _ in range(N+1)]

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

print(dp[N][W])

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+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i+w],dp[i]+v)
print(max(dp))

Submission status: Runtime Error

Solution code:
from requests import api

n,W = map(int,input().split())
w,v = [],[]
for i in range(n):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
sv = sum(v)
INF = float("INF")
dp = [[INF]*sv for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(sv):
        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])
    #print(dp)
ans = 0
for i in range(sv):
    #print(dp[n][i])
    if dp[n][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Runtime Error

Solution code:
from requests import api

n,W = map(int,input().split())
w,v = [],[]
for i in range(n):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
sv = sum(v)
INF = float("INF")
dp = [[INF]*sv for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(sv):
        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])
    #print(dp)
ans = 0
for i in range(sv):
    print(dp[n][i])
    if dp[n][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

s_val = sum([v for w, v in knap])
    
INF = float("inf")
dp = np.full(s_val+1, INF)

for i, (w, v) in enumerate(knap):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
    
print(max([i for i in range(s_val+1) if dp[i] <= W]))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

ans=[[0]*(W+1) for _ in range(n)]

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

print(ans[-1][W])

Submission status: Runtime Error

Solution code:
#問題D
#これだとタイムアウト
import numpy as np
import warnings
warnings.filterwarnings('ignore')

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

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])

Submission status: Runtime Error

Solution code:
#問題D
#これだとタイムアウト
import numpy as np
import warnings
warnings.filterwarnings('ignore')

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

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

Submission status: Runtime Error

Solution code:
import warnings
warnings.filterwarnings('ignore')
import numpy as np

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

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(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())
    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, dtype = np.int64)

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

print(dp.max())

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

    print(dp.max())

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
def knapsack(N,W,w,v):
    dp = [[0]*(W+1) for _ in range(N)]
    
    for i in range(N):
        for j in range(W+1):
            if j-w[i]>=0:
                dp[i][j] = max(dp[i-1][j],v[i]+ dp[i-1][j-w[i]])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[N-1][W]

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())

print(knapsack(N,W,w,v))

Submission status: Runtime Error

Solution code:
import numpy as np

n,W=list(map(int,input().split()))

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

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

Submission status: Runtime Error

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

# Input#
# n = int(input())
n, tar_w = map(int, input().split())

w = [-1]
v = [-1]

memo = [[-1] * (tar_w + 1) for i in range(n + 1)]

for i in range(tar_w + 1):
    memo[0][i] = 0


def dp(n, tar_w):
    if memo[n][tar_w] == -1:
        if tar_w < w[n]:
            memo[n][tar_w] = dp(n - 1, tar_w)
        else:
            memo[n][tar_w] = max(dp(n - 1, tar_w), dp(n - 1, tar_w - w[n]) + v[n])
    return memo[n][tar_w]


for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)

for i in range(n):
    ans = dp(i,tar_w)

ans = dp(n, tar_w)

print("{}".format(ans))

Submission status: Runtime Error

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

# Input#
# n = int(input())
n, tar_w = map(int, input().split())

w = [-1]
v = [-1]

memo = [[-1] * (tar_w + 1) for i in range(n + 1)]

for i in range(tar_w + 1):
    memo[0][i] = 0


def dp(n, tar_w):
    if memo[n][tar_w] == -1:
        if tar_w < w[n]:
            memo[n][tar_w] = dp(n - 1, tar_w)
        else:
            memo[n][tar_w] = max(dp(n - 1, tar_w), dp(n - 1, tar_w - w[n]) + v[n])
    return memo[n][tar_w]


for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)


ans = dp(n, tar_w)

print("{}".format(ans))

Submission status: Runtime Error

Solution code:
a = [int(x) for x in input().split()]
weight = a[1]
dp = [0] * weight + [0]
for x in range(a[0]):
    b = [int(x) for x in input().split()]
    for x in range(weight, b[0] - 1, -1):
        dp[x] = max(dp[x], dp[x - b[0]] + b[1])
print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

#　繰り返し回数節約
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    dp[i][wv[i-1][0]:] = np.maximum(dp[i-1][wv[i-1][0]:],dp[i-1][:W+1-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        for j in range(V_max):
            jv = j + V[i]
            if jv < V_max:
                dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            return j
    return -1


print(solve(N, W_max, W, V))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


import numpy as np
LL = np.longlong
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


@njit('i8(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        for j in range(V_max):
            jv = j + V[i]
            if jv < V_max:
                dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            return j
    return -1


print(solve(N, W_max, W, V))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


import numpy as np
LL = np.longlong
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        for j in range(V_max):
            jv = j + V[i]
            if jv < V_max:
                dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            return j


print(solve(N, W_max, W, V))

Submission status: Runtime Error

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

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = []
for i in range(N):
    wv.append(list(map(int,input().split())))
    
#- dp[i][j] i番目より後ろの品物から、重さjまで許して荷物を入れた時の価値の最大
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N-1,-1,-1):#N番目以降は品物がもうないので0。→N-1からやる
    for j in range(W,-1,-1): #重いほうから見ていく
        if j<wv[i][0]:#i番目の荷物の重さがそもそも許容値よりも大きい→いれられない
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-wv[i][0]]+wv[i][1])#いれない or いれる　の大きいほう
#最後の出力は、0番目以降の品物(つまり、全部)から、重さWまで許したときの価値の最大
print(dp[0][W])

Submission status: Runtime Error

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

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

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

print(dp.max())

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(n):
  a,b=map(int,input().split())
  wi+=[a]
  vi+=[b]
  
dp=[[0]*(w+1) for i in range(n+1)]

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

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())

weights = [0]*n
values = [0]*n

for i in range(n):
    weights[i], values[i] = map(int, input().split())

v = sum(values)

dp = [[float('inf') for _ in range(v+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(1, v+1):
        if v[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(w[i] + dp[i-1][j-v[i]], dp[i-1][j])

for j in range(v+1):
    if dp[-1][j] == w:
        print(j)

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 w_lim in range(W+1):
        if w <= w_lim:
            dp[i+1][w_lim] = max(dp[i][w_lim-w]+v, dp[i][w_lim])
        else:
            dp[i+1][w_lim] = dp[i][w_lim]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
ans = [0]*(w+1)
for i in range(n):
    wht, val = map(int, input().split())
    for j in range(0, ((w-wht)+1))[::-1]:
        #print(j, wht, val, ans)
        ans[j+wht]=max(ans[j+wht], ans[j]+val)
print(max(ans))

Submission status: Runtime Error

Solution code:
#Same code for 2
import numpy as np
n, w = map(int, input().split())
wht = []
val = []
for i in range(n):
    a, b = map(int, input().split())
    wht.append(a)
    val.append(b)
ans = np.array([[0]*(w+1)]*n, dtype=int)
#print(ans)
for i in range(0, n):
    for j in range(0, w+1):
        #print(j, i, ans)
        if i==0:
            (ans[i])[j]=0   
        if True:
            if j<wht[i]:
                (ans[i])[j]=np.int64(ans[i-1][j])
            else:
                xxx = val[i]
                yyy = int(ans[i-1][j-wht[i]])
                ##print(xxx+yyy, type(xxx), type(yyy))
                ##print(True,"sum=", val[i]+(ans[i-1][j-wht[i]]), ans[i-1][j], ans[i-1][j-wht[i]], val[i])
                #print(max(xxx+yyy,int(ans[i-1][j])))
                ans[i][j] = np.int64(max(xxx+yyy,int(ans[i-1][j])))
print(ans[-1][-1])

Submission status: Runtime Error

Solution code:
#Same code for 2
import numpy as np
n, w = map(int, input().split())
wht = []
val = []
for i in range(n):
    a, b = map(int, input().split())
    wht.append(a)
    val.append(b)
ans = np.array([[0]*(w+1)]*n, dtype=np.int64)
#print(ans)
for i in range(0, n):
    for j in range(0, w+1):
        #print(j, i, ans)
        if i==0:
            (ans[i])[j]=0   
        if True:
            if j<wht[i]:
                (ans[i])[j]=np.int64(ans[i-1][j])
            else:
                xxx = val[i]
                yyy = int(ans[i-1][j-wht[i]])
                ##print(xxx+yyy, type(xxx), type(yyy))
                ##print(True,"sum=", val[i]+(ans[i-1][j-wht[i]]), ans[i-1][j], ans[i-1][j-wht[i]], val[i])
                #print(max(xxx+yyy,int(ans[i-1][j])))
                ans[i][j] = np.int64(max(xxx+yyy,int(ans[i-1][j])))
print(ans[-1][-1])

Submission status: Runtime Error

Solution code:
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = np.zeros(w+1)

for w, v in wv:
    dp[w:] = np.maximum(dp[:-w]+v,dp[w:])
print(int(dp[-1]))

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
L = [0]*(W+1)
for i in range (N):
  X,Y = map(int, input().split())
  for j in range (W,X-1,-1):
    L[j] = max(L[j], L[j-X] + Y)
print(max(L))

Submission status: Runtime Error

Solution code:

#Atcoder#D - Knapsack 1
#{TLE -4 passed} due to python 
n,cap = list(map(int,input().split()))
dp = [0]*(cap+1)
for _ in range(n):    
    weight,value = list(map(int,input().split()))
    for j in range(cap-weight,-1,-1):
        dp[j+weight] = max(dp[j+weight],dp[j]+value)    
print(dp[-1])

Submission status: Runtime Error

Solution code:
#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

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

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

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])

Submission status: Runtime Error

Solution code:
def main():
    n, w = [int(x) for x in input().split()]
    itens = []
    dp = [[-1]*w for i in range(n)]
    
    for _ in range(n):
        itens.append([int(x) for x in input().split()])#item([peso, valor])

    print(knapsack(n, w, itens, dp))

def knapsack(n, w, itens, dp):

    if n == 0 or w == 0:
        return 0

    if dp[n-1][w-1] != -1:
        return dp[n-1][w-1]

    if itens[n-1][0] > w:
        dp[n-1][w-1] = knapsack(n-1, w, itens, dp)
        return dp[n-1][w-1]

    else:
        dp[n-1][w-1] = max(itens[n-1][1] + knapsack(n-1, w - itens[n-1][0], itens, dp),
                           knapsack(n-1, w, itens, dp))

        return dp[n-1][w-1]

main()