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 numba as nb
import sys
import numpy as np
@nb.njit
def solve(w,weight,value):
    total=w
    dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
    for i in range(l):
        for w in range(total+1):
            if weight[i]<=w:
                dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[l-1][total])
n,w=map(int,sys.stdin.readline().split())
weight=[0]*n
value=[0]*n
total=w
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    weight[i]=x
    value[i]=y
l=len(weight)
solve(w,weight,value)

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

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

D = [0] * (w+1)

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

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

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

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

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

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

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

Solution (Python):
N,W = map(int,input().split())
w, v = zip(*(map(int, input().split()) for _ in range(N)))

dp = [0] * (W+1)

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

Solution (Python):
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]
print(knapsack(N, W))

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

Solution (Python):

import os
import operator
import sys
from io import BytesIO, IOBase

def inar():
    return [int(k) for k in input().split()]
def main():
    n,we=map(int,input().split())
    arr=[]
    for i in range(n):
        w,v=inar()
        arr.append([w,v])
    arr.sort()
    dp=[]

    for i in range(n+1):
        lis=[0]*(we+1)
        dp.append(lis)
    
    
    for i in range(1,n+1):
        for j in range(1,we+1):
            if arr[i-1][0]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],arr[i-1][1]+dp[i-1][j-arr[i-1][0]])
    
    
    print(dp[n][we])








BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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

if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = [[0] * (W + 1) for _ in [0] * N]

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


resolve()

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

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

for i in range(1, N+1):
    item[i][0], item[i][1] = map(int, input().split())

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

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

print(DP[N][W])

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

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

if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, W = map(int, input().split())
    w = [None] * N
    v = [None] * N

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

if __name__ == "__main__":
    main()

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

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

import numpy as np
dp = np.zeros(W + 1, dtype = int)

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

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

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


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    N, W = map(int, input().split())  

    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  
    dp = [dp_min] * (W + 1)

    for _ in range(N):
        w, price = map(int, input().split())
        S = reversed(range(w, W + 1))
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - w] + price)
    return dp[W]




print(knapsack_weight(single=True))

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


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    N, W = map(int, input().split())  

    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  
    dp = [dp_min] * (W + 1)

    for _ in range(N):
        w, price = map(int, input().split())
        if single:
            S = reversed(range(w, W + 1))
        else:
            S = range(w, W + 1)
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - w] + price)
    return dp[W]




print(knapsack_weight(single=True))

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


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = reversed(range(weight_list[item], W + 1))
        else:
            S = range(weight_list[item], W + 1)
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return dp[W]




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

price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)

print(knapsack_weight(single=True))

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



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

price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)




def max2(x,y):
    """ pythonの組み込み関数 max は２変数に対しては遅い！！ """
    if x>y:
        return x
    else:
        return y


dp_min = 0                                                      

""" dp[weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [dp_min] * (W + 1)

for item in range(N):
    for weight in reversed(range(weight_list[item], W + 1)):
        dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])


print(dp[W])

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



M, W = map(int, input().split())                                
single = True                                                   

price_list = [0]
weight_list = [0]
for _ in range(M):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)




dp_min = 0                                                      

""" dp[item <= M ][weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                 

""" 重さ 0 の時の境界条件 """
for item in range(M+1):
    dp[item][0] = 0                                             

""" 品物 0 個の時の境界条件 """




for item in range(1,M+1):                                       
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          
            dp[item][weight] = dp[item - 1][weight]
        else:
            temp = dp[item - single][weight - weight_list[item]] + price_list[item]  
            if temp > dp[item-1][weight]:                       
                dp[item][weight] = temp
            else:
                dp[item][weight] = dp[item-1][weight]

print(dp[M][W])

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

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

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

    print(dp[N][W])


if __name__ == '__main__':
    main()

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

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

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

print(max(dp[N]))

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

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

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

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

print(max(dp[N]))

Solution (Python):

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

Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * (W + 1) for i in range(N)]

for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if (i == 0) & (Current_Weight <= W) :
        dp[i][Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = [j for j, x in enumerate(dp[i-1]) if x > -1]
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        
        for l in range(len(Last_Search_List)):
            Last_Search_Weight =  Last_Search_List[l] 
            dp[i][Last_Search_Weight] = dp[i-1][Last_Search_Weight]
        
        for k in range(len(Current_Search_List)):
            Last_Search_Weight =  Last_Search_List[k] 
            Current_Search_Weight = Current_Search_List[k]
            if Current_Search_Weight > W:
                break
            else:
                dp[i][Current_Search_Weight] = max((dp[i-1][Last_Search_Weight] + Current_Value),
                                                   dp[i-1][Current_Search_Weight])


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

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

Solution (Python):



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

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]
jmax=100010
nmax=110
 
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    
DP= [[0]*jmax for i in range(nmax)]
 
 
def chmax(a,b):
    if a>b:
        return a
    else:
        return b
 
 
for i in range(N):
    for j in range(jmax):
        if  j-w[i]>=0:
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-w[i]]+v[i])
        else:
            DP[i+1][j]=DP[i][j]
 
            
