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
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def resolve():
    return 

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]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wv[i][0]] + wv[i][1])
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print(dp[N][W])

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

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


    for i in range(n):
        for k in range(w+1):
            if k + A[i][0] <= w:

                Knap[i+1][k+A[i][0]] = max(Knap[i+1][k+A[i][0]], (Knap[i][k] + A[i][1]))

            Knap[i+1][k] = max(Knap[i][k], Knap[i+1][k])


    
    
    print(Knap[n][w])

resolve()

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

Solution (Python):
import numpy as np
N,W=list(map(int,input().split()))
DP=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=list(map(int,input().split()))
    a=DP[:-w]+v
    b=DP[w:]
    DP[w:]=np.fmax(a,b)
print(DP[-1])

Solution (Python):
n,w = map(int,input().split())
box = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
dp = [[0 for i in range(w+1)] for j in range(n+1)]

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

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

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

Solution (Python):


from collections import deque

n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

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

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(w+1):
        if j-_w < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-_w]+_v)

print(dp[n][w])

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

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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 j in range(1, w + 1):
        for i in range(1, n + 1):
            w, v = goods[i - 1]
            if j - w >= 0:
                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])


if __name__ == '__main__':
    resolve()

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

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

for i in range(N):
    w,v=list(map(int,input().split()))
    a=DP[:-w]+v
    b=DP[w:]
    c=np.maximum(a,b)
    DP[w:]=c



print(int(DP[-1]))

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

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)):
    w, v = map(int, input().split())
    for j in range(1,W+1):

        if j-w<0:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        else:
            dp[i][j] = max(dp[i-1][j-w]+v,dp[i-1][j])

print(max(max(dp)))

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

def solve_knapsack(capacity):
    
 
    
    
    dp = [0]*(W + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    
 
    
    
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    for i in range(0, N):
        weights[i],profits[i] = map(int,input().split())
    

    for i in range(0, N):
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    
 
    
    
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    

    for i in range(0, N):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    
 
    
    
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    
 
    
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    
 
    dp = [0]*(capacity + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

Solution (Python):
import sys
read = lambda: sys.stdin.readline().rstrip()
 
N,W=map(int,read().split())
 
def solve_knapsack(capacity):
    
 
    dp = [0]*(capacity + 1)
    
 
    for i in range(0, N):
        weights,profits = map(int,read().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    
 
    dp = [0]*(capacity + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
res = solve_knapsack(W)
print(res)

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

def solve_knapsack(capacity):
    
 
    dp = [0]*(capacity + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    
 
    dp = [0]*(capacity + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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


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

def solve_knapsack(capacity):
    
 
    dp = [0]*(capacity + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Solution (Python):
def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()

Solution (Python):
def knapsack(N, C, weights, values):
    dp = [[0 for _ in range(N + 1)] for _ in range(C + 1)]
    for i in range(1, C + 1):
        for j in range(1, N + 1):
            if weights[j - 1] <= i:
                dp[i][j] = max(dp[i][j - 1], values[j - 1] + dp[i - weights[j - 1]][j - 1])
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[C][N]
 
 
if __name__ == '__main__':
    n, c = list(map(int, input().split()))
    weights = [0] * n
    values = [0] * n
    for i in range(n):
        weights[i], values[i] = map(int, input().split())
    print(knapsack(n, c, weights, values))

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 j - w[i] >= 0:
            
            dp[i+1][j] = dp[i][j - w[i]] + v[i]

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

print(dp[N][W])

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

print(dp[N][W])

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

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

print(dp[N][W])

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

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], dp[i-1][j-w]+v)
    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)
 
for i in range(N):
    w, v = map(int,input().split())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m

print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush




def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    

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

    print(dp[-1])



if __name__ == "__main__":
    main()

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

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

Solution (Python):
N, W = map(int, input().split())
Ws = []
Vs = []

for _ in range(N):
  w, v = map(int, input().split())
  Ws.append(w)
  Vs.append(v)

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

for i in range(W+1):
  if i >= Ws[0]:
    Ans[0][i] = Vs[0]

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

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

Solution (Python):
def knapsack(w,val,W,n,t):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
t=[[0 for x in range(W+1)] for x in range(n+1)] 
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n,t)
print(ans)

Solution (Python):
[n, w] = map(int, input().split())
weights = []
values = []
for i in range(n):
    weight, value = [int(i) for i in input().split()]
    weights.append(weight)
    values.append(value)
dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    for weight in range(w+1):
        if weight - weights[i] >= 0:
            dp[i+1][weight] = max(dp[i][weight-weights[i]] + values[i], dp[i+1][weight])
        dp[i+1][weight] = max(dp[i+1][weight], dp[i][weight])

print(dp[n][w])

Solution (Python):
N, W = map(int, input().split())
v = []
w = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.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 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]
print(dp[N][W])

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N, W = MI()
inp = LI2(N)
w = [inp[i][0] for i in range(N)]
v = [inp[i][1] for i in range(N)]
dp = FILL2(0,N+1,W+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+1][j+w[i]],dp[i][j]+v[i])
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(max(dp[N]))

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

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

Solution (Python):
def mips():
    return map(int,input().split())
def chmax(DP,b,weight,number):
    if DP[number+1][weight] < b : 
        DP[number+1][weight] = b
        return True
    return False    
N,W = mips()
Poids = []
Valeur = []
for i in range(N):
    weight,value = mips()
    Poids.append(weight)
    Valeur.append(value)
DP = [[0] * (2*W) for i in range(N+1)]
for i in range(N):
    for sum_p in range(0,W+1):
        if sum_p - Poids[i] >= 0:
            chmax(DP,DP[i][sum_p-Poids[i]] + Valeur[i],sum_p,i)
        chmax(DP,DP[i][sum_p],sum_p,i)
print(DP[N][W])

Solution (Python):
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

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

def main():
	n, W = rli()
	items = []
	for _ in range(n):
		w, v = rli()
		items.append((w, v))
	dp = [0 for _ in range(W + 1)]
	for w, v in items:
		for i in range(W, -1, -1):
			if i - w >= 0:
				dp[i] = max(dp[i], dp[i-w] + v)
	print(dp[-1])
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[0 for e in range(W+1)] 
for i in range(N):
 w,v=map(int,input().split())
 for j in range(w,W+1)[::-1]:
  ans[j]=max(ans[j-w]+v,ans[j])
print(max(ans))

Solution (Python):
import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[[0 for e in range(W+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for k in range(0,w):
  ans[i+1][k]=ans[i][k]
 for j in range(w,W+1):
  ans[i+1][j]=max(ans[i][j-w]+v,ans[i][j])
print(max(ans[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)]

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

print(max(dp[-1]))

Solution (Python):
n,c = list(map(int, input().split()))
W=[]
P=[]
for _ in range(n):
    w,val = list(map(int, input().split()))
    W.append(w)
    P.append(val)
dp=[]
for i in range(n+1):
    dp.append([0]*(c+1))
for i in range(1,n+1):
    for j in range(1,c+1):
        inc=0
        exc=0
        if j-W[i-1]>=0:
            inc=P[i-1]+dp[i-1][j-W[i-1]]
        exc=dp[i-1][j]
        dp[i][j]=max(inc,exc)
print(dp[n][c])

Solution (Python):
import numpy as np
 
N,Max_W = map(int,input().split())
 
dp = [0 for _ in range(Max_W + 1)]
dp = np.array(dp)
 
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m
print(dp[-1])

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

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

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

print(dp[N][W])

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

Ws = []
Vs = []

for _ in range(N):
  w, v = map(int, input().split())
  Ws.append(w)
  Vs.append(v)


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

if Ws[0] <= W:
  for i in range(Ws[0], W+1):
    S[0][i] = Vs[0]

for weight in range(W+1):
  for item_num in range(N-1):
    if weight - Ws[item_num+1] < 0:
      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight])
    else:
      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight-Ws[item_num+1]] + Vs[item_num+1], S[item_num][weight])

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

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

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

Solution (Python):


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

weights, profits = [], []

for i in range(N):
    w, p = map(int, input().split())
    weights.append(w)
    profits.append(p)

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(1, W+1):
        if w - weights[i-1] >= 0:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + profits[i-1])
        else:
            dp[i][w] = dp[i-1][w]

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

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

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

