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):
def knapsack(n, W, w, v):
  dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
  for i in range(n+1):
    for j in range(W+1):
      if(i==0 or j==0):
        dp[i][j] = 0
      elif(w[i-1]<=j):
        dp[i][j] = max(v[i-1]+dp[i-1][j-w[i-1]], dp[i-1][j])
      else:
        dp[i][j] = dp[i-1][j]
  return dp[n][W]


n, W = map(int, input().split())
we = []
va = []
for i in range(n):
  w, v = map(int, input().split())
  we.append(w)
  va.append(v)
print(knapsack(n, W, we, va))

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

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

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


w = li[0][0]
if w<=W:
    dp[0][w]= li[0][1]

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

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

Solution (Python):
import sys

if __name__ == "__main__":
    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 = [[0]*(w+1) for i in range(n+1)]
    for i in range(n+1):
        for j in range(w+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif W[i-1] <= j:
                dp[i][j] = max(dp[i-1][j-W[i-1]]+V[i-1],dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[-1][-1])

Solution (Python):
from collections import Counter
import math
from collections import Counter
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")




import bisect

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][W]


n, c = map(int, input().split())
w = []
v = []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
print(knapSack(c, w, v, n))

Solution (Python):






import sys
input = sys.stdin.readline


import heapq 
import copy
import math
import decimal











 



 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 
 

def pr_list(a):
	print(*a, sep=" ")
def main():
	
	tests = 1
	mod = 998244353
	limit = 10**18
	ans = 0
	for test in range(tests):
		[n,w] = inlt()
		val = []
		for i in range(n):
			a = inlt()
			val.append(a)
		dp = [[-1 for i in range(w+3)]for j in range(2)]
		dp[0][0] = 0
		ans = 0
		for i in range(n):
			
			for j in range(w+3):
				dp[(i+1)%2][j] = max(dp[(i+1)%2][j],dp[(i)%2][j])
				if dp[i%2][j] != -1 and j + val[i][0]<=w:
					dp[(i+1)%2][j+val[i][0]] = max(	dp[(i)%2][j+val[i][0]] , 	dp[(i)%2][j] + val[i][1])
					ans = max(ans,dp[(i+1)%2][j+val[i][0]] )
		print(ans)

if __name__== "__main__":
	main()

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

Solution (Python):
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = [[0]*(W+1)for _ in range(N+1)]
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                dp[i+1][j] = max(dp[i+1][j],dp[i][j-w[i]] + v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
            
    print(dp[N][W])

Solution (Python):
n,w=[int(x) for x in input().split()]
dp=[0]*(w+1)
lw=w
for test in range(n):
    cw, v = [int(x) for x in input().split()]
    temp=[0]*(w+1)
    for i in range(1,w+1):
        if cw <= i :
            temp[i]=max(dp[i],v+dp[i-cw])
        else:
            temp[i]=max(dp[i],temp[i-1])
    dp=temp[:]
    
print(dp[w])

Solution (Python):
def knapsackBottomUp(wt,price,c,n):
    dp=[[0 for x in range(c+1)] for y in range(n+1)]
    for i in range(n+1):
        for w in range(c+1):
            if i==0 or w==0:
                dp[i][w]=0
            else:
                inc=exc=0
                if wt[i-1]<=w:
                    inc=price[i-1]+dp[i-1][w-wt[i-1]]
                exc=dp[i-1][w]
                dp[i][w]=max(inc,exc)
    
    return dp[n][c]
  
n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
print(knapsackBottomUp(wt,price,c,n))

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

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

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


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

print(dp[W])

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

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

print(dp[N][W])

Solution (Python):
import numpy as np

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

Solution (Python):
n, w = map(int,input().split())
weight = []
value = []
for i in range(n):
    x, y = map(int,input().split())
    weight.append(x)
    value.append(y)

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

omosa = 0

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

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

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


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

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

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


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

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 w[i] <= j:
            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])

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

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

print(dp[N][W])

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

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

Solution (Python):



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

dp = [0] * (W+1) 

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

Solution (Python):



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

dp = [0] * (W+1) 

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

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

dp = [0] * (W+1)

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

Solution (Python):

def knapsack1(N,W,weight,value):
    inf = float("inf")
    DP = [[-inf]*(W+1) for i in range(N+1)]
    for i in range(W+1): DP[0][i]=0

    for i in range(N):
        for j in range(W+1):
            if j-weight[i] >= 0:
                DP[i+1][j] = chmax(DP[i][j],DP[i][j-weight[i]]+value[i])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
    return DP[N][W] 

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

