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 math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,W = imn()
weight = []
value = []
for _ in range(N):
    w,v = imn()
    weight.append(w)
    value.append(v)

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

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

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

for n in range(1, N + 1):
    for w in range(W + 1):
        if wv_array[n - 1][0] > w:
            ans_array[n][w] = ans_array[n - 1][w]
        else:
            ans_array[n][w] = max(
                ans_array[n - 1][w], ans_array[n - 1][w - wv_array[n - 1][0]] + wv_array[n - 1][1])


print(ans_array[N][W])

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

def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    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(1, N+1):
        for j in range(1, 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):
import numpy as np


n, capacity = map(int, input().split())
dp = np.zeros(capacity + 1, dtype=np.int64)
for _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])

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

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

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


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


if __name__ == "__main__":
    main()

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

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



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


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

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

print(dp[N][W])

Solution (Python):
from sys import stdin

def main():
    n,w = map(int, input().split())
    ary = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dp = [[0 for _ in range(w+1)] for _ in range(n)]
    for i in range(n):
        for y in range(1,w+1):
            if i == 0:
                dp[i][y] = ary[i][1] if ary[i][0] <= y else 0
            elif ary[i][0] <= y:
                dp[i][y] = max(dp[i-1][y-ary[i][0]] + ary[i][1],dp[i-1][y])
            else:
                dp[i][y] = dp[i-1][y]
    print(dp[n-1][w])

if __name__ == '__main__':
    main()

Solution (Python):

import sys


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

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


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


if __name__ == '__main__':
    main()

Solution (Python):
N_W=list(map(int,input().split()))
N=N_W[0]
W=N_W[1]
items=[]
for i in range(N):
	sets=list(map(int,input().split()))
	items.append(sets)
knapsack=[[0 for i in range(W+1)] for j in range(N+1)]

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

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

def knapsack(n,w,wv):
    inf = float('inf')
    dp = [[-inf for _ in range(w+1)] for _ in range(n+1)]
    for i in range(w+1): dp[0][i] = 0

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

print(knapsack(n,w,wv))

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


dp=[]
for k in range(N+1):
    dp.append([0]*(W+1))


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



print(dp[N][W])

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

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

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

dp=[[-float("inf") for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
  dp[0][i]=0

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

print(str(dp[N][W]))

Solution (Python):
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)
dp = [[0]*(W+1) for j in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if w[i] <= sum_w:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-w[i]]+v[i])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]

print(dp[N][W])

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

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

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

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

print(max(dp[-1]))

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

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

print(dp[n][W])

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

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

Solution (Python):
n,w_lim = map(int,input().split())
dp = [[0 for i in range(w_lim+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)


for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0


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

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

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

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

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

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

print(dp[N][W])

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

x, y  = map(int, input().split())
li =[]
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(1, y+1):
        if j - li[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j - li[i][0] ]+ li[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[x][y])

Solution (Python):




inf = 10**9+7

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

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

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

    print(max(dp[N]))


if __name__ == "__main__":
    main()

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

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

dp = [[-float('inf')]*(W+1) for _ in range(N+1)]
for w in range(W+1):
  dp[0][w] = 0

  
for i in range(0, N):
  for w in range(0, 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]

print(dp[N][W])

Solution (Python):






"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        for j in range(max_capacity, w - 1, -1):
            tmp = dp[j - w] + v
            if dp[j] < tmp:
                dp[j] = tmp
    return dp[max_capacity]


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Solution (Python):

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

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


main()

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

def solve(n, w ,weights, values):
    def rec_solve(cw, cv, max_w, i):
        nonlocal weights, values
        
        if i == -1:
            return cv
        
        
        if weights[i] + cw <= max_w:
            return max(rec_solve(cw+weights[i], cv + values[i], max_w, i-1),
                        rec_solve(cw, cv, max_w, i-1))

        else:
            
            return rec_solve(cw, cv, max_w, i-1)

    return rec_solve(0, 0, w, n-1)

def solve_fast(n_items, max_w, weights, values):
    dp =  [[0]*(max_w+1) for _ in range(n_items)]
    dp[0] = [values[0] if i >= weights[0] else 0 for i in range(max_w+1)]

    for r in range(1, n_items):
        cw, cv = weights[r], values[r]
        for c in range(max_w+1):
            if cw > c:
                dp[r][c] = dp[r-1][c]
            else:
                dp[r][c] = max(dp[r-1][c], dp[r-1][c-cw] + cv)

    
        

    return dp[-1][-1]


print(solve_fast(N, W, weights, values))

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

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(np.max(dp)))

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):
def solve(c, a):
    dp = [0]*(c+1)
    for w, p in a:
        for i in range(c, -1, -1):
            if dp[i] > 0 and i+w < c+1:
                dp[i+w] = max(dp[i+w], dp[i] + p)
        if w < c+1:
            dp[w] = max(dp[w], p)
    return max(dp)
  
n, k = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
print(solve(k, a))

