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

import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
 
    print(dp[-1])
main()

Solution (Python):

import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
 
    print(dp[-1])
main()

Solution (Python):

import sys, os
 
def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
 
    print(dp[-1])
main()

Solution (Python):

import sys, os

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]

    print(dp[-1])
main()

Solution (Python):

import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]
 
    print(dp[-1])
main()

Solution (Python):

import os


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n = inp[0]
    m = inp[1]

    wi = inp[2]
    vi = inp[3]

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()

Solution (Python):

import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Solution (Python):

import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Solution (Python):

import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

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

    print(dp[-1])
main()

Solution (Python):

import io
import os


def main():
    n, m = 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] * (m + 1)
    for i in range(w[0], m + 1):
        dp[i] = v[0]
    for i in range(n - 1):
        for j in reversed(range(w[i + 1], m + 1)):
            dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Solution (Python):
import sys
n,w=list(map(int, sys.stdin.readline().split()))
arr=[list(map(int, sys.stdin.readline().split())) for i in range(n)]

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

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


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

Solution (Python):

"""
問題
https://atcoder.jp/contests/dp/tasks/dp_d

解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
"""

def solve():
    """
    Python: TLE (´･_･`)
    """
    N, LIMIT = list(map(int, input().split()))
    W, V = [None], [None]
    for i in range(N):
        w, v = list(map(int, input().split()))
        W.append(w)
        V.append(v)
    
    
    dp = [[w for w in range(LIMIT+1)] for i in range(N+1)]
    for w in range(LIMIT+1):
        dp[0][w] = 0
    
    
    for i in range(1, N+1):
        for w in range(LIMIT+1):
            if w-W[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i])
            else:
                dp[i][w] = dp[i-1][w]

    ans = 0
    for w in range(LIMIT+1):
        ans = max(ans, dp[N][w])

    print(ans)


if __name__ == "__main__":
    solve()

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


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

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

    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:])
print(dp[-1])

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


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

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

print(dp[-1])

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

Solution (Python):
import numpy as np

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

print(dp[N,:].max())

Solution (Python):
n,W=map(int,input().split())
wei=[]
val=[]
for _ in range(n):
    x,y=map(int,input().split())
    wei.append(x)
    val.append(y)
dp=[[0 for p in range(W+1)] for q in range(n+1)]
for i in range(n):
    for w in range(W+1):
        if wei[i]<=w:
            dp[i+1][w]=max(dp[i][w-wei[i]]+val[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[n][W])

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

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


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

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

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

n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=np.zeros(W+1,dtype="i8")
for w,v in wv:
    np.maximum(dp[w:],dp[:W+1-w]+v,out=dp[w:])
print(dp[-1])

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

def f(n,W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [-1] * (W + 1)
    dp[0] = 0
    for w, v in wv:
        for i in range(W - w, -1, -1):
            if dp[i] == -1: continue
            nv = dp[i] + v
            if nv > dp[i + w]:
                dp[i + w] = nv
    print(max(dp))

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

Solution (Python):
n,W=map(int,input().split())
w_list=[0]
v_list=[0]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
dp=[]
for i in range(n+1):
    sub_list=[]
    for j in range(W+1):
        sub_list.append(0)
    dp.append(sub_list)
for i in range(1,n+1):
    for j in range(W+1):
        if j>=w_list[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_list[i]]+v_list[i])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][W])

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

import numpy as np
ndp = np.zeros(W+1,dtype= np.int64)
for w,v in zip(w,v):
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])

Solution (Python):

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

dp = [[None for __ in range(M+1)] for _ in range(N+1)]
dp[0] = [0 for _ in range(M+1)]
for i in range(1, N+1):
    for w in range(M+1):
        if W[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1])
        else:
            dp[i][w] = dp[i-1][w]


print(max(dp[-1]))

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

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

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

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

Solution (Python):
import numpy as np

def main():
    num, weigh = map(int, input().split())
    dp = np.zeros((num + 1, weigh + 1), dtype=int)

    for i in range(1, num + 1):
        now_weigh, now_value = map(int, input().split())
        dp[i, :now_weigh] = dp[i - 1, :now_weigh]
        dp[i, now_weigh:] = np.maximum(dp[i - 1, :weigh - now_weigh + 1] + now_value, dp[i - 1, now_weigh:])

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