if __name__ == '__main__':
    N,W = map(int,input().split())
    weight = [0]*N
    value = [0]*N
    
    for i in range(N):   
        lst = list(map(int,input().split()))
        
        weight[i] = lst[0]
        value[i] = lst[1]
        
    
    ans = knapsack1(N,W,weight,value)
    print(ans)

Solution (Python):

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




weight=[0]*110
value=[0]*110

S = [[0 for j in range(3)] for i in range(100010)]
DP= [[0 for j in range(100100)] for i in range(110)]

for i in range(N):
    A,B=map(int,input().split())
    weight[i]=A
    value[i]=B
    
for i in range(N):
    for w in range(W+1):
        if w>=weight[i]:
            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 numpy as np
 
N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = np.maximum(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )

print(dp[N][W])

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

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(1,n+1):
  wi,vi=map(int,input().split())
  for wb in range(w+1):
    if wb < wi:
      dp[i][wb] = dp[i-1][wb]
    else:
      dp[i][wb] = max(dp[i-1][wb],dp[i-1][wb-wi]+vi)
print(dp[n][w])

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

from collections import defaultdict

dp = defaultdict(int)

dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for k, val in list(dp.items()):
        if k+w <= W:
            dp[k+w] = max(dp[k+w], val+v)



print(max(dp.values()))

Solution (Python):
import numpy as np
def resolve():
	
	N, W = map(int, input().split())
	
	dp = np.empty((N+1, W+1), dtype=np.int64)
	
	dp[0,:] = 0
	for i in range(N):
		w_n, v_n = map(int, input().split())
		dp[i+1, :w_n] = dp[i, :w_n]
		dp[i+1, w_n:] = np.maximum(
			dp[i, w_n:],
			dp[i, :(W+1-w_n)] + v_n
		)
	print(dp[N, W])
resolve()

Solution (Python):
import numpy as np

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

Solution (Python):



import numpy as np

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


    print(dp[W])

if __name__ == '__main__':
    main()

Solution (Python):



import numpy as np

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


    print(dp[N][W])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections as cc
input = sys.stdin.readline
I=lambda:list(map(int,input().split()))
n,w=I()
val=[]
wt=[]
for i in range(n):
	x,y=I()
	wt.append(x)
	val.append(y)
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 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):
N,W=map(int,input().split())
dp=[ [0]*(W+1) for i in range(N+1) ]

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

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

Solution (Python):
n,w=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
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):
        if wt[i-1]<=j:
            dp[i][j]=max(value[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):
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))

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

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

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

Solution (Python):
import sys
import math
from  collections import defaultdict





def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = map(int, input().split())
	dp = [[0 for j in range(w + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			dp[i][j] = dp[i - 1][j]
			if wgt[i - 1] <= j:
				dp[i][j] = max(dp[i][j], val[i - 1] + dp[i - 1][j - wgt[i - 1]])
	ans = dp[-1][-1]
	print(ans)



if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Solution (Python):
n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [max(dp[sum_w], dp[sum_w - w] + v) for sum_w in range(w, W+1)]
    dp[w:] = tmp_dp
print(dp[-1])

Solution (Python):
n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [max(dp[sum_w], dp[sum_w - w] + v) for sum_w in range(w, W+1)]
    dp[w:] = tmp_dp
print(max(dp))

Solution (Python):

n, w = [int(i) for i in input().split()]
weights = []
value = []
for _ in range(n):
    x, y = [int(i) for i in input().split()]
    weights.append(x)
    value.append(y)
dp = [[0 for i in range(w+1)] for j in range(n)]
for i in range(n):
    for j in range(1, w+1):
        if weights[i] <= j:
            dp[i][j] = max(value[i] + dp[i-1][j-weights[i]],dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
print(dp[-1][-1])

Solution (Python):
n,w = map(int,input().split())
inf = float("inf")
dp = [[-inf]*(w+1) for _ in range(n+1)]
for j in range(w+1):
    dp[0][j] = 0
for i in range(n):
    s,t = map(int,input().split())
    for l in range(w+1):
        if l-s >=0:
            dp[i+1][l] = max(dp[i][l],dp[i][l-s]+t)
        else:
            dp[i+1][l] = dp[i][l]
print(dp[-1][w])

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

dp = [[0] * (NW[1]+1) for i in range(NW[0]+1)]
for i in range(NW[0]+1):
    for sum_w in range(NW[1]+1):
            try:
                if (sum_w - wv[i][0])>=0:
                    dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-wv[i][0]] + wv[i][1])
                dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
            except:
                continue

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

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

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

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

dp=np.array([[0]*(W+1) for _ in range(N+1)],dtype='int64')

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

    if w<=W:
        dp[i][w:]=np.maximum(dp[i-1][w:],dp[i-1][:W-w+1]+v)
        dp[i][:w]=dp[i-1][:w]
    else:
        dp[i]=dp[i-1]

print(dp[N][W])

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

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

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

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

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

print(dp[N][W])

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

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    p = {}
    for j in DP:
        if j+wi <= W and DP.get(j+wi, 0) < DP[j]+vi:
            p[j+wi] = DP[j]+vi
    for pi in p:
        DP[pi] = p[pi]
print(max((DP[x] for x in DP)))

Solution (Python):

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

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    DP_dst = DP.copy()
    for j in DP:
        if j+wi <= W:
            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)
    DP = DP_dst
print(max((DP[x] for x in DP)))

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

print(dp[N][W])

Solution (Python):
import numpy as np

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

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

print(dp.max())

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


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


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

print(dp[n][w])

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

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

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

print(dp[n][w])

Solution (Python):
def e():
    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]+v, dp[w:], out=dp[w:])

    print(dp[-1])



