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 unittest


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(8, [[3, 30], [4, 50], [5, 60]]),
            90
        )

    def test_2(self):
        self.assertEqual(
            think(
                5, [
                    [1, 1000000000], [1, 1000000000], [1, 1000000000],
                    [1, 1000000000], [1, 1000000000]
                ]
            ),
            5000000000
        )

    def test_3(self):
        self.assertEqual(
            think(15, [[6, 5], [5, 6], [6, 4], [6, 6], [3, 5], [7, 2]]),
            17
        )


def solve():
    w, list_of_w_and_v = read()
    result = think(w, list_of_w_and_v)
    write(result)


def read():
    n, w = read_int(2)
    list_of_w_and_v = []
    for _ in range(n):
        list_of_w_and_v.append(read_int(2))
    return w, list_of_w_and_v


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(w, list_of_w_and_v):
    invalid = -1

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

    for weight, value in list_of_w_and_v:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] == invalid:
                continue
            if i + weight >= len(dp):
                continue
            dp[i + weight] = max(
                    dp[i + weight],
                    dp[i] + value
            )
    return max(dp)


def write(result):
    print(result)


if __name__ == '__main__':
    
    solve()

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

def dp():
  inf = float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
    
  for i in range(N):
    w = WV[i][0]
    v = WV[i][1]
    for j in range(W+1):
      if w<=j: 
        dp[i+1][j]=max(dp[i][j-w]+v, dp[i][j])
      else: 
        dp[i+1][j]=dp[i][j]
  return dp[N][W]
print(dp())

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  dp=[[0 for _ in range(W+1)]for __ in range(n+1)]
  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

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


print(main())

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

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

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

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

print(max(dp))

Solution (Python):
import numpy as np

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

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

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

print(dp[-1])

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(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):
import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)

for i in range(1,n+1): 
  wn, vn = map(int, input().split())
  dp[wn:] = np.maximum(dp[wn:], dp[:-wn]+vn)
print(int(dp[-1]))

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

Solution (Python):
def solve():
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        weight.append(tmpw)
        value.append(tmpv)
    
    dp = [[0] * (W+1) for i in range(N+1)]
    for i in range(N):
        for w_i in range(W+1):
            if w_i - weight[i] >= 0:
                dp[i+1][w_i] = max(dp[i+1][w_i], dp[i][w_i - weight[i]] + value[i])
            
            dp[i+1][w_i] = max(dp[i+1][w_i], dp[i][w_i])

    print(dp[N][W])
if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])

Solution (Python):
N, W = [int(i) for i in input().split()]
weight, value = [], []

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

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

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

print(dp[N][W])

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,w = inpl()
wei = [0] * n
val = [0] * n
for i in range(n):
    wei[i],val[i] = inpl()

dp = [[0]*(w+5) for i in range(n+5)]
for i in range(n):
    for j in range(w+1):
        if wei[i] > j:
            dp[i+1][j] = dp[i][j]
            continue
        dp[i+1][j] = max(dp[i+1][j], dp[i][j-wei[i]]+val[i], dp[i][j])
print(dp[n][w])

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

print(dp[N][W])

Solution (Python):
n, max_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 _ in range(max_w+1)] for _ in range(n+2)]

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

print(max(dp[n]))

Solution (Python):
def knapsack1(weight_value, w):
    cur = [0] * (w + 1)
    
    for weight, value in weight_value:
        for i in reversed(range(weight, w + 1)):
            cur[i] = max(cur[i], cur[i - weight] + value)

    return cur[w]


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack1(weight_value, w)


print(main())

Solution (Python):
def knapsack1(weight_value, w):
    cur = [0] * (w + 1)
    nxt = [0] * (w + 1)

    for weight, value in weight_value:
        for i in range(1, weight):
            nxt[i] = cur[i]
        for i in range(weight, w + 1):
            nxt[i] = max(cur[i], cur[i - weight] + value)
        cur, nxt = nxt, cur
    return cur[w]


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack1(weight_value, w)


print(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]*(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(dp[-1][-1])

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

print(dp[N][W])

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

for i in range(n):
  ww[i],vv[i] = map(int,input().split())      
  
for i in range(1,n+1):
  for j in range(1,w+1):
    dp[i][j] = dp[i-1][j]
    if j - ww[i-1] >= 0:
      dp[i][j] = max(dp[i][j], \
                     dp[i-1][j-ww[i-1]] + vv[i-1])        

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

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 i in range(N):
    for j in range(0,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):
n, sum_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] * (sum_w + 1) for i in range(n+1)]

