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 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):
import numpy as np
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=np.zeros(w+1,np.int64)


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

Solution (Python):
def main():
    n, w= map(int, input().split())
    w_item = []
    v_item = []
    dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
    for _ in range(n):
        tmp_w, tmp_v = map(int, input().split())
        w_item.append(tmp_w)
        v_item.append(tmp_v)

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  n,w=map(int,input().split())
  wv=[tuple(map(int,input().split())) for _ in range(n)]
  dp=[[0]*(w+1) for _ in range(n+1)]
  for i in range(n):
    for j in range(w+1):
      dp[i+1][j]=max(dp[i][j-wv[i][0]]+wv[i][1],dp[i][j]) if j-wv[i][0]>=0 else dp[i][j]
  print(dp[n][w])
if __name__=='__main__':
  main()

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

score = [0] * (W+1)

for n in range(N) :
  w, v = map(int,raw_input().split())
  for i in range(w, W+1) :
    score[i-w] = max(score[i-w], score[i] + v)

print score[0]

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-w, -1, -1):
            if dp[j] >= 0 and dp[j+w] < dp[j]+v:
                dp[j+w] = dp[j] + v

    print(max(dp))


main()

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

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W:
                dp[j+w] = max(dp[j+w], dp[j] + v)

    print(max(dp))


main()

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())
    if w > W:
        continue
    else:
        np.maximum(dp[w:],dp[:-w]+v,out = dp[w:])
print(dp[W])

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

Solution (Python):
import sys
from io import StringIO
import unittest


