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
input = sys.stdin.readline

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

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

if __name__ == '__main__':
    main()

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


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

    
    
    print(dp[N][W])


if __name__ == '__main__':
    main()

Solution (Python):


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

l=[-1]*(W+1)
l[0]=0
dp=l[:]

for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=-1 and W>=index+w:
            dp[index+w]=max(item+v,l[index+w])
    l=dp[:]
print(max(l))

Solution (Python):

n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
   dp.append([-1]*(w+1))
def rec(i,j):
   if dp[i][j]>=0:
       return dp[i][j]
   if i==n:
       res=0
   elif j<a[i][0]:
       res=rec(i+1,j)
   else:
       res=max(rec(i+1,j),rec(i+1,j-a[i][0])+a[i][1])
   dp[i][j]=res
   return res
print(rec(0,w))

Solution (Python):

n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
  dp.append([])
  for l in range(w+1):
      dp[k].append(0)
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+a[i][0]<=w:
           dp[i+1][j+a[i][0]]=max(dp[i+1][j+a[i][0]],dp[i][j]+a[i][1])
print(dp[n][w])

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

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

Solution (Python):

n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
  dp.append([])
  for l in range(w+1):
      dp[k].append(0)
for i in range(n):
   for j in range(w+1):
       if j<a[i][0]:
           dp[i+1][j]=dp[i][j]
       else:
           dp[i+1][j]=max(dp[i][j],dp[i][j-a[i][0]]+a[i][1])
print(dp[n][w])

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

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

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

dp[0][0] = 0

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

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

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

Solution (Python):
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))

Solution (Python):
from copy import deepcopy
n,W = map(int,input().split())
dp = [0] * (W+1)
for i in range(n):
  w,v = map(int,input().split())
  pdp = deepcopy(dp)
  for j in range(w,W+1):
    dp[j] = max(pdp[j-w]+v,dp[j])
print(max(dp))

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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 i in range(1,n+1): 
        newdp=dp[:] 
        for j in range(W+1):
            if(j-w[i]>=0): 
                newdp[j]=max(dp[j-w[i]]+v[i],dp[j])
        dp=newdp
    print(dp[-1])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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 i in range(1,n+1): 
        newdp=dp[:]
        for j in range(W+1):
            if(j+w[i]<=W):
                newdp[j+w[i]]=max(newdp[j+w[i]],dp[j]+v[i])
        dp=newdp
    print(dp[-1])
resolve()

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

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

Solution (Python):
N, W = map(int, input().split())
dp = [{ 0: 0 }]
for i in range(N):
  w, v = map(int, input().split())
  d = dp[i]
  d2 = {}
  for w0 in d:
    v0 = d[w0]
    d2[w0] = v0
  for w0 in d:
    v0 = d[w0]
    if w0+w > W:
      continue
    if w0+w not in d:
      d2[w0+w] = v0+v
    else:
      d2[w0+w] = max(d2[w0+w], v0+v)
  dp.append(d2)
r = max(dp[N].values())
print(r)

Solution (Python):
import numpy as np

MAX_WEIGHT = 100100


