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 .

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

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

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

print(max(DP[N]))

Solution (Python):
import sys


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

N, W = IL()
v_list = [0] * N
w_list = [0] * N
v = 0
w_total = 0
for i in range(N):
	w_list[i], v_list[i] = IL()

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

print(dp[N][W])

Solution (Python):
n, m = map(int, input().split())
dp = [[0] * (m+1) for i in range(n+1)]

for i in range(n):
    w, v = map(int, input().split())
    for j in range(m+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][m])

Solution (Python):
N, W = map(int, input().split())
items = [[0, 0]]
for _ in range(N):
    items.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(W + 1):
        if j - items[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j - items[i][0]] + items[i][1], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(dp[N]))

Solution (Python):
import numpy as np

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

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

dp = np.zeros( ww+1 )
dp = dp.astype( "int64" )
for ni in range( n ):
    dp[ w[ ni ]: ] = np.maximum( dp[ w[ ni ]: ], dp[ :-w[ ni ] ]+v[ ni ] )


print( dp[ -1 ] )

Solution (Python):
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    w, v = [0 for _ in range(N)], [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = map(int, input().split())
    ans = solve(N, W, w, v)
    print(ans)


def solve(N, W, w, v):
    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 0 <=  j - w[i - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]
    
    return dp[N][W]


if __name__ == '__main__':
    main()

Solution (Python):
n, w = map(int ,input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)

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

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


print(int(dp[i][j]))

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

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

def main():
	n, W = rli()
	weight = [0 for _ in range(n)]
	val = [0 for _ in range(n)]
	for i in range(n):
		w, v = rli()
		weight[i], val[i] = w, v
	
	

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

if __name__ == "__main__":
	main()

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

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

def main():
	n, W = rli()
	weight = [0 for _ in range(n)]
	val = [0 for _ in range(n)]
	for i in range(n):
		w, v = rli()
		weight[i], val[i] = w, v
	
	

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

if __name__ == "__main__":
	main()

Solution (Python):
N,W=map(int,input().split())
listN=[[0 for i in range(W+1)] for k in range(N+1)]
for i in range(N):
  w,v=map(int,input().split())
  for k in range(1,W+1):
    if k>=w:
      listN[i+1][k]=max(listN[i][k],listN[i][k-w]+v)
    else:
      listN[i+1][k]=listN[i][k]     
ans=listN[N][W]
print(ans)

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

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

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

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] 
for i,j in itertools.product(range(1,N+1),range(W+1)):
    w,v = wv[i-1]
    if j-w>=0:
        dp[i][j] = max(dp[i][j],dp[i-1][j-w]+v)
    dp[i][j] = max(dp[i][j],dp[i-1][j])
print(dp[-1][-1])

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

Solution (Python):
n,w=map(int,input().split())
val=[0]*n
wt=[0]*n
dp=[[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n):
  a,b=map(int,input().split())
  wt[i]=a
  val[i]=b
for i in range(1,n+1):
    for j in range(1,w+1):
        if(wt[i-1] <= j):
            dp[i][j]=max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

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

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

    
    for i in range(N):
        
        for j in range(W+1):
            w, v = WV[i]
            num_w = min(1, j//w)        
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w*num_w] + v*num_w)
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Solution (Python):
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(n):
    for sum_w in range(w+1):
        
        if sum_w - W[i] >= 0:
            Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w - W[i]] + V[i])
        
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] 
for i,j in itertools.product(range(N),range(W+1)):
    w,v = wv[i]
    if j-w>=0:
        dp[i+1][j] = max(dp[i+1][j],dp[i][j-w]+v)
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])

Solution (Python):
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = np.zeros(W+1,dtype=int) 
for i in range(N):
    w,v = wv[i]
    dp[w:] = np.fmax(dp[:-w]+v,dp[w:])
print(dp[-1])

