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^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

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

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

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:
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(N)]
for i in range(W+1):
    dp[0][i] = oj[0][1] if oj[0][0] <= i else 0

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

Submission status: Accepted

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

Submission status: Accepted

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

Solution code:
def DP_D() :
    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)

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

    return max(dp[N])

print(DP_D())

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
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] <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - A[p-1][0]] + A[p-1][1])
# print(dp)
print(dp[N][W])

Submission status: Accepted

Solution code:
n,cap=map(int,input().split())
weigh=[]
profit=[]
temp=n
while temp!=0:
    w,p=map(int,input().split())
    weigh.append(w)
    profit.append(p)
    temp-=1

mat=[[0 for i in range(cap+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(1,cap+1):
        if j<weigh[i-1]:
            mat[i][j]=mat[i-1][j]
        else:
            mat[i][j]=max(profit[i-1]+mat[i-1][j-weigh[i-1]],mat[i-1][j])
print(mat[n][cap])

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

WV = [[int(x) for x in input().split()] for _ in range(N)]

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

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

# print(dp)
ans = dp[N][W]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


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


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------

if __name__ == "__main__":
    n, w = rinput()
    w_v = []
    for i in range(n):
        w_v.append(rlinput())
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    # print(w_v)
    for item in range(1, n+1):
        for weight in range(1, w+1):
            if weight >= w_v[item-1][0]:
                dp[item][weight] = max(dp[item-1][weight-w_v[item-1][0]]+w_v[item-1][1],dp[item-1][weight])
            else:
                dp[item][weight] =dp[item-1][weight]
    print(dp[n][w])

Submission status: Accepted

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

for i in range(n):
    ww, v = map(int, input().split())
    value.append(v)
    weight.append(ww)

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

for i in range(n):
    for mw in range(w + 1):
        if weight[i] <= mw:
            dp[i + 1][mw] = max(dp[i][mw], dp[i][mw - weight[i]] + value[i])
        else:
            dp[i + 1][mw] = dp[i][mw]

print(dp[n][w])

Submission status: Accepted

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())
# the max value with less than or equal to j weight
dp = [0] * (W+1)
for i in range(N):
    for j in range(w[i], W+1)[::-1]:
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])
print(dp[W])

Submission status: Accepted

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

Submission status: Accepted

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

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]
 
dp = [0] * (w+1)
for wi, vi in wv:
    for sum_w in reversed(range(wi, w+1)):
        dp[sum_w] = max(dp[sum_w], dp[sum_w - wi] + vi)
print(dp[w])

Submission status: Accepted

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

print(res[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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())
    # w, vを使うかどうかで更新する
    dp[w:W+1] = np.maximum(dp[:W-w+1]+v, dp[w:W+1])
  print(dp[W])

if __name__ == "__main__":
  main()

Submission status: Accepted

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

    # この前段階で、荷物の数、ウェイトの上限、weightと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: Accepted

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

Solution code:
inp = list(map(lambda x: int(x), input().split(" ")))
n = inp[0]
w = inp[1]
inp = []
for i in range(n):
    inp.append(list(map(lambda x: int(x), 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>=inp[i][0]):
            dp[i+1][j] = max(dp[i][j], dp[i][j-inp[i][0]]+inp[i][1])
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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 _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if w[i]<=j:
                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])
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/submissions/10194253
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(dp[-1]))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
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] <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - A[p-1][0]] + A[p-1][1])
# print(dp)
print(dp[N][W])

Submission status: Accepted

Solution code:
def KnapSack(val, wt, n, W): 
      
    # matrix to store final result  
    mat = [[0 for i in range(W + 1)]  
              for i in range(2)] 
    # iterate through all items  
    i = 0
    while i < n: # one by one traverse  
                 # each element  
        j = 0 # traverse all weights j <= W 
          
        # if i is odd that mean till  
        # now we have odd number of  
        # elements so we store result   
        # in 1th indexed row  
        if i % 2 == 0: 
            while j < W: # check for each value  
                j += 1
                if wt[i] <= j: # include element  
                    mat[1][j] = max(val[i] + mat[0][j - 
                                     wt[i]], mat[0][j]) 
                else: # exclude element 
                    mat[1][j] = mat[0][j] 
                      
        # if i is even that mean till  
        # now we have even number  
        # of elements so we store  
        # result in 0th indexed row  
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - 
                                     wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    # Return mat[0][W] if n is  
    # odd, else mat[1][W]  
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 
  
# Driver code
n,W = map(int,input().split())
val = [] 
wt = []  
for i in range(n):
    a,b = map(int,input().split())
    val.append(b)
    wt.append(a)
    
print(KnapSack(val, wt, n, W))

Submission status: Accepted

Solution code:
import sys

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

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

INF = (-1)*10**13

dp = [[0]*(1+W) for i in range(N+1)]
for j in range(1, W+1):
    dp[0][j] = INF
for i in range(1, N+1):
    for j in range(1, W+1):
        if j-WV[i-1][0]>=0 and dp[i-1][j-WV[i-1][0]]!=INF:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-WV[i-1][0]]+WV[i-1][1])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[N][W])

Submission status: Accepted