def main(n, w, items):
    dp = np.zeros((n + 1, MAX_WEIGHT), dtype=int)
    for i in range(n):
        weight, value = items[i]
        dp[i + 1][:weight] = dp[i][:weight]
        dp[i + 1][weight:] = np.maximum(dp[i][weight:], dp[i][:MAX_WEIGHT - weight] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    ITEMS = []
    for _ in range(N):
        ITEMS.append(tuple(map(int, input().split())))
    print(main(N, W, ITEMS))

Solution (Python):
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        dp[i][:weight] = dp[i - 1][:weight]
        dp[i][weight:] = np.maximum(dp[i - 1][weight:], dp[i - 1][:w - weight + 1] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

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

vw = [0] * (mw + 1)

for i in range(n):
  for j in reversed(range(iwv[i][0], mw + 1)):
    vw[j] = max(vw[j], vw[j - iwv[i][0]] + iwv[i][1])
  
print(max(vw))

Solution (Python):
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        dp[i][:weight] = dp[i - 1][:weight]
        dp[i][weight:] = np.maximum(dp[i - 1][weight:], dp[i - 1][:w - weight + 1] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Solution (Python):
def main():
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

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

    print(dp[N][W])


if __name__ == '__main__':
    main()

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

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)


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

for i in reversed(range(n)):
    for j in reversed(range(W)):
        weight, val = w[i], v[i]

        if j + weight <= W:
            chose = dp[i+1][j + weight] + val
            unchose = dp[i+1][j]
            dp[i][j] = max(chose, unchose)
        else:
            dp[i][j] = dp[i+1][j]



print(dp[0][0])

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:], dp[:-w] + v, out= dp[w:])
print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*n
    V=[0]*n
    for i in range(n):
        W[i],V[i]=map(int,input().split())
    dp=[[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for k in range(w+1):
            if(k+W[i]<=w):
                dp[i+1][k+W[i]]=max(dp[i][k]+V[i],dp[i+1][k+W[i]])
            dp[i+1][k]=max(dp[i+1][k],dp[i][k])
    print(dp[n][w])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1)
    V=[0]*(n+1)
    for i in range(n):
        W[i+1],V[i+1]=map(int,input().split())
    dp=[[0]*(w+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for k in range(w+1):
            if(k-W[i]>=0):
                dp[i][k]=max(dp[i-1][k-W[i]]+V[i],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
def make_v(*args,e=0):
    from copy import deepcopy
    A=e
    for i in args[::-1]: A=[deepcopy(A) for _ in range(i)]
    return A
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1)
    V=[0]*(n+1)
    for i in range(n):
        W[i+1],V[i+1]=map(int,input().split())
    dp=make_v(n+1,w+1)
    for i in range(1,n+1):
        for k in range(w+1):
            if(k-W[i]>=0):
                dp[i][k]=max(dp[i-1][k-W[i]]+V[i],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()

Solution (Python):
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
 
baggage = [0]*N
 
for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)
 
dp = [[0]*(W+1) for _ in range(N+1)]
 
for i in range(N):
    for w in range(W+1):
        if w >= baggage[i][0]:
            dp[i+1][w] = max(baggage[i][1]+dp[i][w-baggage[i][0]],dp[i][w])
 
        dp[i+1][w] = max(dp[i][w],dp[i+1][w])
print(dp[N][W])

Solution (Python):
def main():
    
    m=0
    n, W = map(int, input().split())
    v, w = [0], [0]
    for _ in range(n):
        wi, vi = map(int, input().split())
        v.append(vi)
        w.append(wi)
    cond = []
    b_list = []
    for _ in range(m):
        a, b = map(int, input().split())
        cond.append([b, a])
        b_list.append(b)
    cond.sort(reverse=True)

    
    for i in range(m):
        a, b = cond[i][1], cond[i][0]
        v[a] += v[b]
        w[a] += w[b]

    
    b_tuple = tuple(b_list)
    
    dp = [[0]*(W+1) for _ in range(n+1)]
    skip = 0
    for i in range(1, n+1):
        if i in b_tuple:
            skip += 1
            continue
        for j in range(1, W+1):
            if j>=w[i]:
                dp[i][j] = max(dp[i-1-skip][j], dp[i-1-skip][j-w[i]]+v[i])
            else:
                dp[i][j] = dp[i-1-skip][j]
    print(max(max(dp)))

if __name__ == '__main__':
    main()

Solution (Python):
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(min(w,W+1),W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])

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

print(dp[N][W])

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

Solution (Python):
import copy

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




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


for i in range(W+1):
    if i < w[0]:
        s[0][i] = 0
    else :
        s[0][i] = v[0]

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

print(s[-1][-1])

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

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

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)]
ans = int(0)
dp[0][0] = 0

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

ans = dp[N][W]

print(ans)

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 = [[int(0) for i in range(W+1)] for i in range(N+1)]
ans = int(0)
dp[0][0] = 0


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

ans = dp[N][W]

print(ans)

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

import collections
def main():
    N,W = map(int, input().split())
    I = collections.deque()
    for _ in range(N):
        I.append(tuple(map(int, input().split())))

    dp = [0]*(W+1)
    while I:
        w,v = I.popleft()
        for j in range(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x

    print(dp[W])

if __name__ == '__main__':
    main()

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

def main():
    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]*(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]
                
    ans = 0
    for a in dp:
        ans = max(ans, max(a))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

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

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


main()

Solution (Python):
def knapsack(val,wt,n,k):
    b = [[0 for _ in range(k+1)]for _ in range(n+1)]
    for i in range(n+1):
        for j in range(k+1):
            if j==0 or i==0:
                b[i][j] = 0
            elif wt[i-1]<=j:
                b[i][j] = max(val[i-1]+b[i-1][j-wt[i-1]],b[i-1][j])
            else:
                b[i][j] = b[i-1][j]
    return b[n][k]
from sys import stdin
input = stdin.readline
n,k = list(map(int,input().split()))
val,wt = [],[]
for _ in range(n):
    x,y = list(map(int,input().split()))
    val.append(y)
    wt.append(x)