def main():
    num, weigh = map(int, input().split())
    dp = [defaultdict(int) for i in range(num + 1)]
    dp[0][0] = 0

    for i in range(1, num + 1):
        data = list(map(int, input().split()))
        for pre_value in dp[i - 1].keys():
            dp[i][pre_value] = max(dp[i - 1][pre_value], dp[i][pre_value])
            if pre_value + data[0] <= weigh:
                dp[i][pre_value + data[0]] = max(dp[i - 1][pre_value] + data[1], dp[i][pre_value + data[0]])

    print(max(list(dp[-1].values())))


if __name__ == '__main__':
    main()

Solution (Python):
n,W=map(int,input().split())
w_list=[]
v_list=[]
dp=[]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range(n):
    dp_sub=[]
    for j in range(W+1):
        dp_sub.append(-1)
    dp.append(dp_sub)
dp_sub=[]
for j in range(W+1):
    dp_sub.append(0)
dp.append(dp_sub)
for i in range(n):
    i_=n-1-i
    for j in range(W+1):
        if w_list[i_]<=j:
            dp[i_][j]=max(dp[i_+1][j],dp[i_+1][j-w_list[i_]]+v_list[i_])
        else:
            dp[i_][j]=dp[i_+1][j]
print(dp[0][W])

Solution (Python):
dp = [[0] * 100100 for i in range(110)]

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

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

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] * (W+1) for _ in range(N+1)]

for n in range(1, N+1):
    weigh = weight[n-1]
    val = value[n-1]
    for w in range(W+1):
        if w < weigh:
            dp[n][w] = dp[n-1][w]
        else:
            dp[n][w] = max(dp[n-1][w], 
                        dp[n-1][w-weigh] + val)
        

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

Solution (Python):
import numpy as np
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] = dp[i-1, :w]
    dp[i, w:] = np.maximum(dp[i-1, :W-w+1] + v, dp[i-1, w:])

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

Solution (Python):



import numpy as np

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

dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().rstrip().split(' '))
    dp[w:] = np.max(np.vstack([dp[w:], dp[:-w] + v]), axis=0)
    
    
print(int(max(dp)))

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

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

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

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

Solution (Python):
N,W=map(int,input().split())
from collections import*
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    for k,b in d.copy().items():
        if k+w<=W:
            d[k+w]=max(d[k+w],b+v)
print(max(d.values()))

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

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]



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

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

print(dp[N][W])

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

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


DP = [0]*(W+1) 




for i in range(0, N, 1): 
  w, v = wv[i]
  
  
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))

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

n,w=map(int,input().split())
dp=[0]*(w+1)
c,p=map(int,input().split())
dp[c]=p

def ans(n,w):
  for _ in range(1,n):
    c,p=map(int,input().split())
    for j in range(w,c,-1):
      if dp[j-c] != 0 and dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
    if dp[c] < p:
      dp[c]=p
  return max(dp)
print(ans(n,w))

Solution (Python):
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(int(dp[-1]))

Solution (Python):
N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])

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

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

Solution (Python):

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(int(dp[-1]))

Solution (Python):
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(int(dp[-1]))

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


from collections import defaultdict
dp = defaultdict(int)
dp[0]=0

for wv in wvList:
    w,v = wv
    tp = defaultdict(int,{ i[0]+w : i[1]+v  for i in dp.items() if i[0]+w<=W})
    for i in set(list(dp.keys())+list(tp.keys())):
        dp[i] = max(dp[i],tp[i])

print(max(dp.values()))

Solution (Python):
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""

def solve(wv_pairs):
    dp = [0] * (W + 1)
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for ww in range(W, w_i - 1, -1):
            dp[ww] = max(dp[ww], dp[ww - w_i] + v_i)
    return max(dp)


N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)

Solution (Python):
import sys

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

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, sys.stdin.readline().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(DP[j - w] + v if element < DP[j - w] + v else element)
        else:
            dp.append(element)
    DP = dp

print(max(DP))

Solution (Python):
import numpy as np

N, W = map(int, input().split())
INF = -10 ** 12


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

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

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

Solution (Python):
def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))

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

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

Solution (Python):
import numpy as np
import sys
input = sys.stdin.readline
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])

Solution (Python):
n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
DP=[[0 for i in range(w_max+1)] for j in range(n)]
for i in range(w_max+1):
  if i>=W[0]:
    DP[0][i]=V[0]
