Problem:
 Score : 100 points    Problem Statement There are N items, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq N ), Item i has a weight of w_i and a value of v_i .  Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W , which means that the sum of the weights of items taken must be at most W .  Find the maximum possible sum of the values of items that Taro takes home.      Constraints  All values in input are integers.  1 \leq N \leq 100  1 \leq W \leq 10^5  1 \leq w_i \leq W  1 \leq v_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  W  w_1  v_1  w_2  v_2  :  w_N  v_N       Output Print the maximum possible sum of the values of items that Taro takes home.        Sample Input 1 3 8
3 30
4 50
5 60      Sample Output 1 90  Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8 , and the sum of the values is 30 + 60 = 90 .       Sample Input 2 5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000      Sample Output 2 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 3 6 15
6 5
5 6
6 4
6 6
3 5
7 2      Sample Output 3 17  Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14 , and the sum of the values is 6 + 6 + 5 = 17 .

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

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

if __name__ == "__main__":
  main()

Solution (Python):








def resolve():
    N, W = map(int, input().split())
    weight, value = [0] * N, [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())

    
    def knapsack(N, W, weight, value):

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

        return dp[N][W]

    print(knapsack(N,W,weight,value))

resolve()

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

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

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

Solution (Python):
inp = list(map(lambda x: int(x), input().split(" ")))
n = inp[0]
w = inp[1]
inp = []
for i in range(n):
    inp.append(list(map(lambda x: int(x), input().split(" "))))

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

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

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

Solution (Python):
import numpy as np

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())
ndp = np.zeros(W + 1, dtype=np.int64)

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

print(ndp[-1])

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

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


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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

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

if __name__ == '__main__':
    main()

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

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

if __name__ == '__main__':
    main()

Solution (Python):

import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)
for i in range(n):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[:-w]+v, dp[w:])
print(int(dp[-1]))

Solution (Python):
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
dp = [[0 for w in range(W+1)] for n in range(N+1)]
for i in range(W+1):
	dp[0][i] = 0
for p in range(1, N+1):
	for q in range(W+1):
		dp[p][q] = dp[p-1][q]
		if (A[p-1][0] <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - A[p-1][0]] + A[p-1][1])

print(dp[N][W])

Solution (Python):
def KnapSack(val, wt, n, W): 
      
    
    mat = [[0 for i in range(W + 1)]  
              for i in range(2)] 
    
    i = 0
    while i < n: 
                 
        j = 0 
          
        
        
        
        
        if i % 2 == 0: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[1][j] = max(val[i] + mat[0][j - 
                                     wt[i]], mat[0][j]) 
                else: 
                    mat[1][j] = mat[0][j] 
                      
        
        
        
        
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - 
                                     wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    
    
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 
  

n,W = map(int,input().split())
val = [] 
wt = []  
for i in range(n):
    a,b = map(int,input().split())
    val.append(b)
    wt.append(a)
    
print(KnapSack(val, wt, n, W))

Solution (Python):
import sys

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

WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = (-1)*10**13

dp = [[0]*(1+W) for i in range(N+1)]
for j in range(1, W+1):
    dp[0][j] = INF
for i in range(1, N+1):
    for j in range(1, W+1):
        if j-WV[i-1][0]>=0 and dp[i-1][j-WV[i-1][0]]!=INF:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-WV[i-1][0]]+WV[i-1][1])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[N][W])

Solution (Python):
import numpy as np
n,w = map(int,input().split())
dp = np.array([0]*(w+1))

for i in range(n):
    we,va = map(int, input().split())
    dp[we:] = np.maximum(dp[we:],dp[:-we]+va)

print(int(dp[-1]))

Solution (Python):
import sys

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

WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**11+1

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

for i in range(1, N+1):
    for j in range(1, 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):
import sys

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

WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**11+1

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

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

print(dp[N][W])

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