for i in range(n):
    for j in range(w + 1):
        if j == 0:
            nw = wv[i][0]
            if nw <= w:
                dp[i][nw] = wv[i][1]

        elif dp[i - 1][j] != 0:
            nw = wv[i][0] + j
            if nw <= w:
                dp[i][nw] = max(dp[i][nw], dp[i - 1][j] + wv[i][1])

        dp[i][j] = max(dp[i - 1][j], dp[i][j])
print(max(dp[-1]))

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

K = [[0 for x in range(W+1)] for y 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]
print(K[N][W])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,weight=map(int,input().split())
    WV=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[0]*(weight+1) for _ in range(n+1)] 
    for i in range(n):
        ni=i+1
        w,v=WV[ni-1]
        for j in range(weight+1):
            dp[ni][j]=max(dp[ni][j],dp[i][j])
            if j+w<=weight and (j==0 or dp[i][j]>0):
                dp[ni][j+w]=max(dp[ni][j+w],dp[i][j]+v)
    print(max(dp[n]))
            



if __name__=='__main__':
    main()

Solution (Python):
N,W=map(int,input().split(' '))
bag=[tuple(map(int,input().split(' '))) for _ in range(N)]
dp1,dp2=[0]*(W+1),[0]*(W+1)
for i in range(N):
    dp1=dp2
    dp2=[0]*(W+1)
    for j in range(1,W+1):
        if j<bag[i][0]:
            dp2[j]=dp1[j]
        else:
            dp2[j]=max(dp1[j],dp1[j-bag[i][0]]+bag[i][1])
print(dp2[-1])

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

Solution (Python):
import numpy as np

n, w = map(int, input().split())
DP = np.zeros((n, w + 1), dtype="int64")
for i in range(n):
    weight, value = map(int, input().split())
    DP[i, :weight] = DP[i - 1, :weight]
    DP[i, weight:] = np.fmax(DP[i - 1, weight:], DP[i - 1, : w - weight + 1] + value)

print(DP[-1][w])

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

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

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

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

print(dp[N][W])

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

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

Solution (Python):
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [collections.defaultdict(int) for _ in range(N+1)] 
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for dw,dv in dp[i-1].items():
        dp[i][dw] = max(dp[i][dw],dv)
        if dw+w<=W:
            dp[i][dw+w] = max(dp[i][dw+w],dv+v)
print(max(dp[-1].values()))

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


print(dp[N][W])

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

    
    dp = [[-1]*(wmax+1) for _ in range(n+1)]

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

if __name__ == '__main__':
    main()

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

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

    
    
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.fmax(dp[i-1, w:], dp[i-1,:W-w+1]+v)

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