print(DP[N][W])

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000
"""

n ,W = map(int, input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
dp = [[0 for i in range(W+1)] for j in range(n+1)]
for i in range(n):
    for j in range(W+1):
        if j < w[i]:
            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):
def MI(): return map(int, input().split())
N,W=MI()
w=[]
v=[]
for i in range(N):
  a,b=MI()
  w.append(a)
  v.append(b)
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  for j in range(W+1):
    if j<w[i]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])      
ans=dp[-1][-1]
print(ans)

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

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


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

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

ans = 0
for val in dp:
    ans = max(ans, val)

print(ans)

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

print(dp[N][W])

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

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

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

Solution (Python):
def MI(): return map(int, input().split())
import sys
input = sys.stdin.readline
n,w = map(int,input().split())

W=[]
V=[]
for i in range(n):
  a,b=MI()
  W.append(a)
  V.append(b)
dp = [0]*(w+1)
for i in range(n):
    for j in range(w,W[i]-1,-1):
        dp[j] = max(dp[j],dp[j-W[i]]+V[i])
print(max(dp))

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

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

print(max(dp))

Solution (Python):
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 - 1][j - w] + v)
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N][W])

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

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

print(max(dp[N]))

Solution (Python):
import numpy as np

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


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

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

print(memo[-1])

Solution (Python):
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


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

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i in range(1, N + 1):
        w, v = wv[i - 1]
        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 - w] + v, dp[i - 1, j])
    return dp[-1, -1]


def main():
    N, W = map(int, input().split())
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = map(int, input().split())
        wv[i] = w, v

    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8, i8)")
def chmax(a, b):
    if a > b:
        return a
    else:
        return b


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i in range(1, N + 1):
        w, v = wv[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp[i, j] = dp[i - 1, j]
            else:
                dp[i, j] = chmax(dp[i - 1, j - w] + v, dp[i - 1, j])
    return dp[-1, -1]


def main():
    N, W = map(int, input().split())
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = map(int, input().split())
        wv[i] = w, v

    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8, i8)")
def chmax(a, b):
    if a > b:
        return a
    else:
        return b


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    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(1, W + 1):
            if j < w:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = chmax(dp[i - 1][j - w] + v, dp[i - 1][j])
    return dp[-1][-1]


def main():
    N, W = map(int, input().split())
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = map(int, input().split())
        wv[i] = w, v

    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

N,W=map(int,input().split())
w=[]
v=[]
jmax=100010
nmax=110

for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    
DP= [[0 for j in range(jmax)] for i in range(nmax)]


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


for i in range(N):
    for j in range(jmax):
        if  j-w[i]>=0:
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-w[i]]+v[i])
        else:
            DP[i+1][j]=DP[i][j]

            
print(DP[N][W])

Solution (Python):
import sys

input = sys.stdin.readline


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

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                a = dp_im[j - w] + v
                b = dp_im[j]
                if a > b:
                    dp_i[j] = a
                else:
                    dp_i[j] = b

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


if __name__ == "__main__":
    main()

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

print(max(dp))

Solution (Python):


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

weight = []
value = []

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


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

print(dp[N][W])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)





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


def main():
    N, W = map(int, input().split())
    item = []
    dp = [[0] * (W + 1) for _ in range(N)]

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

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


if __name__ == "__main__":
    main()

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




def main():

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

    dp = [0] * (W+2)

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

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

    print(dp[W])



if __name__ == "__main__":
    main()

Solution (Python):
def readinput():
    n,w=list(map(int,input().split()))
    wlist=[]
    vlist=[]
    for _ in range(n):
        ww,vv=list(map(int,input().split()))
        wlist.append(ww)
        vlist.append(vv)
    return n,w,wlist,vlist

def main(n,W,w,v):
    dp=[]
    for _ in range(n+1):
        dp.append([0]*(W+1))
    for i in range(1,n+1):
        for j in range(W+1):
            if j-w[i-1]>=0:
                dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1], dp[i][j])
            dp[i][j]=max(dp[i-1][j], dp[i][j])
    return dp[n][W]

if __name__=='__main__':
    n,w,wlist,vlist=readinput()
    ans=main(n,w,wlist,vlist)
    print(ans)

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

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

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

print(dp[N][WM])

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

DP= [[0 for j in range(100010)] for i in range(110)]
def chmax(a,b):
    if a>b:
        return a
    else:
        return b


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


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

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

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
    row = dp[i]; row_before = dp[i-1]
    v_i = v[i]; w_i = w[i]
    for sum_w in range(1, W+1):
        if sum_w - w_i >= 0:
            row[sum_w] = max(row_before[sum_w - w_i] + v_i, row_before[sum_w])
        else:
            row[sum_w] = row_before[sum_w]
print(dp[N][W])

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

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

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

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

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

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

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

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

for j in range(k+1):
    dp[0][j] = v[0] if j >= m[0] else 0

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

print(dp[i][j])