Solution (Python):
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] 
for i,j in itertools.product(range(N),range(W+1)):
    w,v = wv[i]
    if j-w>=0:
        dp[i+1][j] = max(dp[i+1][j],dp[i][j-w]+v)
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

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

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









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

print(dp[N][W])

Solution (Python):
n,ww=map(int,input().split())
waight=[0]
value=[0]
for _ in range(n):
    a,b=map(int,input().split())
    waight.append(a)
    value.append(b)
dp=[[0]*(ww+1) for _ in range(n+1)]
for i in range(n):
    for w in range(ww+1):
        if w-waight[i+1]>=0:
            dp[i+1][w]=max(dp[i][w],dp[i][w-waight[i+1]]+value[i+1])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[-1][-1])

Solution (Python):
import numpy as np

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

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

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

Solution (Python):
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    INF = 10**10  
    
    dp = [[0]*(W+1) for _ in range(N+1)]
    """
    初期化の値は，
        最小化問題：INF, 
        最大化問題：-INF（0以上の値しか取らないなら-1, あるいは0でもいいかも)
        数え上げ問題：0
        確率問題：0
        Yes/No判定問題:False
    """

    
    

    
    for typ in range(1, N+1):
        for weight in range(W+1):

            """
            dp[from] の値の更新が完了していればノード from からノード to への緩和を行っていい．貰うdpであれ配るdpであれ．
            両者の違いを意識すべきケースはcf. 
            https://qiita.com/drken/items/ace3142967c4f01d42e9

            
            """
            
            if weight-w[typ-1] >= 0:
                dp[typ][weight] = max(max(dp[typ][weight], dp[typ-1][weight-w[typ-1]]+v[typ-1]),dp[typ-1][weight])
            
            else:
                dp[typ][weight] = max(dp[typ][weight], dp[typ-1][weight])

    
    print(dp[N][W])


resolve()

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

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

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

print(dp[N][W])

Solution (Python):
import copy
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

d = [0]*(W+1)
dp = [copy.deepcopy(d) for j in range(N+1)]

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

print(dp[N][W])

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

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

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

Solution (Python):
N, W = map(int, input().split())
wt, vt = [], []
for _ in range(N):
    w, v = map(int, input().split())
    wt.append(w)
    vt.append(v)

dp = [[0] * (W + 5) for _ in range(105)]

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

print(dp[N][W])

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

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

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

Solution (Python):
import numpy as np
n,W=map(int,input().split())
w,v=[],[]
for i in range(n):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)
dp = np.zeros((n+1,W+1),dtype=np.int64)
for i in range(n):
    tmp=np.zeros(W+1,dtype=np.int64)
    tmp[w[i]:]=dp[i][:-w[i]]+v[i]
    dp[i+1]=np.maximum(dp[i],tmp)
print(dp[n][W])

Solution (Python):
import copy
n,W=map(int,input().split())
l=[0]*(W+1)
for _ in range(n):
	w,v=map(int,input().split())
	d=copy.deepcopy(l)
	for i in range(len(d)):
		if i-w>=0:
			d[i]=max(d[i],l[i-w]+v)
	l=d
	

print(l[-1])

Solution (Python):
n, w = map(int, input().split())
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[0 for j in range(w+1)]for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j-g[i][0] < 0:
            m[i+1][j] = m[i][j]
        else:
            m[i+1][j] = max(m[i][j], m[i][j-g[i][0]]+g[i][1])
print(m[n][w])

Solution (Python):
import numpy as np
n,W,*wv=map(int,open(0).read().split())
w=np.array(wv[::2])
v=np.array(wv[1::2])
dp=np.zeros([n+1,W+1],dtype=int)
for i in range(1,n+1):
  now=np.zeros(W+1,dtype=int)
  now[w[i-1]:]=dp[i-1][:-w[i-1]]+v[i-1]
  dp[i]=np.maximum(dp[i-1],now)
print(dp[-1][-1])

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