Solution (Python):
def main():
    goods, weight_limit = map(int, input().split())
    good_info = [tuple(map(int, input().split())) for _ in range(goods)]
    dp = [[0 for _ in range(weight_limit + 1)] for _ in range(goods + 1)]
    for i in range(goods):
        for j in range(weight_limit + 1):
            if j >= good_info[i][0]:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - good_info[i][0]] + good_info[i][1])
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[goods][weight_limit])


if __name__ == '__main__':
    main()

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

wv = []
for i in range(n):
    wv.append(list(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):
    for j in range(1, w + 1):
        wi = wv[i - 1][0]
        vi = wv[i - 1][1]

        if j - wi >= 0:
            dp[i][j] = max([
                dp[i][j - 1],
                dp[i - 1][j - wi] + vi
            ])
            
        dp[i][j] = max([
            dp[i - 1][j],
            dp[i][j]
        ])

print(dp[n][w])

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))



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

N, W = MAP()
L = [LIST() for _ in range(N)]

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

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

print(dp[N][W])

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

Solution (Python):
import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
f_min = 0 
dp = [[f_min] * (W+1) for _ in range(N+1)]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def chmax(a,b):
    if a < b:
        return b
    else:
        return a
def main():
    

    for i in range(1,N+1):
        w,v = wv[i-1][0], wv[i-1][1]

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

            
 

if __name__ == "__main__":
    main()

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

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

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

Solution (Python):
def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]
    dp = [[0] * (M+1) for i in range(N+1)]
    
    for i in range(N):
        for s in range(M+1):
            a, b = A[i]
            if s-a >= 0:
                dp[i+1][s] = max(dp[i+1][s], dp[i][s-a] + b)
            dp[i+1][s] = max(dp[i+1][s], dp[i][s])
    return dp[N][M]

print(solve())

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

Solution (Python):
def knapsack_1(N, W, lst):
    
    
    
    
    
    dp = [[0 for i in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for j in range(W+1):
            if j < lst[i][0]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j - lst[i][0]] + lst[i][1])
    return dp[N][W]


n,w = map(int,input().split())
lst = []
for i in range(n):
    w_, v_ =  map(int,input().split())
    lst.append((w_, v_))
print(knapsack_1(n,w,lst))

Solution (Python):
import sys
 
N, W = map(int, input().split())
 
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
 
dp = [[0]*(N+1) for i in range(W+1)]
for i in range(1, W+1):
        for j in range(1, N+1):
                if i - WV[j-1][0]>=0:
                        dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = dp[i][j-1]
 
print(dp[W][N])

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n,w=mii()

wei=[0]
val=[0]
for i in range(n):
    x,y=mii()
    wei.append(x)
    val.append(y)

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

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

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

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

print(max(dp))

Solution (Python):
N, W = list(map(int, input().split()))
dp = [-1] * (W + 1)
dp[0] = 0
for i in range(N):
    w, v = list(map(int, input().split()))
    next = dp[:]
    for i in range(W):
        if dp[i] >= 0 and i + w <= W:
            next[i+w] = max(dp[i+w], dp[i] + v)
    dp = next

print(max(dp))

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

dp = [0] * (w+1)
for wi, vi in wv:
    for sum_w in range(w, wi-1, -1):
        dp[sum_w] = max(dp[sum_w], dp[sum_w - wi] + vi)
print(dp[w])

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

dp = [0] * (w+1)

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

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

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1, dtype='int64')
for i in range(N):
  wi,vi=map(int,input().split())
  dp[wi:]=np.maximum(dp[wi:],dp[0:W-wi+1]+vi)
print(dp[W])

Solution (Python):
import numpy as np

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

dp = np.zeros((n+1, w+1), np.int64)
for i, (wi, vi) in enumerate(wv):
    dp[i + 1] = dp[i]
    np.maximum(dp[i+1][wi:], dp[i][:-wi] + vi, out=dp[i+1][wi:])
print(dp[n, w])

Solution (Python):
dp = [[0 for _ in range(10**5+10)] for _ in range(10**2+10)]

