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):
n, w = map(int, input().split())
lis = [[0, 0]]
for i in  range(n):
    lis.append(list(map(int, input().split())))

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

Solution (Python):
N,W = map(int, input().split())
wv = [[int(x) for x in 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] >= 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
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, W = na()
dp = [[0] * (W+1) for _ in range(n)]

w, v = na()
dp[0][w] = v

for i in range(1, n):
    w, v = na()
    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(max(dp[n-1]))

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

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

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

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

print(dp[N][W])

Solution (Python):
def solve(n, w, WV):
    dp = [[0] * (w + 1) for _ in range(n)]
    for w_limit in range(WV[0][0], w + 1):
        dp[0][w_limit] = WV[0][1]
    for i in range(1, n):
        for w_limit in range(1, w + 1):
            dw, dv = WV[i]
            if dw > w_limit:
                dp[i][w_limit] = dp[i - 1][w_limit]
            else:
                dp[i][w_limit] = max(dp[i - 1][w_limit], dp[i - 1][w_limit - dw] + dv)
    return dp[n - 1][w]

_n, _w = map(int, input().split())
_WV = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _w, _WV))

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

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

  w, v = map(int, input().split())
  values = values[:w-1] + [max(values[j], v + values[max(0, j-w)]) for j in range(w-1, W)]

print(values[-1])

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

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

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

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

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

print(dp[n][W])

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

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])

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

    for i in range(N):
        dp[i%2 ^ 1] = dp[i % 2]
        w, v = item[i]
        np.maximum(dp[i%2][:-w] + v, dp[i%2][w:], out=dp[i%2 ^ 1][w:])
        
    print(dp[N%2][W])

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

Product_Num, Limit_of_the_weight = map(int, input().split())

dp = np.zeros(Limit_of_the_weight + 1)

for i in range(Product_Num):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[:-w] + v, dp[w:])

print(int(np.max(dp)))

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

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])

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

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

if __name__ == "__main__":
    main()

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


dp = [[0 for _ in range(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):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







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

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

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

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

mod = 1000000007
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, mw = na()
wv = [na() for i in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
dp = [(mw + 1) * [0] for i in range(n + 1)]

for i in range(n):
    for j in range(mw + 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][mw])

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

mod = 1000000007
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, mw = na()
wv = [na() for i in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
dp = [(mw + 1) * [0] for i in range(n + 1)]

for i in range(n):
    for j in range(mw + 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][mw])

Solution (Python):
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    dp = [0] * (W+1)
    for w, v in WV:
        for i in range(W, w-1, -1):
            tmp_dp = dp[i-w] + v
            if dp[i] < tmp_dp:
                dp[i] = tmp_dp
    return max(dp)


if __name__ == "__main__":
    answer = solve()
    print(answer)

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

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

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

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

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

print(dp[0][W])

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

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
import numpy as np

dp=np.zeros([n+1,W+1],dtype=np.int64)
for i in range(n):
  w=items[i][0]
  v=items[i][1]
  dp[i+1][:w]=dp[i][:w]
  dp[i+1][w:]=np.maximum(dp[i][w:],dp[i][:-w]+v)
print(dp[-1][-1])

Solution (Python):
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')


dp = [[0 for _ in range(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):
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd

input = sys.stdin.readline  


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

    for i in range(n):
        for j in range(w+1):
            wi = WVs[i][0]
            vi = WVs[i][1]

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

    print(dp[n-1][w]) 
    return

if __name__ == "__main__":
    main()

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

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

    for i in range(min(W, W-w), -1, -1):
        if dp[i] != -1:
            dp[i+w] = max(dp[i+w], dp[i]+v)

print(max(dp))

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

print("%s" % mem[N-1][W])

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

Solution (Python):
N, W = map(int, input().split())
wv = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])


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

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

print(dp[W])

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

table = [[0] * (W + 1) for _ in range(N + 1)]
for n in range(N):
    for w in range(W + 1):
        addn = table[n][w - goods[n][0]] + goods[n][1] if w - goods[n][0] >= 0 else 0
        table[n + 1][w] = max(table[n][w], addn)
print(table[N][W])

Solution (Python):
import numpy as np

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

table = np.zeros((N + 1, W + 1), dtype=np.int64)
for n in range(N):
    tmp = np.zeros(W + 1, dtype=np.int64)
    tmp[goods[n][0]:] = table[n][:W + 1 - goods[n][0]] + goods[n][1]
    table[n + 1] = np.maximum(table[n], tmp)
print(table[N][W])

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())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])
  print(dp[-1])
  
if __name__ == "__main__":
  main()

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())
    np.maximum(dp[:W-w+1]+v, dp[w:W+1], out=dp[w:W+1])
  print(dp[W])
  
if __name__ == "__main__":
  main()

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.array((dp[:W-w+1]+v, dp[w:W+1])).max(axis=0)
  print(dp[W])
  
if __name__ == "__main__":
  main()

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

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

dp = [0]*(W+1) 

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

print(dp[-1])

Solution (Python):
import numpy as np

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

dp = np.zeros((N+1, W+1), dtype='uint64')

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

Solution (Python):
n, W = map(int, input().split())
ws = [0]*n
vs = [0]*n

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

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

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

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

max_index = a[0]
max_weight = a[1]

dp = [ [0] * (max_weight + 1) for j in range(max_index + 1)]