for i in range(n):
    for j in range(sum_w + 1):
        if j < weight[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

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

Solution (Python):


import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"


test = ""

"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""

test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()


(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
 np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()


N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

dp = np.zeros(W + 1, dtype="int64")
for w, v in WV:
    dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    
print(dp[-1])

Solution (Python):


import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"


test = ""

"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""

test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()


N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

dp = np.zeros(W + 1, dtype="int64")
for w, v in WV:
    dp[W:w-1:-1] = np.maximum(dp[W:w-1:-1], dp[W-w::-1] + v)

print(dp[-1])

Solution (Python):
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def plecak_rozwiazanie(pojemnosc, lista_przedmiotow): 
    bez_przedmiotu = [0] * (pojemnosc + 1)
    for waga, wartosc in lista_przedmiotow:
        z_przedmiotem = [None] * (pojemnosc + 1)
        for i in range(pojemnosc+1): 
            if waga > i: 
                z_przedmiotem[i] = bez_przedmiotu[i]
            else: 
                z_przedmiotem[i] = max(bez_przedmiotu[i-waga]+wartosc, bez_przedmiotu[i])
        bez_przedmiotu = z_przedmiotem
    return bez_przedmiotu[pojemnosc]

def plecak_1(): 
    N, W = wczytaj_liste()
    przedmioty = []
    for i in range(N): 
        waga, wartosc = wczytaj_liste()
        przedmioty.append((waga, wartosc))
    print (plecak_rozwiazanie(W,przedmioty))   
    
plecak_1()

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(n):
    for sum_w in range(1,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][sum_w],dp[i+1][sum_w])
        
print(dp[-1][-1])

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

    for i in range(N):
        now_i, next_i = i & 1, (i+1) & 1
        for j in range(W+1):
            if j - ws[i] >= 0:
                dp[next_i][j] = max(dp[now_i][j], dp[now_i][j-ws[i]] + vs[i])
            else:
                dp[next_i][j] = dp[now_i][j]
    print(max(dp[N & 1]))


if __name__ == '__main__':
    main()

Solution (Python):
n,w=map(int,input().split())
weight=[]
money=[]
weight.append(0)
money.append(0)
for i in range(n):
    s,v=map(int,input().split())
    weight.append(s)
    money.append(v)
dp= [[0 for i in range(w+1)] for j in range(n+1)]
for i in range(w+1):
    dp[0][i]=0

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

Solution (Python):

import sys
INF = float("inf")


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    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 j-w[i] >= 0:
                DP[i+1][j] = max(DP[i+1][j], DP[i][j-w[i]]+v[i])
    print(DP[N][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
input = sys.stdin.readline

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

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

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-w+1]+v, dp[w:], out=dp[w:])

print(dp[-1])

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

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

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


if __name__ == '__main__':
    solve()

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

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

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

print(dp[n][w])

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

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

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

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

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

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

print(max(dp[n][: w + 1]))

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

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

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

print(value[N][W])

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

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


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

for load in range(W+1):
  if load < ws[0]:
    
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:   
      
      Value[num][load] = Value[num-1][load]
      

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

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

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

inf = 1e10


Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:   
      
      Value[num][load] = Value[num-1][load]
      

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

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

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

inf = 1e10


Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   
      
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
      
      
    else:   
      
      Value[num][load] = Value[num-1][load]
      

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

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

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

inf = 1e10


Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:
      
      
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:
      Value[num][load] = max(Value[num][load], Value[num-1][load])

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

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

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

Solution (Python):
import sys
input = sys.stdin.readline
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(DP[-1])

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

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)

c = [[0 for j in range(W)] for i in range(n)]
for i in range(W):
    if i+1 < w[0]:
        c[0][i] = 0
    else:
        c[0][i] = v[0]

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

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

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

for i in range(N):
    for sum_w in range(W+1):
        
        if sum_w >= weight[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

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

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

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  w=[]
  v=[]
  dp=[[0 for _ in range(W+1)] for __ in range(n+1)]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n)[::-1]:
    for j in range(W+1):

      if j<w[i]:
        dp[i][j]=dp[i+1][j]

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

  return dp[0][W]


print(main())

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

print(max(dp[n]))

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

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=int)

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

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

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

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

Solution (Python):
import collections


Item = collections.namedtuple("Item", ("weight", "value"))


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

    
    for n in range(1, N + 1):
        
        for w in range(W + 1):
            
            item = items[n - 1]
            
            if w - item.weight >= 0:
                dp[n][w] = max(dp[n][w], dp[n - 1][w - item.weight] + item.value)
            
            dp[n][w] = max(dp[n][w], dp[n - 1][w])

    ans = dp[N][W]
    print(ans)


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]*(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], 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())
WV=[list(map(int,input().split())) for i in range(n)]


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

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

Solution (Python):
import sys
input=sys.stdin.readline
def fun(n,w):
 cos=[0]*(w+1)
 for i in range(n):
  w1,v1=map(int,input().split())
  for j in range(w,w1-1,-1):
   f=cos[j-w1]+v1
   if(cos[j]<f):
    cos[j]=f
 print(cos[-1])
n,w=map(int,input().split())
fun(n,w)

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

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

print(max(dp[-1]))

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

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

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

print(max(dp))

Solution (Python):

import math
import datetime
import itertools
import sys
import copy






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


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

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


print (max(dp[N][:]))

Solution (Python):

import math
import datetime
import itertools
import sys
import copy






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



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

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


print (max(dp[N]))

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