for i in range(1,n):
  for j in range(w_max+1):
    if j>W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    elif j==W[i]:
      DP[i][j]=max(DP[i-1][j],V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(DP[n-1][w_max])

Solution (Python):
from sys import stdin
import numpy as np


def dp_solve(dp, lim, n):
    for i in range(n):
        w, v = map(int, input().split())
        dp[i+1][:w] = dp[i][:w]
        dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
    return np.max(dp[n])


if __name__ == "__main__":
    n, lim = map(int, stdin.readline().split())
    items = []

    dp = np.zeros((n+1, lim+1), dtype='uint64')
    print(dp_solve(dp, lim, n))

Solution (Python):

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


dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    
    
    
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:]) 

print(dp[-1])

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

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

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

Solution (Python):
N,W = list(map(int,input().split()))
w = [0]
v = [0]

for i in range(N):
  a,b = list(map(int,input().split()))
  w.append(a)
  v.append(b)
  

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

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

print(dp[N][W])

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

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

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



costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(range(W + 1)):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print(max(costs))

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

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)


dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)



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

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)

def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)




dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    

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


print(dp[N][W])

Solution (Python):
def dp():
  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 j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())

Solution (Python):
def nap(n,cap):
    val = [0]*(cap+1)
    for _ in range(n):
        w,v = map(int,input().split())
        for k in range(cap,w-1,-1):
            nv=val[k-w]+v
            if val[k]<nv:
                val[k]=nv
    return max(val)

n,cap=map(int,input().split())
print(nap(n,cap))

Solution (Python):

"""
Created on Sat Mar 23 21:51:02 2019

@author: Yamazaki Kenichi
"""

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

ans = [[-1 for i in range(N+1)]]
ans[0][N] = 0
for i in range(1,W+1):
    tmp = -1
    maxv = ans[-1][N]

    for j in range(N):


        if i-A[j][0] >= 0 and ans[i-A[j][0]][j] == -1 and ans[i-A[j][0]][N] + A[j][1] > maxv:
            maxv = ans[i-A[j][0]][N] + A[j][1]
            tmp = j

    if tmp != -1:
        ans.append(ans[-A[tmp][0]][:])
        ans[i][tmp] = 1
    else:
        ans.append(ans[-1][:])
    ans[i][N] = maxv


print(ans[W][N])

Solution (Python):
import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))

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

Solution (Python):
N, W = map(int,input().split())
dp = [[0 for i in range(100001)] for i in range(N+1)]

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

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

print(max(dp[-1]))

Solution (Python):
import numpy as np

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

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

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

Solution (Python):
import sys

input = sys.stdin.readline

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

dp = [[0 for _ in range(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])

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

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

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

Solution (Python):
import sys
import numpy as np

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, w = nm()
lis = [nl() for _ in range(n)]
lis.insert(0, [0, 0])
dp = np.zeros(w + 1, dtype=np.int64)

for i in range(1, n + 1):
    dp[lis[i][0]:] = np.maximum(dp[lis[i][0]:], dp[:-lis[i][0]] + lis[i][1])

print(dp[-1])

Solution (Python):
from itertools import accumulate
N,W = [int(i) for i in input().split()]

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

li = [[int(i) for i in input().split()] for _ in range(N)]
dp[0][li[0][0]] = li[0][1]
dp[0] = list(accumulate(dp[0]))
for i in range(1,N):
    for j in range(W+1):
        if j < li[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-li[i][0]]+li[i][1],dp[i][j-1],dp[i-1][j])

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

Solution (Python):
import numpy as np

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

dp = np.zeros(ww+1)

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

print(int(max(dp)))

Solution (Python):
import sys

n, w = map(int, sys.stdin.readline().split())
weight = []
value = []
for i in range(n):
    wi, vi = map(int, sys.stdin.readline().split())
    weight.append(wi)
    value.append(vi)

wght = [0] * (w+1)

for i in range(n):
    for j in range(w - weight[i], -1, -1):
        wght[j + weight[i]] = max(wght[j + weight[i]], wght[j] + value[i])

print(wght[-1])

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

d = sorted(d)
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        w1, v1 = d[i]
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        if w + w1 <= W:
            dp[i + 1][w + w1] = max(dp[i + 1][w + w1], dp[i][w] + v1)


num = 0
for i in range(W + 1):
    num = max(num, dp[N][i])

print(num)

Solution (Python):


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

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

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
n, W = map(int, input().split())
dp = np.zeros(W+1,'i8')
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())
w,v = [],[]
for i in range(N):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
dp = [[0]*(W+1) for i 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[N][W])