if __name__ == "__main__":
    e()

Solution (Python):
def e():
    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]+v, dp[w:], out=dp[w:])

    print(dp[-1])



if __name__ == "__main__":
    e()

Solution (Python):
def main():
    def solve(N, W, wv):
        dp = [-1] * (W+1)
        dp[0] = 0

        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]

            for j in range(W-wi, -1, -1):
                if dp[j] == -1:
                    continue
                if dp[j+wi] < dp[j] + vi:
                    dp[j+wi] = dp[j] + vi

        return max(dp)

    N, W = map(int, input().split())
    wv = tuple(tuple(map(int, input().split())) for i in range(N))
    print(solve(N, W, wv))


if __name__ == "__main__":
    main()

Solution (Python):
def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

Solution (Python):

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

weights = []
profits = []

for i in range(n):
    x, y = map(int, input().split())
    weights.append(x)
    profits.append(y)

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

        if weights[i-1] <= j:
            dp[i][j] = max(dp[i-1][j], profits[i-1] + dp[i-1][j-weights[i-1]])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])

Solution (Python):
def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

Solution (Python):
n,w=map(int,input().split())
dp=[-1]*(w+1)
dp[0]=0
for _ in range(n):
  a,d=map(int,input().split())
  for b in range(w,a-1,-1):
    if dp[b-a]!=-1:
    	dp[b]=max(dp[b],d+dp[b-a])
print(max(dp))

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

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

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

Solution (Python):
n,w=map(int,input().split())
wv=[]
for i in range(n):
    wv.append(tuple(map(int,input().split())))
dp=[[0]*(w+1) for _ in range(n+1)]
for i in range(1,n+1):
    wei,val=wv[i-1]
    for j in range(1,w+1):
        if 0<=j-wei<=w:
            dp[i][j]=max(dp[i-1][j], dp[i-1][j-wei]+val)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

Solution (Python):
n,w = map(int, input().split())
high = [0] * (w + 1)
for i in range(n):
    weight, value = map(int, input().split())
    if weight <= w:
        renewal = high[:weight]
        renewal += [max([j+value, k]) for j,k in zip(high[:w-weight+1], high[weight:])]
        high = renewal
print(high[w])

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

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

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

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

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

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

print(dp[N][W])

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

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

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

print(max(dp[-1]))

Solution (Python):
from sys import stdin
import numpy as np
def main():
    
    readline=stdin.readline
    inf=10**12
    n,max_w=map(int,readline().split())
    w=[0]*n
    v=[0]*n
    for i in range(n):
        w[i],v[i]=map(int,readline().split())

    dp=np.full((n+1,max_w+1),-inf,dtype=np.int64)
    dp[0][0]=0
    for i in range(n):
        dp[i+1,:w[i]]=dp[i,:w[i]]
        dp[i+1,w[i]:]=np.maximum(dp[i,w[i]:],dp[i,:max_w-w[i]+1]+v[i])

    print(dp[n].max())

if __name__=="__main__":
    main()

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

w = []
v = []

for x in range(n):
    peso,valor = map(int,input().split())
    w.append(peso)
    v.append(valor)

dp = [0] * (W+1)

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


resposta = 0

for x in dp:
    resposta = max(x,resposta)

print(resposta)

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]*(w+1) for i in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        
        if sum_w -  weight[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]]+value[i])
        
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[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 + 1)]

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

print(dp[N][W])