Solution code:
import numpy as np
n,w = map(int,input().split())
dp = np.array([0]*(w+1))

for i in range(n):
    we,va = map(int, input().split())
    dp[we:] = np.maximum(dp[we:],dp[:-we]+va)

print(int(dp[-1]))

# n = 3 w = 8
# dp [0,1,2,3,4,5,6,7,8] = [0,0,0,0,0,0,0,0]
# we = 3 va = 30
# dp[3,4,5,6,7,8] = max(dp[3,4,5,6,7,8],dp[0,1,2,3,4,5]+30)
# dp [0:9] = [0,0,0,30s,30,30,30,30,30] 
# we = 4 va = 50
# dp[4,5,6,7,8] = max(dp[4,5,6,7,8],dp[0,1,2,3,4]+50)
# dp[4,5,6,7,8] = max(dp[4,5,6,7,8],dp[0,1,2,3,4]+50)
# dp[0:9] = [0,0,0,30,50,50,50,80,80]
# we = 5 va = 60
# dp[5,6,7,8] = max(dp[5,6,7,8],dp[0,1,2,3]+60)
# dp[0:9] = [0,0,0,30,50,60,60,80,90]

Submission status: Accepted

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**11+1

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

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

print(dp[N][W])

Submission status: Accepted

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**11+1

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

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

print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    goods, weight_limit = map(int, input().split())
    good_info = [tuple(map(int, input().split())) for _ in range(goods)]
    dp = [[0 for _ in range(weight_limit + 1)] for _ in range(goods + 1)]
    for i in range(goods):
        for j in range(weight_limit + 1):
            if j >= good_info[i][0]:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - good_info[i][0]] + good_info[i][1])
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[goods][weight_limit])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
l = []
for i in range(N):
  L = list(map(int, input().split()))
  l.append(L)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(W+1):
    if j >= l[i-1][0]:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

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 i in range(n)]
for i in range(n):
    for j in range(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(dp)
print(dp[n-1][W])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,w=mii()

wei=[0]
val=[0]
for i in range(n):
    x,y=mii()
    wei.append(x)
    val.append(y)

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

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

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

Submission status: Accepted

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

print(max(dp))

Submission status: Accepted

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

print(max(dp))

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [tuple(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):
        dp[sum_w] = max(dp[sum_w], dp[sum_w - wi] + vi)
print(dp[w])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [tuple(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):
        if sum_w - wi >= 0:
            dp[sum_w] = max(dp[sum_w], dp[sum_w - wi] + vi)
print(dp[w])

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((n+1, w+1), np.int64)
for i, (wi, vi) in enumerate(wv):
    dp[i + 1] = dp[i]
    np.maximum(dp[i+1][wi:], dp[i][:-wi] + vi, out=dp[i+1][wi:])
print(dp[n, w])

Submission status: Accepted

Solution code:
dp = [[0 for _ in range(10**5+10)] for _ in range(10**2+10)]

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)

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

print(dp[N][W])

Submission status: Accepted

Solution code:

import numpy as np  

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

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

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np  

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

dp = np.zeros(w+1)

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np  

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

dp = np.zeros(w+1)

for _ in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    import sys
    input=sys.stdin.readline
    
    n,w=map(int,input().split())
    items=np.array([list(map(int,input().split())) for _ in range(n)])

    dp=np.zeros([n+1,w+1],dtype=np.int64)
    for i in range(n):
        wi=items[i][0]
        vi=items[i][1]
        dp[i+1][:wi]=dp[i][:wi]
        dp[i+1][wi:]=np.maximum(dp[i][wi:],dp[i][:-wi]+vi)
        
    print(dp[-1][-1])
 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np  

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

dp = np.zeros(w+1)

for _ in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value)

print(int(dp[-1]))

Submission status: Accepted

Solution code:
n,w = list(map(int,input().split()))
mat = [[0 for i in range(w+1)]for j in range(n+1)]
arr = []
for i in range(n):
	arr.append(list(map(int,input().split())))
for i in range(1,n+1):
	wt,val = arr[i-1][0],arr[i-1][1]
	for j in range(1,w+1):
		if j<wt:
			mat[i][j] = mat[i-1][j]
		else:
			mat[i][j] = max(mat[i-1][j-wt]+val,mat[i-1][j])
print(mat[n][w])

Submission status: Accepted

Solution code:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, wlim = list(map(int,ipti().split()))
    w = [0] * n
    v = [0] * n

    for i in range(n):
        w[i], v[i] = list(map(int,ipti().split()))

    dp = [[0] * (wlim+1) for _ in range(n+1)]

    for i in range(n):
        vcur = v[i]
        wcur = w[i]
        for j in range(wlim + 1):
            if wcur <= j:
                dp[i+1][j] = max(dp[i][j-wcur] + vcur, dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]

    print(dp[n][wlim])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque, defaultdict #要素ごとの出現回数、双方向アクセス可能データ型
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

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
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
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)
# template


def main():
    n, w = map(int, input().split())
    dp = np.zeros(w+1)

    for _ in range(n):
        weight, value = map(int, input().split())

        dp[weight:] = np.maximum(dp[weight:], dp[:-weight]+value)

    print(int(dp[-1]))

if __name__ == "__main__":
    main()