Solution (Python):
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split()))for _ in range(n)])
dp = [0]*(w+1)
for i in range(1, n+1):
    for j in reversed(range(1, w+1)):
        if j-weights[i-1] < 0:
            continue
        dp[j] = max(dp[j], dp[j-weights[i-1]]+values[i-1])
print(dp[-1])

Solution (Python):
n,w=map(int,input().split())
cost=[[0 for i in range(w+1)] for j in range(n+1)]
value=[tuple(map(int,input().split())) for i in range(n)]
for i in range(1,n+1):
  for j in range(w+1):
    weight_=value[i-1][0]
    value_=value[i-1][1]
    if j < weight_:
      cost[i][j]=cost[i-1][j]
    else:
      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])
print(cost[-1][-1])

Solution (Python):
import numpy as np
n, w = map(int, input().split())
wv_list = [[int(i) for i in input().split()] for i in range(n)]

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

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

Solution (Python):
import numpy as np

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

dp = np.zeros(w+1)

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

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

Solution (Python):
def resolve():
    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] * (W + 1)]
    for i in range(N):
        d = []
        for w in range(W + 1):
            if w >= weight[i]:
                d.append(max(dp[-1][w - weight[i]] + value[i], dp[-1][w]))
            else:
                d.append(dp[-1][w])
        dp.append(d)
    print(dp[-1][-1])


if __name__ == "__main__":
    resolve()

Solution (Python):
n,w = map(int,input().split())
dp = [-1] * (w + 1)
dp[0] = 0
for i in range(n):
  weight,value = map(int,input().split())
  for j in range(w,-1,-1):
    if dp[j] != -1 and weight + j <= w:
      dp[weight+j] = max(dp[weight+j],dp[j] + value)
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 _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if 0 <= j-wv[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
        dp[i][j] = max(dp[i-1][j], dp[i][j])

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

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

Solution (Python):

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

wv.sort()

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

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

ans = dp[-1]
print(ans)

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

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

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

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    dp = []
    for _ in range(N):
        l = [0]*(W + 1)
        dp.append(l)
    
    
    for j in range(W + 1):
        dp[0][j] = v[0] if j >= w[0] else 0

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



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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict


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



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

if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):



def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

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

    for i, item in enumerate(items):
        for i_w in range(w + 1):
            if i_w >= item[0]:
                dp[i + 1][i_w] = max(dp[i][i_w - item[0]] + item[1], dp[i][i_w])
            else:
                dp[i + 1][i_w] = dp[i][i_w]

    print(dp[n][w])


if __name__ == '__main__':
    main()

Solution (Python):
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110000 for i in range(110)]


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

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

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

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

Solution (Python):
N, W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int,input().split())
  dp[n][:] = dp[n-1][:]
  for w in range(W+1):
    if w + wn > W: break
    dp[n][w+wn] = max(dp[n][w+wn],dp[n-1][w]+vn)
print(max(dp[N]))

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

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

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

dp = [[0] * (W + 1) for _ in range(N)]
for w in range(W + 1):
  if (w == 0):
    continue
  for i, wv in enumerate(WV):
    if(w < wv[0]):
      if (i - 1 < 0):
        dp[i][w] = 0
      else:
        dp[i][w] = dp[i - 1][w]
    else:
      if (i - 1 < 0):
        val1 = 0
      else:
        val1 = dp[i - 1][w]
      
      if (((i - 1) < 0) or ((w - wv[0]) < 0)):
        val2 = wv[1]
      else:
        val2 = wv[1] + dp[i - 1][w - wv[0]]
      dp[i][w] = val1 if (val1 > val2) else val2

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

Solution (Python):
import numpy as np

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

print(dp[-1])

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

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

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

print(max(x))

Solution (Python):
n, w = [int(i) for i in input().split()]
dp = [0] * (w + 1)
for _ in range(n):
    u, v = [int(i) for i in input().split()]
    for i in reversed(range(w - u + 1)):
        dp[i + u] = max(dp[i + u], dp[i] + v)

print(max(dp))

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,w = map(int,readline().split())
WV = []
for i in range(n):
	WV.append(list(map(int,readline().split())))

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

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

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

Solution (Python):
n, m = map(int, input().split())
W, V = [], []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
A = [0 for j in range(m+1)]
for i in range(n):
    B = []
    for j in range(W[i]):
        B.append(A[j])
    for j in range(W[i], m+1):
        B.append(max(A[j], A[j-W[i]]+V[i]))
    A = B
print(A[m])

Solution (Python):
n, m = map(int, input().split())
W, V = [], []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
A = [0 for j in range(m+1)]
for i in range(n):
    B = []
    for j in range(W[i]):
        B.append(A[j])
    for j in range(W[i], m+1):
        B.append(max(A[j], A[j-W[i]]+V[i]))
    A = B
print(A[m])

Solution (Python):
n, m = map(int, input().split())
W, V = [], []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
A = [0 for j in range(m+1)]
for i in range(n):
    B = []
    for j in range(W[i-1]):
        B.append(A[j])
    for j in range(W[i-1], m+1):
        B.append(max(A[j], A[j-W[i-1]]+V[i-1]))
    A = B
print(A[m])