p = knapsack(val,wt,n,k)
print(p)

Solution (Python):
n, w = [int(i) for i in input().split()]
import numpy as np
dp = np.zeros(w+1, np.int64)
for i in range(n):
    wi, vi = [int(i) for i in input().split()]
    np.maximum(dp[:-wi]+vi, dp[wi:], out=dp[wi:])
print(max(dp))

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


if __name__ == '__main__':
    main()

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

Solution (Python):
import numpy as np

n,W = (int(i) for i in input().split())
items=[[int(i) for i in input().split()]for j in range(n)]

dp  = np.zeros(W+1)

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

print(int(dp[-1]))

Solution (Python):
import numpy as np

n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

dp  = np.zeros(W+1)

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

print(int(dp[-1]))

Solution (Python):
from sys import stdin,stdout
N,W=map(int,stdin.readline().split())
matrix=[[-1 for i in range(0,W+1)]for j in range(0,N+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,stdin.readline().split())
    weights.append(w)
    values.append(v)
for item in range(1,N+1):
    for weight in range(1,W+1):
        if(weights[item-1]<=weight):
            matrix[item][weight]=max(values[item-1]+matrix[item-1][weight-weights[item-1]],matrix[item-1][weight])
        else:
            matrix[item][weight]=matrix[item-1][weight]
print(matrix[N][W])

Solution (Python):
import numpy as np

num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

dp = np.zeros(weight_limit + 1)

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

print(int(dp[-1]))

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

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

print(dp[n][w])

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    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-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])

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]

baggage = [0]*N

for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)

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

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

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

weight_value = [0] * n
for i in range(n):
  weight_value[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (w+1) for i in range(n+1)]

for i in range(n):
  for w_upper in range(w+1):
    if w_upper - weight_value[i][0] >= 0:
      dp[i+1][w_upper] = max(dp[i][w_upper - weight_value[i][0]] + weight_value[i][1], dp[i][w_upper])
    else:
      dp[i+1][w_upper] = dp[i][w_upper]
print(dp[n][w])

Solution (Python):
N, W = (int(n) for n in input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = (int(n) for n in input().split())
    w.append(w_)
    v.append(v_)

def knapsack_dp(W, w, v):
    """Solve knapsack problem by dynamic programming"""
    N = len(w)
    dp = [[0] * (W + 1) for _ in range(N + 1)]

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

    return dp[N][W]

print(knapsack_dp(W, w, v))

Solution (Python):
N, weight_capacity = (int(n) for n in input().split())
weights, values = [], []
for _ in range(N):
    w, v = (int(n) for n in input().split())
    weights.append(w)
    values.append(v)

def knapsack_dp(weight_capacity, weights, values):
    """Solve knapsack problem by dynamic programming"""
    N = len(weights)
    dp = [[0] * (weight_capacity + 1) for _ in range(len(weights) + 1)]

    for i in range(N):
        for w in range(weight_capacity + 1):
            if w >= weights[i]:
                dp[i + 1][w] = max(dp[i][w], dp[i][w - weights[i]] + values[i])
            else:
                dp[i + 1][w] = dp[i][w]

    return dp[N][weight_capacity]

print(knapsack_dp(weight_capacity, weights, values))

Solution (Python):
def run():
  N, W = map(int, input().split())
  wv_li = [[0, 0]]+[list(map(int, input().split())) for n in range(N)]
  dp = [[0]*(N+1) for w in range(W+1)]
  
  
  for w in range(1, W+1):
    for n in range(1, N+1):
      wn, vn = wv_li[n]
      if w < wn:
        dp[w][n] = dp[w][n-1]
      else:
        dp[w][n] = max(dp[w][n-1], dp[w-wn][n-1]+vn)
  print(dp[W][N])
      
  
if __name__ == '__main__':
  run()

Solution (Python):
n,w=list(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+1)]
dp[0][0] = 0

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

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

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

dp = [[-float("inf") for _ in range(w+1)] for _ in range(n+1)]
dp[0][0] = 0

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

print(max(dp[-1]))

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

    dp = [-1] * (W + 1)
    dp[0] = 0

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

    print(max(dp))

main()

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

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()

Solution (Python):

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

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

print(dp[n][w])

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

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


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

Solution (Python):

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

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

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

        
        
        if w_sum+items[i][0] <= W:
            dp[i+1][w_sum+items[i][0]] = max(dp[i+1][w_sum+items[i][0]],
                                             dp[i][w_sum]+items[i][1])

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

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

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

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

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

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