def solve():
    for i in range(max_index - 1, -1, -1):
        for j in range(max_weight + 1):
            if (j < b[i][0]):
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max([dp[i + 1][j], dp[i + 1][j - b[i][0]] + b[i][1]])
    print(dp[0][max_weight])

solve()

Solution (Python):
n,Capacity=list(int(i) for i in input().split())
maxv=0
W=[]
Values=[]
for i in range(n):
    w,v=list(int(i) for i in input().split())
    if v>maxv:
        maxv=v
    W.append(w)
    Values.append(v)
dp=[[0 for j in range(Capacity+1)]for i in range(n+1)]
for i in range(n+1):
    for w in range(Capacity+1):
        if i==0 or w==0:
            dp[i][w]=0
        elif w>=W[i-1]:
            dp[i][w]=max(dp[i-1][w],Values[i-1]+dp[i-1][w-W[i-1]])
        else:
            dp[i][w]=dp[i-1][w]
print(dp[-1][-1])

Solution (Python):
ln = input()
n, cap = ln.split()
n = int(n)
cap = int(cap)

'''
weights = [[0 for x in range(2)] for y in range(n)] 
values = [[0 for x in range(2)] for y in range(n)] 
mat = [[0 for x in range(2)] for y in range(1000000)] 
'''
weights = [0 for x in range(n)] 
values =  [0 for x in range(n)] 
mat =  [0 for x in range(1000000)] 

for i in range(n):
    ln = input()
    ln = ln.split()
    weights[i] = int(ln[0])
    values[i] = int(ln[1])
 
for i in range(n):
    for j in range(cap,weights[i]-1,-1):
        '''
        print(j)
        print(values[i])
        print(mat[j-weights[i]])
        '''
        mat[j] = max(mat[j], mat[j-weights[i]] + values[i])
 
        
print(mat[cap])

Solution (Python):

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

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

for i in range(1, N+1):
    w, v = map(int, input().split())
    dp[w:W+1] = np.maximum(dp[0:W-w+1]+v, dp[w:W+1])

print(dp[-1])

Solution (Python):

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

Solution (Python):
def main():
    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] >= 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])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    N, W = Scanner.map_int()
    V = [Scanner.map_int() for i 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):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if 0 <= j - V[i][0]:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j - V[i][0]] + V[i][1])
    print(dp[N][W])


if __name__ == "__main__":
    main()

Solution (Python):
def knap_sack_1(weight_and_value, w):
    n = len(weight_and_value)
    dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
    for w in range(1, w + 1):
        for i in range(1, len(weight_and_value) + 1):
            w_i, v_i = weight_and_value[i-1]
            if w >= w_i:
                dp[i][w] = max(dp[i][w], dp[i-1][w - w_i] + v_i)
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    return dp[-1][-1]

def get_input():
    n, k = list(map(int, input().split()))
    data = []
    for i in range(n):
        el = list(map(int, input().split()))
        data.append(el)
    return data, k

data, w = get_input()
print(knap_sack_1(data, w))

Solution (Python):
N, W, *t = map( int, open( 0 ).read().split() )
d = [[ 0 for _ in range( W + 1 ) ] for _ in range( N + 1 ) ]
ans = 0
 
i = 0
for w, v in zip( *[ iter( t )] * 2 ):
  for j in range( 1, W + 1 ):
    d[ i + 1 ][ j ] = d[ i ][ j ]
    if j - w >= 0:
      d[ i + 1 ][ j ] = max( d[ i ][ j - w ] + v, d[ i ][ j ] )
  i += 1
print( d[N][W])

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

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

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

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

Solution (Python):


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

print(max(dp[-1]))

Solution (Python):

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

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

for i in range(1, N+1):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[0:W-w+1] + v)

print(dp[-1])

Solution (Python):
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        if sum_w + ws[i] <= w:
            dp[i+1][sum_w + ws[i]] = max(dp[i+1][sum_w + ws[i]],
                                         dp[i][sum_w]+v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])

Solution (Python):
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

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

for sum_w in range(w+1):
    for i in range(1, n+1):
        if ws[i-1] <= sum_w:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-ws[i-1]]+v[i-1])
        else:
            dp[i][sum_w] = dp[i-1][sum_w]

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

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=[[-1]*(W+1) for _ in range(N+1)]

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

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

print(dp[N][W])

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

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

for i in range(n):
 for sum_w in range(w+1):

  if sum_w-l[i][0]>=0:
   dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])

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

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

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

print(dp[N][W])

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

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

print(dp[-1])

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

if __name__ == '__main__':
    main()

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

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

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

dp=[0]*(w+1)

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

print(max(dp))

Solution (Python):
INF = 10**10 - 1




N,Wmax = 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 = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0


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

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)

Solution (Python):
INF = 10**10 - 1




N,Wmax = 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 = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0


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

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)

Solution (Python):
N,W=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
w,v=zip(*List)
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+1][j],dp[i][j-w[i]]+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())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))

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

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

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

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

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

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

dp = np.zeros(W+1, dtype=np.int64)
for i in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[:-w]+v, dp[w:], out = dp[w:])

print(dp[-1])

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

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

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

print(dp[N][W])

Solution (Python):
def chmin(a, b):
  if (a > b):
    return b

  return a

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

  return a

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

dp = [[0] * (10**5+10) for i in [0] * (N+1)]

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

    dp[n+1][w] = chmax(dp[n+1][w], dp[n][w])


print(max(max(dp)))