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:
""""
E-Knapsack2
Wが10**9まであるのでdpの置き方を工夫する。
dp[i]:=価値がiのときのナップザックの重さ
""""
N,W = map(int,input().split())
dp = [0]+[W+1]*(N*10**3)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(N*10**3+1-v)[::-1]:
        dp[j+v] = min(dp[j+v],dp[j]+w)
for i in range(N*10**3+1)[::-1]:
    if dp[i]<=W:
        print(i)
        exit()

Submission status: Runtime Error

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

    dp = [0] * (W + 1)

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

    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)]
v_max = 10 ** 3
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]
dp[0][0] = 0

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


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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def solve(items, n, w):
    f = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = items[i-1]
        for j in range(w + 1):
            f[i][j] = f[i-1][j]
            if j >= wi:
                f[i][j] = max(f[i][j], f[i-1][j-wi] + vi)
    return f[n][w]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print(solve(items, n, 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 i in range(W,w-1,-1):
        dp[i] = max(dp[i],dp[i-w]+v)
print(dp[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

w,v=[0],[0]

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

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

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

ans=0

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

Submission status: Runtime Error

Solution code:
#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値
import math
N,W=map(int,input().split())

w,v=[0],[0]

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

dp=[[math.inf for _ in range(N*max(v)+1)] for _ in range(N+1)]
dp[0][0]=0

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import sys

import numpy as np

input = sys.stdin.readline
N, weights = map(int, input().split())

# dp = [0] * (weights + 1)
dp = np.zeros(weights + 1, dtype=np.int64)

while N:
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # for i in range(weights, -1, -1):
    #     if i - w >= 0:
    #         dp[i] = max(dp[i], dp[i - w] + v)
    # print(dp)
    N -= 1
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys

import numpy as np

input = sys.stdin.readline
N, weights = map(int, input().split())

# dp = [0] * (weights + 1)
dp = np.zeros(weights + 1, dtype=np.int64)

while N:
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # for i in range(weights, -1, -1):
        # if i - w >= 0:
            #dp[i] = max(dp[i], dp[i - w] + v)
    # print(dp)
    N -= 1
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

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

for i in range(N):
	for j in range(W+1):
		if j-w[i] >= 0:
			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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

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

for i in range(N):
	for j in range(W+1):
		if j-w[i-1] >= 0:
			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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

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

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

Submission status: Runtime Error

Solution code:
N,w = [int(x) for x in input().split()]
ll = []
for i in range(N):
    abc = [int(x) for x in input().split()]
    ll.append(abc)
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 ll[i-1][0] <= j:
            DP[i][j] = max(DP[i-1][j-ll[i-1][0]]+ll[i-1][1],DP[i-1][j])
        else:
            DP[i][j] = DP[i-1][j]
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.int)
for _ in range(N):
  w, v = map(int, input().split())
  dp[w:] = np.maximum(dp[w:], dp[:-w] + v)
print(dp[W])

Submission status: Runtime Error

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

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

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

# print(*dp, sep='\n')
print(dp[N][W])

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+1) for _ in range(n+1)]
for i in range(n):
    w_, v_ = wv[i]
    for j in range(w+1):
        if j < w_:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j-w_]+v_, dp[i][j])
print(dp[n][w])

Submission status: Runtime Error

Solution code:
#import numpy as np
from sys import stdin,stdout

input = stdin.readline
print = stdout.write

vi = [0]
wi = [0]

n,W=map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    vi.append(b)
    wi.append(a)
#print(str(vi),'\n',str(wi))
    #dp = np.zeros((n+1,MW+1),dtype=np.int64)
dp = [[0]*(W+1) for i in range(n+1)]
    
for j in range(1,n+1):
    for k in range(1,W+1):
        if(wi[j]>k) :
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = max(dp[j-1][k],dp[j-1][k-wi[j]]+vi[j])

print(str(dp[n][W]))

Submission status: Runtime Error