print(dp[N][W])

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

Solution (Python):



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

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

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

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

Solution (Python):
import sys
 
 
def input():
    return sys.stdin.readline().strip()
 
 
sys.setrecursionlimit(20000000)
 
 
def main():
    N, W = map(int, input().split())
    B = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        w = B[i][0]
        v = B[i][1]
        for j in range(W + 1):
            if j >= w:
                dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[-1][-1])
 
 
if __name__ == "__main__":
    main()

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

dp =[[0 for i in range(W+1)] for j in range(N+1)]
w = np.zeros(W+1)
v = [0]*N
ndp = np.zeros(W + 1, dtype=np.int64)
for i in range(N):
  w[i],v[i] =  map(int,input().split())
for i in range(N):
  ndp[w[i]:] = np.maximum(ndp[:-w[i]] + v[i], ndp[w[i]:])
print(ndp[W])

Solution (Python):
import numpy as np
n,W = [int(e) for e in input().split()]
v = np.zeros(n,dtype='int64')
w = np.zeros(n,dtype='int64')

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

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

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

print(dp[-1])

Solution (Python):
N,W=map(int,input().split())
v=[]
w=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    v.append(vv)
    w.append(ww)

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

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

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

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

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

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

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

print(max(dp[n]))

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


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


for i in range(n):
    for j in range(w+1):
        if i==0:
            if j>=wv[i][0]:
                dp[i][j]=wv[i][1]
        else:
            if j< wv[i][0]:
                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])



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

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

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

for i in range(N):
    w, v = Wl[i], Vl[i]
    for j in range(W+1):
        if j+w < W+1: dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(max(dp[N]))

Solution (Python):
import sys

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

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007



def main():
	
	n, w = IN()
	
	dp = [-1]*(w+1)
	dp[0]=0
	for _ in range(n):
		wi, vi = IN()
		for ri, v in enumerate(dp[::-1]):
			i=len(dp)-ri-1
			
			if i + wi > w:
				continue
			if dp[i] >= 0:
				dp[i + wi] = max(dp[i+wi], dp[i]+vi)
		
	ret = max(dp)
	return ret
				
			
		
	
	
	

isTest=False

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

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

Solution (Python):
import sys

input = sys.stdin.readline


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

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

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

    print(dp[N][W])

if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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

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

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

    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Solution (Python):
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])

Solution (Python):

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

Solution (Python):



import numpy as np



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


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


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

print(dp[-1])

Solution (Python):
def dynamicprogramming():
  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 - w, -1, -1):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()

Solution (Python):
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

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

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


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

Solution (Python):
import numpy as np

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


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

for i in range(n):
    tmp = np.zeros(w + 1, dtype=int)
    tmp[l[i][0]:] = dp[i][:-l[i][0]] + l[i][1]
    dp[i + 1] = np.maximum(dp[i], tmp)
    
print(dp[n][w])

Solution (Python):
import sys


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


sys.setrecursionlimit(20000000)


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


if __name__ == "__main__":
    main()

Solution (Python):

import sys

import fractions
import copy
import bisect
import math
import numpy as np
import itertools
from itertools import combinations_with_replacement


from operator import itemgetter
from sys import stdin

from operator import mul
from functools import reduce
from collections import Counter





j=0
k=0
n=3
r=1
a=[0]






"1行1つの整数を入力を取得し、整数と取得する"




"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

for i in number_list:
    print(number_list[i-1])

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
'''

'''



"正方行列にstr型の値を入力"
'''




'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"


'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''











'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''




"aという変数に入っているものを大文字にして出力"















'''
コンビネーションの組み合わせの中身を出力する形式
for i in itertools.combinations(brray, 2)
combinationsをpermutationsにすれば順列になる
今回なら(abc133B)
入力
1 2
5 5
-2 8
出力
[[1, 2], [5, 5], [-2, 8]]
もちろん一次元リストでも使えるし
何よりiもリストのように使えるので便利
'''


'''
def cmb(n,r):
    
    r= min(n-r,r)
    
    if r == 0: return 1
    over = reduce(mul, range(n, n-r, -1))
    
    
    

    under = reduce(mul, range(1, r+1))
    
    
    
    

    return over // under
    
    
    
    