def resolve():
    N, W = map(int, input().split())

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

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

    for i in range(W + 1):
        if i >= wv[0][0]:
            dp[0][i] = wv[0][1]

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

    print(max([l[-1] for l in dp]))



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 8
3 30
4 50
5 60"""
        output = """90"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000"""
        output = """5000000000"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6 15
6 5
5 6
6 4
6 6
3 5
7 2"""
        output = """17"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
N,W = map(int,input().split())
import copy
dp = [0]*(W+1)
for _ in range(N):
    dpc = copy.deepcopy(dp)
    w,v = map(int,input().split())
    if w > W:
        continue
    else:
        for j in range(w,W+1):
            if dpc[j] < dpc[j-w]+v:
                dp[j] = dpc[j-w]+v
print(dp[W])

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

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

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

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

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



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


print(dp[N][W])

Solution (Python):


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

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

npsk_1(N, W)

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

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

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

def npsk_1(N, W):
    w, v = [0]*N, [0]*N 
    for _ in range(N):
        w[_], v[_] = 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[-1][-1])

npsk_1(N, W)

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:])
    print(ndp[-1])
main()

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())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
dp = [[0 for _ in range(W + 10)] for _ in range(N + 10)]
for i in range(N):
    for w in range(W+1):
        if w+L[i][0] <= W:
            dp[i+1][w+L[i][0]] =max(dp[i][w]+L[i][1], dp[i+1][w+L[i][0]])
        dp[i+1][w] = max(dp[i][w], dp[i+1][w])
ans = 0
for w in range(W+1):
    ans = max(ans,dp[N][w])
print(ans)

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

dp = [[0] * 100100 for _ in range(110)]


for i in range(N):
    for sum_w in range(W + 1):

        if wv[i][0] <= sum_w:
            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])
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())

def solve(w,v):
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    ans = dp[-1][-1]
    return ans
print(solve(w,v))

Solution (Python):
n,w=map(int,input().split())
from copy import copy
a=[0]*(w+1)
for i in range(n):
    b=copy(a)
    x,y=map(int,input().split())
    for j in range(min(x,w),w+1):
        b[j]=max(a[j-x]+y,a[j])
    a=copy(b)
print(max(a))

Solution (Python):
n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(W[i-1]):
        DP[i][j] = DP[i-1][j]
    for j in range(W[i-1], m+1):
        DP[i][j] = max(DP[i-1][j], DP[i-1][j-W[i-1]]+V[i-1])
print(DP[n][m])

Solution (Python):
n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(W[i]):
        DP[i+1][j] = DP[i][j]
    for j in range(W[i], m+1):
        DP[i+1][j] = max(DP[i][j], DP[i][j-W[i]]+V[i])
print(DP[n][m])

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
inf = float("inf")

n_item, w_volume = map(int, input().split())
weight, value = [], []
for _ in range(n_item):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)








dp = [[0 for w in range(w_volume + 1)] for i in range(n_item + 1)]

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

print(dp[n_item][w_volume])

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

Solution (Python):
def knapsack_dp(n,w,wts,val):
    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 wts[i-1]<=j:
                dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-wts[i-1]])
            else:
                dp[i][j]=dp[i-1][j]

    return dp[n][w]


n,w=map(int,input().split())
wts,vals=[],[]
for i in range(n):
    a,b=map(int,input().split())
    wts.append(a)
    vals.append(b)

print(knapsack_dp(n,w,wts,vals))

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

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

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

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write

INF=int(10e9)


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,w=mdata()
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
print(knapSack(w,wt,val,n))

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

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

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

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

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

Solution (Python):

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

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

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

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")


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



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



for iN in range(1,N+1):
	w,v = WV[iN]
	for iW in range(W+1):
		
		v0 =     dp[iN-1][iW]
		v1 = v + dp[iN-1][iW-w] if iW-w>=0 else 0
		
		
		dp[iN][iW] = max(v0, v1)



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

Solution (Python):

def main():
    import sys
    N, W = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    
    dp = [[0 for i in range(10**5+1)] for _ in range(N)]
    for i in range(N):
        w, v = L[i][0], L[i][1]
        if i>=1:
            dp[i][w] = max(v, dp[i-1][w])
        elif i==0:
            dp[i][w] = v
        for j in range(10**5+1):
            if i>=1 and dp[i-1][j]!=0:
                dp[i][j] = max(dp[i-1][j], dp[i][j])
                if w+j <=10**5:
                    dp[i][w+j] = max(dp[i-1][w+j], v + dp[i-1][j])
                
    print(max(dp[-1][:W+1]))



if __name__=='__main__':
    main()

Solution (Python):
from sys import stdin



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


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, W = list(map(int,_in[0].split(' ')))  
    w_v_arr = []
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  
        w_v_arr.append(_)
    
    dp = [[0] * (W+1) for _ in range(N+1)] 
    
    
    for i in range(N):
        for w in range(1,W+1):
            if w >= w_v_arr[i][0]:
                dp[i+1][w] = chmax(dp[i+1][w],dp[i][w-w_v_arr[i][0]]+w_v_arr[i][1])
            dp[i+1][w] = chmax(dp[i+1][w],dp[i][w])
    cnt = dp[N][W]
    
    print(cnt)

Solution (Python):


def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, W = MAP()
w, v = [], []
for _ in range(N):
    wi, vi = MAP()
    w.append(wi)
    v.append(vi)

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

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

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

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

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

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

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

Solution (Python):
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
    wv.append(list(map(int,input().split())))
dp=np.zeros(w+1,np.int64)
for i in range(n):
    w_=wv[i][0]
    v_=wv[i][1]
    dp[w_:]=np.maximum(dp[w_:],dp[:-w_]+v_)

print(dp[-1])

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

print(dp[N][W])

Solution (Python):
N, W = [int(i) for i in input().split()]
noWeight = [[0 for j in range(W+1)] for i in range(N)]
wv = [[] for i in range(N)]
for i in range(N) :
	wv = [int(i) for i in input().split()]
	for j in range(1,W+1) :
		if i != 0 :
			if j < wv[0]  :
				noWeight[i][j] = noWeight[i-1][j]
			else :
				noWeight[i][j] = max(noWeight[i-1][j - wv[0]] + wv[1], noWeight[i-1][j])
		else :
			if j >= wv[0] :
				noWeight[i][j] = wv[1]
			else :
				noWeight[i][j] = 0
	
print(noWeight[N-1][W])

Solution (Python):
def main():
    N, W = list(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 = list(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],DP[i][sum_w-w]+v)
            DP[i+1][sum_w] = max(DP[i+1][sum_w],DP[i][sum_w])
    print(max(DP[-1]))

if __name__ == "__main__":
    main()
    pass

Solution (Python):
import copy
n,w = map(int,input().split())
b = [0]*(w+1)
a = [0]*(w+1)
for _ in range(n):
  wi,vi = map(int,input().split())
  a = copy.copy(b)
  for i in range(min(wi,w+1),w+1):
    a[i] = max(b[i-wi]+vi,b[i])
  b = a
print(max(b))

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

Solution (Python):
def solve():
    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 i in range(1,N+1):
        for w in range(W+1):
            if w - weight[i-1] < 0:
                dp[i][w] = max(dp[i][w],dp[i-1][w])
            else:
                dp[i][w] = max(dp[i][w], dp[i-1][w-weight[i-1]]+value[i-1])
                dp[i][w] = max(dp[i][w],dp[i-1][w])
    
    print(max(*dp[-1]))


if __name__ == '__main__':
    solve()

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

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

print(dp[n][w])

Solution (Python):
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W + 1)
for n 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 copy

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


DP=[[0]*(W+1)]
inf=float('inf')
component=[0]+[-inf]*W
for index2 in range(N):
    DP.append(copy.copy(component))

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



    

print(DP[N][W])

Solution (Python):
def main():
  N,W = map(int,input().split())  
  num_list = [list(map(int, input().split())) for _ in range(N)]
  dp = [[0] * (W+1) for i in range(N+1)]
  weight=[row[0] for row in num_list]
  value=[row[1] for row in num_list]
  for i in range(0,N):
    for sum_w in range(0,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(int(dp[N][W]))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def rec(i,j):
    res=0
    if(dp[i][j]>=0):
        return dp[i][j]
    if(i==n):
        res=0
    elif(j<w[i]):
        res=rec(i+1,j)
    else:
        res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
    dp[i][j]=res
    return res
n,x=map(int,input().split())
dp=[[-1]*(x+10) for i in range(n+10)]
w,v=[],[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a);v.append(b)
print(rec(0,x))

Solution (Python):
N,W=map(int,input().split())
w=[0 for _ in range(110)]
v=[0 for _ in range(110)]
for i in range(1,N+1):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(110000)] for j in range(110)]

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

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

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


dp=np.zeros(w+1,np.int64)
for i in range(n):
      
      
      
      w_=wv[i][0]
      v_=wv[i][1]
      
      
      
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(dp[-1])

Solution (Python):
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W + 1)
for n 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,wmax = map(int,input().split())
dp = [[0 for ww in range(wmax+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

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

ans = dp[n][wmax]
print(ans)

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

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)


for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0


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

ans = dp[n-1][w_lim]
print(ans)

Solution (Python):
def solve():
    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 i in range(N+1)]

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

if __name__ == '__main__':
    solve()

Solution (Python):
N,W = [int(x) for x in input().split()]
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
DP = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,W+1):
    for j in range(1,N+1):
        if l[j-1][0] > i:
            DP[j][i] = DP[j-1][i]
        else:
            DP[j][i] = max(DP[j-1][i],DP[j-1][i-l[j-1][0]]+l[j-1][1])
print(DP[N][W])

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

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

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

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

    for j in range(wi):
        dp[i+1][j] = dp[i][j]

    for j in range(wi, W+1):
        dp[i+1][j] = max(dp[i][j], dp[i][j-wi] + vi)

print(dp[N][W])

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

Solution (Python):
import sys


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

def main():

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

    dp = np.zeros(W + 1, int)

    for i 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__":
    main()

Solution (Python):
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

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


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

    
    print(dp.max())


if __name__ == "__main__":
    main()

Solution (Python):
import sys

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

def main():
    N,W = map(int,input().split())
    goods = [list(map(int,input().split())) for _ in range(N)]

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

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

if __name__ == "__main__":
    main()

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