Solution code:
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
T=zeros(W+1,int)
exec('w,v=f();T[w:]=maximum(T[w:],T[:-w]+v);'*N)
print(T[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(n):
  l.append(list(map(int,input().split())))

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

for j in range(w+1):
  dp[0][j] = 0


def dphoi(i,j):
  #print(i,j)
  if dp[i][j] >= 0: 
    return dp[i][j]
  else:
    
    if j < l[i-1][0]:
      dp[i][:j] = dphoi(i-1,j)
      
    else:    
      dp[i][j] = max(dphoi(i-1,j),dphoi(i-1,j-l[i-1][0]) + l[i-1][1])
  
  return dp[i][j]

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

print(dphoi(n,w))
print(dp)

Submission status: Runtime Error

Solution code:
N, W = [int(i) for i in input().split()]
value, weight = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    value[i], weight[i] = [int(i) for i in input().split()]
sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

#%%

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = min(dp[i][j], weight[i] + dp[i -1][j - value[i]])
        else:
            dp[i][j] = dp[i -1][j]
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][i] == W:
        ans = i

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    MV = max(v)*N+1
    inf = float("inf")
    dp = [[inf]*MV for i in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(MV):
            if v[i] <= j:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:
                dp[i+1][j] = dp[i][j]
    ldp = dp[N]
    for i in reversed(range(MV)):
        if ldp[i] <= W:
            print(i)
            exit()

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
oj=[]
for i in range(N):
  oj.append(list(map(int,input().split())))
M=100*1001
dp=[10**10]*M
dp[0]=0
for i in range(N):
  for j in range(M,-1,-1):
    if j+oj[i][1]<M:
      k=j+oj[i][1]
      dp[k]=min(dp[k,dp[j]+oj[i][0])
v=0
for i in range(M):
  if dp[i]<=W:v=i
print(v)

Submission status: Runtime Error

Solution code:
N,W = map(int, input().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)

dp = [0] * (W+1)
for i in range(W+1):
    dp[i] = oj[0][1] if oj[0][0] <= i else 0

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

Submission status: Runtime Error

Solution code:

n ,w = map(int, input().split())

weightArr = [0] * n
valueArr = [0] * n

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

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

for i in range(n):
    for j in range(w+1):
        dp[i][j] = dp[i-1][j]
        if j >= weightArr[i]:
            dp[i][j] = max(dp[i][j],dp[i-1][j-weightArr[i]] + valueArr[i])
print(dp[-1][-1])

Submission status: Runtime Error

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

import fractions
MAX = 10**5 + 1
dp = [[fractions.inf] * MAX for i in range(N + 1)]
dp[0][0] = 0

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

ans = 0
for j in range(1, MAX):
    if dp[-1][j] <= W:
        ans = j

print(ans)

Submission status: Runtime Error

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

import math
MAX = 10**5 + 1
dp = [[math.inf] * MAX for i in range(N + 1)]
dp[0][0] = 0

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

ans = 0
for j in range(1, MAX):
    if dp[-1][j] <= W:
        ans = j

print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

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

for w, v in wv:
    for i in range(W, w - 1, -1):
        tmp = dp[i - w] + v
        if tmp > dp[i]:
            dp[i] = tmp

print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
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=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])

Submission status: Runtime Error

Solution code:
n, mw = 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] * (mw + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(mw + 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][mw])

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+w] = max(dp[j+w],dp[j] + v)
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+1)]

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

i = 1

while(True):
        for j in range(1, N+1):
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(i, dp[i][N])
        if dp[i-1][N] <= W and dp[i][N] > W:
                break
        i += 1

print(i-1)

Submission status: Runtime Error

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N, W = map(int, input().split())
    weight, value = [0] * N, [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())


    # この前段階で、荷物の数N、ウェイトの上限W、
    # weightの表weightとvalueの表valueは用意しておく。
    def knapsack(N, W, weight, value):
        dp = [[0] * (W + 1) for _ in range(N + 1)]

        for i in range(N):
            for w in range(W + 1):
                if w >= weight[i]:  # 荷物が加わる可能性がある
                    # max関数の第一引数だと、既存の荷物の方がましな場合。
                    # 第二引数だと、新入りを加えた方が良い場合。
                    dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i]] + value[i])
                else:  # 加わる可能性はない
                    dp[i + 1][w] = dp[i][w]

        return dp[N][W]

    print(knapsack(N, W, weight, value))


resolve()

Submission status: Runtime Error

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    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)
    # この前段階で、荷物の数N、ウェイトの上限W、
    # weightの表weightとvalueの表valueは用意しておく。
    def knapsack(N, W, weight, value):
        dp = [[0] * (W + 1) for _ in range(N + 1)]

        for i in range(N):
            for w in range(W + 1):
                if w >= weight[i]:  # 荷物が加わる可能性がある
                    # max関数の第一引数だと、既存の荷物の方がましな場合。
                    # 第二引数だと、新入りを加えた方が良い場合。
                    dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i]] + value[i])
                else:  # 加わる可能性はない
                    dp[i + 1][w] = dp[i][w]

        return dp[N][W]

    print(knapsack(N,W,weight,value))