a = cmb(n, r)

'''

'''
import itertools
from itertools import combinations_with_replacement

combinationについて
以下の違いを意識しよう
combinations() p, r 長さrのタプル列、ソートされた順で重複なし

combinations_with_replacement() p, r 長さrのタプル列、ソートされた順で重複あり


使用例 　　　　　　　　　　　                  出力　　
combinations('ABCD', 2)　　　　　　　　　　　　AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)　　 AA AB AC AD BB BC BD CC CD DD
'''



'''




for i in a.most_common(n):print(i)





 


'''









'''
bisect.bisect_left(a, x, lo=0, h=len(a))
引数
a: ソート済みリスト
x: 挿入したい値
lo: 探索範囲の下限
hi: 探索範囲の上限
(lo, hiはスライスと同様の指定方法)
bisect_leftはソートされたリストaに対して順序を保ったままxを挿入できる箇所を探索します。leftが示す通り、aにすでにxが存在している場合は、挿入箇所は既存のxよりも左側になります。また、lo, hiを指定することで探索範囲を絞り込むことも可能です。デフォルトはaの全体が探索対象です。
'''














def main():

    import numpy as np
    j=0
    k=0
    
    


    "1行1つの整数を入力を取得し、整数と取得する"
    
    
    "12 21 332 とか入力する時に使う"
    "1行に複数の整数の入力を取得し、整数として扱う"
    
    
    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])
    
    
    
    
    '''
    入力
    1234
    出力
    [1, 2, 3, 4]
    '''



if __name__ == "__main__":
    main()

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

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

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

Solution (Python):
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)
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(1,W+1):
        op1,op2 = 0,0
        if weight[i-1] <= j:
            op1 = value[i-1] + dp[i-1][j-weight[i-1]]
        op2 = dp[i-1][j]
        dp[i][j] = max(op1,op2)
print(dp[N][W])

Solution (Python):
n, w = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(n)]
max_w = w + 1

dp = [[float('inf')] * max_w for _ in range(n)]

for sum_w in range(max_w):
    if sum_w + items[0][0] < max_w:
        dp[0][sum_w] = items[0][1]
    else:
        dp[0][sum_w] = 0

for i in range(1, n):
    for sum_w in range(max_w):
        if sum_w + items[i][0] < max_w:
            v_0 = dp[i-1][sum_w + items[i][0]] + items[i][1]
            v_1 = dp[i-1][sum_w]
            dp[i][sum_w] = max(v_0, v_1)
        else:
            dp[i][sum_w] = dp[i-1][sum_w]
print(dp[n-1][0])

Solution (Python):
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())

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [[0]*(10**5 + 10) for _ in range(110)]






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

print(dp[N][W])

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

  wv_list.append([w,v])

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


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

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

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

print(max(n_list[-1]))

Solution (Python):
def main():
    import numpy as np
    N, W = map(int, input().split())
    ndp = np.zeros(W+1, dtype= np.int64)
    for _ in range(N):
        w, v = map(int,input().split())
        np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
    else:print(ndp[-1])

if __name__=="__main__":
    main()

Solution (Python):
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
N,W = LI()
dp = [0 for _ in range(W+1)]
for i in range(1,N+1):
    w,v = LI()
    for j in range(W,0,-1):
        if j < w: continue
        dp[j] = max(dp[j],dp[j-w]+v)
print(dp[-1])

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

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

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

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

for i in range(n):
    weight, value = goods[i]
    for sum_w in range(w + 1):
        if (sum_w - weight) >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight] + value)

        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

print(dp[n][w])