N, W = map(int,input().split())
w = []
v = []

for i in range(N):
    wi,vi = map(int,input().split())

    w.append(wi)
    v.append(vi)

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

print(dp[N][W])

Solution (Python):

import numpy as np  

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

dp = np.array([0] * (w+1)) 

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Solution (Python):
import numpy as np  

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

dp = np.zeros(w+1)

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Solution (Python):
import numpy as np  

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

dp = np.zeros(w+1)

for _ in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Solution (Python):
def main():
    import numpy as np
    import sys
    input=sys.stdin.readline
    
    n,w=map(int,input().split())
    items=np.array([list(map(int,input().split())) for _ in range(n)])

    dp=np.zeros([n+1,w+1],dtype=np.int64)
    for i in range(n):
        wi=items[i][0]
        vi=items[i][1]
        dp[i+1][:wi]=dp[i][:wi]
        dp[i+1][wi:]=np.maximum(dp[i][wi:],dp[i][:-wi]+vi)
        
    print(dp[-1][-1])
 
if __name__=='__main__':
    main()

Solution (Python):
import numpy as np  

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

dp = np.zeros(w+1)

for _ in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value)

print(int(dp[-1]))

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

    print(dp[N][W])

if __name__=="__main__":
    main()

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

Solution (Python):





import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, wlim = list(map(int,ipti().split()))
    w = [0] * n
    v = [0] * n

    for i in range(n):
        w[i], v[i] = list(map(int,ipti().split()))

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

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

    print(dp[n][wlim])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter 
from fractions import gcd 
from copy import deepcopy 
from collections import Counter, deque, defaultdict 
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



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

    for _ in range(n):
        weight, value = map(int, input().split())

        dp[weight:] = np.maximum(dp[weight:], dp[:-weight]+value)

    print(int(dp[-1]))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter 
from fractions import gcd 
from copy import deepcopy 
from collections import Counter, deque, defaultdict 
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



def main():
    n, w = map(int, input().split())

    dp = np.zeros(w+1)
    for _ in range(n):
        weight, value = map(int, input().split())
        dp[weight:] = np.maximum(dp[:-weight]+value, dp[weight:])
     
    print(int(dp[-1]))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter 
from fractions import gcd 
from copy import deepcopy 
from collections import Counter, deque, defaultdict 
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



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

    dp = np.zeros([n+1, w+1])
    
    for i, itm in enumerate(wv):
        dp[i+1, :itm[0]] = dp[i, :itm[0]]
        dp[i+1, itm[0]:] = np.max([dp[i, itm[0]:], dp[i, :w-itm[0]+1] + itm[1]], axis=0)

    print(int(dp[n, w]))


if __name__ == "__main__":
    main()

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

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

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

ans = dp[n-1][w]

print(ans)

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

Solution (Python):
import sys
import numpy as np

input = sys.stdin.readline


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


lst = [list(map(int, input().split())) for ii in range(n)]



dp = np.zeros([n+1, w+1])

for i, ln in enumerate(lst):
    
    dp[i+1, :ln[0]] = dp[i, :ln[0]]
    
    dp[i+1, ln[0]:] = np.max([dp[i, ln[0]:], dp[i, :w-ln[0]+1]+ln[1]], axis=0)

print(int(dp[n, w]))

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

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

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

Solution (Python):
import numpy as np

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

dp = np.zeros((n+1, w+1), np.int64)

for i, (wi, vi) in enumerate(wv):
    dp[i+1] = dp[i]
    np.maximum(dp[i][wi:], dp[i][:-wi] + vi, out=dp[i+1][wi:])
"""
for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])
"""

print(dp[n][w])

Solution (Python):
import numpy as np

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 = np.zeros((W + 1), dtype=np.uint64)

for _w, _v in zip(w, v):
	np.maximum(dp[_w:], dp[:-_w] + _v, out=dp[_w:])
print(dp[-1])