resolve()

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)
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())
wv = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10**9 + 100
MAX_V = 10**5 + 100
dp = [INF] * (MAX_V + 1)
dp[0] = 0

for wi, vi in wv:
	for sum_v in reversed(range(vi, MAX_V+1)):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])
#print(dp)
ans = 0
for i in range(MAX_V, -1, -1):
    if dp[i] <= w:
        print(i)
        exit()
#print(ans)

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
elems = []
for _ in range(n):
    elems.append(list(map(int, input().split())))
inf = 10**9
res = [inf] * (w + 1)
res[0] = 0

for item in elems:
    for j in range(w, item[0] - 1, -1):
        res[j] = min(res[j], res[j - item[0]] + item[1])

print(res[-1])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
elems = []
for _ in range(n):
    elems.append(list(map(int, input().split())))
inf = 10**9
res = [inf] * w
res[0] = 0

for item in elems:
    for j in range(w, item[0] - 1, -1):
        res[j] = min(res[j], res[j - item[0]] + item[1])

print(res[-1])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
elems = []
for _ in range(n):
    elems.append(list(map(int, input().split())))
res = [float('-inf')] * w
res[0] = 0

for item in elems:
    for j in range(w, item[0] - 1, -1):
        res[j] = max(res[j], res[j - item[0]] + item[1])

res = res[-1] if res[-1] != float('-inf') else 0
print(res)

Submission status: Runtime Error

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

dp = [[float('inf') for _ in range(total_v+1)] for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Runtime Error

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

dp = [[float('inf') for _ in range(total_v+1)] for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(n)]

total_v = sum(nums[i][1] for i in range(n))
dp = [[float('inf') for _ in range(total_v+1)] for _ in range(n)]
dp[0][0] = 0

for i in range(1, n+1):
  for j in range(total_v+1):
    if j < nums[i-1][1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-nums[i-1][1]] + nums[i-1][0])
for i in range(total_v, -1, -1):
  if dp[n][i] != float('inf') and dp[n][i] <= w:
    print(i)
    break

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(n)]

total_v = sum(nums[1])
dp = [[float('inf') for _ in range(total_v+1)] for _ in range(n)]
dp[0][0] = 0

for i in range(1, n+1):
  for j in range(total_v+1):
    if j < nums[i-1][1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-nums[i-1][1]] + nums[i-1][0])
for i in range(total_v, -1, -1):
  if dp[-1][i] <= w:
    print(i)
    break

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
import numpy as np
 
def main():
  n, W = map(int, input().split())
  dp = np.zeros(W+1, dtype=np.int64)
  for _ in range(n):
    w, v = map(int, input().split())
    # 状態n,wにおいてwi,viを使うかどうかで更新する
    dp[w:W+1] = np.maximum(dp[:W-w+1]+v, dp[w:W+1])
  print(dp[W])

if __name__ == "__main__":
  main()

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.ones(N*1000+1,dtype=int)*(W+1)
DP[0]=0
for i in range(N):
    DP[v[i]:]=np.minimum(DP[:-v[i]]+w[i],DP[v[i]:])
ans=0
for k in range(N*1000+1):
    if DP[k]<=W:
        ans=k
print(ans)

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)
for i in range(N):
    DP[w[i]:]=np.maximum(DP[:-w[i]]+v[i],DP[w[i]:])
print(max(DP))

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 i in range(N+1)]

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

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    
    N, W = map(int,input().split())
    wv = [tuple(map(int,input().split())) for i in range(N)]
    dp = [0]*(W+1)
    for i in range(N):
        for j in range(W, wv[i][0]-1, -1):
            dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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())
ndp = np.zeros(W + 1, dtype=np.int64)

for w, v in zip(w, v):
    # [:w]は品物の重量がナップサックの空きよりも重いので更新しない。
    # ndp[w:] は通常DPでのdp[i][w]=dp[i-1][w]。そのままでの更新。
    # ndp[:-w] + v は[:-w]が[w-weight]に相当。
    np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])

print(ndp[-1])

Submission status: Runtime Error

Solution code:
import math
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
g = math.gcd(W, A[0][0]) 
for a in range(1, N):
	g = math.gcd(g, A[a][0])
W = W//g 
# print(g)
dp = [[0 for w in range(W+1)] for n in range(N+1)]
for i in range(W+1):
	dp[0][i] = 0
for p in range(1, N+1):
	for q in range(W+1):
		dp[p][q] = dp[p-1][q]
		if ((A[p-1][0]//g) <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - (A[p-1][0]//g)] + A[p-1][1])
# print(dp)
print(dp[N][W])