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^9  1 \leq w_i \leq W  1 \leq v_i \leq 10^3         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 1 1000000000
1000000000 10      Sample Output 2 10       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 collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
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)) 

N,W = imn()
max_v = 100001
wv = [iln() for _ in range(N)]
max_w = 10**10
dp = [[max_w for _ in range(max_v+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(max_v):
        if sum_v - wv[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-wv[i][1]]+wv[i][0])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0
for sum_v in range(max_v):
    if dp[N][sum_v] <= W: ans = sum_v
print(ans)

Solution (Python):
def solve(N, W, weight_values):
  sum_values = 0
  for w_v in weight_values:
    sum_values += w_v[1]

  
  dp = [float('inf') for _ in range(sum_values + 1)]
  dp[0] = 0

  for i in range(N):
    i_weight, i_value = weight_values[i]
    for v in range(sum_values, i_value - 1, -1):
      temp = dp[v - i_value] + i_weight
      if temp < dp[v]:
        dp[v] = temp

  ans = 0
  for v in range(sum_values + 1):
    if dp[v] <= W:
      ans = max(ans, v)

  print(ans)

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


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)

Solution (Python):
import numpy as np

N,W = map(int,input().split())
item = []
V_MAX = 0
for _ in range(N):
    w, v = map(int,input().split())
    V_MAX += v
    item.append([w,v])
dp = np.array([float('inf')]*(V_MAX+1))
dp[0] = 0
pos = np.zeros(V_MAX+1, dtype = "int32")
pos[0] = 1
for w,v in item:
    dp = np.minimum(dp, np.concatenate([np.array([np.inf]*v),np.roll(dp,v)[v:]]) + np.dot(np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]),w))
    pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))
    pos[pos > 0] = 1
res = 0
for i in range(V_MAX + 1):
    if dp[i]<=W and res < i : res = i
print(res)

Solution (Python):
import numpy as np

N,W = map(int,input().split())
item = []
V_MAX = 0
for _ in range(N):
    w, v = map(int,input().split())
    V_MAX += v
    item.append([w,v])
dp = np.array([float('inf')]*(V_MAX+1))
dp[0] = 0
pos = np.array([0]*(V_MAX+1))
pos[0] = 1
for w,v in item:
    dp = np.minimum(dp, np.concatenate([np.array([np.inf]*v),np.roll(dp,v)[v:]]) + np.dot(np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]),w))
    pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))
    pos[pos > 0] = 1
res = 0
for i in range(V_MAX + 1):
    if dp[i]<=W and res < i : res = i
print(res)

Solution (Python):




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







dp = [[float("inf")]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0 


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



for i,j in enumerate(dp[-1]):
    if j <= W: 
        ans = i
print(ans)

Solution (Python):

from collections import defaultdict


def main():
    INF = 1 << 30
    N, W, *WV = map(int, open(0).read().split())
    dp = defaultdict(lambda: INF)  
    dp[0] = 0
    for w, v in zip(*[iter(WV)] * 2):
        for cur_v, cur_w in tuple(dp.items()):
            if w + cur_w <= W:
                dp[v + cur_v] = min(dp[v + cur_v], w + cur_w)
    print(max(dp.keys()))


if __name__ == "__main__":
    main()

Solution (Python):
import unittest


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

    def test_2(self):
        self.assertEqual(
            think(1000000000, [[1000000000, 10]]),
            10
        )

    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):
    w_max = 10 ** 9
    invalid = w_max + 1
    v_max = 10 ** 3
    n_max = 100

    
    dp = [invalid for _ in range(v_max * n_max + 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 + value >= len(dp):
                continue
            dp[i + value] = min(
                    dp[i + value],
                    dp[i] + weight
            )

    for i in range(len(dp) - 1, -1, -1):
        if dp[i] == invalid:
            continue
        if dp[i] > w:
            continue
        return i


def write(result):
    print(result)


if __name__ == '__main__':
    
    solve()

Solution (Python):
n=0
W=0
n,W=map(int,input().split())
dp=[W+1]*101010
dp[0]=0
for i in range(n):
    w,v=map(int,input().split())
    j=100000
    while j>=0:
        if dp[j+v]>dp[j]+w:
            dp[j+v]=dp[j]+w
        j-=1
ans=0
for v in range(len(dp)):
    if dp[v]<=W:
        ans=v
print(ans)

Solution (Python):
import numpy as np

N, W = map(int, input().split())
v_max = 10**3

dp = np.ones(v_max*N+1, dtype=int) * (10**9+1)
dp[0] = 0

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


print(np.where(dp <= W)[0][-1])

Solution (Python):
import numpy as np
n, w = map(int, input().split())
v_max = 1000
num_v = v_max*n
INF = 10**9+1
dp = np.full(num_v+1, INF, dtype=int)
dp[0] = 0
for i in range(1,n+1):
  wn, vn = map(int, input().split())
  dp[vn:] = np.minimum(dp[vn:], dp[:-vn]+wn)
for i in range(len(dp)-1, -1, -1):
  if dp[i] <= w:
    print(i)
    break

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

INF = 10**15
dp = [INF for _ in range(10**5 + 1)] 
dp[0] = 0

for i in range(N):
  w, v = wv[i]
  for j in range(10**5, -1, -1):
    if dp[j] != INF and j + v <=  10**5:
      dp[j+v] = min(dp[j+v], dp[j]+w)

answer = 0
for i in range(10**5+1):
  if dp[i] <= W:
    answer = i
    
print(answer)

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)

f_inf = float('inf')
max_v = 100000

dp = [f_inf]*(max_v+2)
dp[0] = 0

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

ans = 0
for i in range(max_v+1):
    if dp[i] <= max_w:
        ans = max(ans, i)
print(ans)

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 = [[float('inf')] * (10 ** 5 + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(10 ** 5 + 1):
        if j - value[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - value[i]] + weight[i])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
for j in range(10 ** 5, -1, -1):
    if dp[n][j] <= w:
        print(j)
        break

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

INF = float('inf')
ww = [0]*n
vv = [0]*n
vm = 1000
dp = [[INF]*(n*vm+1) for _ in range(n+1)]

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

dp[0][0] = 0  
for i in range(1,n+1):
  dp[i][0] = 0
  for j in range(1,n*vm+1):        
    if j < vv[i-1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-vv[i-1]] + ww[i-1])        

ans = 0
for i in range(n*vm+1):
  if dp[n][i]<=w:
    ans = i
print(ans)

Solution (Python):
def knapsack2(weight_value, w):
    v = sum(value for weight, value in weight_value)
    cur = [float("inf")] * (v + 1)
    cur[0] = 0

    for weight, value in weight_value:
        for i in reversed(range(value, v + 1)):
            cur[i] = min(cur[i], cur[i - value] + weight)

    for value in reversed(range(v + 1)):
        if cur[value] <= w:
            return value


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 knapsack2(weight_value, w)


print(main())

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

dp = [[10**9]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(10**5+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i][j] + lstW[i] <= W:
            dp[i+1][j+lstV[i]] = min(dp[i+1][j+lstV[i]], dp[i][j]+lstW[i])
ans = []
for i in range(max(lstV)*N+1):
    if dp[-1][i] <= W:
        ans.append(i)
print(max(ans))

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

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

    inf = W+1
    dp = [[inf] * (10**5+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        w, v = wv[i]
        for j in range(10**5+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] + w <= W:
                dp[i+1][j+v] = min(dp[i+1][j+v], dp[i][j] + w)
    for v in range(10**5, -1, -1):
        if dp[-1][v] <= W:
            print(v)
            exit()


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

V = sum(v)
dp = [[2**60]*(V+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - v[i] >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for i in range(N+1):
    for j in range(V+1):
        if dp[i][j] <= W:
            ans = max(ans,j)
print(ans)

Solution (Python):
n, w = map(int, input().split())
l1 = [list(map(int, input().split())) for i in range(n)]
v = 0
for i in range(n):
  v += l1[i][1]
d = [10 ** 9 + 1] * (v + 1)
d[0] = 0
for i in range(n):
    for j in range(v, -1, -1):
        d[j] = min(d[j], d[j - l1[i][1]] + l1[i][0])
answer = 0
for j in range(v + 1):
    if  w >= d[j]:
        answer = max(answer, j)
print(answer)

Solution (Python):
N, W = map(int, input().split())
MV = (10**3)*N+1
dp = [[0] + [10**18]*(MV-1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, MV):
        dp[i][j] = min(dp[i-1][j], dp[i-1][max(0, j-v)]+w)
for i in range(MV):
    if dp[N][MV-i-1] <= W:
        print(MV-i-1)
        break

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)]
V = sum([v for w, v in wv])

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

for i in range(N):
    for j in range(0, V+1):
        w, v = wv[i]
        if (j-v) >= 0:
            dp[i+1][j] = min([dp[i][j], dp[i][j-v]+w])
        else:
            dp[i+1][j] = dp[i][j]

ans = 0
for i in range(0, V+1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Solution (Python):


import numpy as np

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


test = ""

"""
3 8
3 3
4 5
5 6
ans 9
"""

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

"""
N<100, W<10*9
wi<10**9, vi<10**3 
"""

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)], dtype="int64")
Wsum = np.sum(WV[:, 0])
Vsum = np.sum(WV[:, 1])

dp = np.full(Vsum+1, Wsum, dtype="int64")
for w, v in WV:
    dp[:Vsum-v+1] = np.min(np.vstack([dp[:Vsum-v+1], dp[v:] - w]), axis=0)
    

print(dp[dp < W+1].size - 1)

Solution (Python):


import numpy as np

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


test = ""

"""
3 8
3 3
4 5
5 6
ans 9
"""

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

"""
N<100, W<10*9
wi<10**9, vi<10**3 
"""

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)], dtype="int64")
Wsum = np.sum(WV[:, 0])
Vsum = np.sum(WV[:, 1])

dp = np.full(Vsum+1, Wsum, dtype="int64")
for w, v in WV:
    dp[:Vsum-v+1] = np.min(np.vstack([dp[:Vsum-v+1], dp[v:] - w]), axis=0)
    
print(np.where(dp < W+1)[0][-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_2(pojemnosc, lista_przedmitow):
    bez_przedmiotu = [0] + [10**18] * len(lista_przedmitow) * 1000
    for waga, wartosc in lista_przedmitow:
        z_przedmiotem = [None] * (len(lista_przedmitow) * 1000 +1)
        for i in range(len(z_przedmiotem)): 
            if wartosc > i: 
                z_przedmiotem[i] = bez_przedmiotu[i]
            else: 
                z_przedmiotem[i] = min(bez_przedmiotu[i-wartosc]+waga, bez_przedmiotu[i])
        bez_przedmiotu = z_przedmiotem
    for i in reversed(range(len(bez_przedmiotu))):
        if bez_przedmiotu[i] <= pojemnosc:
            return i

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

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())
vmax = max(v)
dp = [[0]*(N * vmax + 1) for i in range(N + 1)]
dp[0][0] = 0
for j in range(N * vmax):
    dp[0][j + 1] = float("inf")

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

ans = 0
for j in range(N * vmax + 1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Solution (Python):
def main():
    INF = 10 ** 12
    N, W = map(int, input().split())
    ws, vs = [], []
    for _ in range(N):
        w, v = map(int, input().split())
        ws.append(w)
        vs.append(v)
    sum_v = sum(vs)
    dp = [[INF] * (sum_v + 1) for _ in range(2)]
    dp[0][0] = 0
    for i in range(N):
        now_i, next_i = i & 1, (i+1) & 1
        for j in range(sum_v + 1):
            if j - vs[i] >= 0:
                dp[next_i][j] = min(dp[now_i][j], dp[now_i][j - vs[i]] + ws[i])
            else:
                dp[next_i][j] = dp[now_i][j]
    ans = 0
    for i in range(sum_v + 1):
        if dp[N&1][i] <= W:
            ans = i
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict
INF = float("inf")


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

    L = 10**5+1
    DP = [[INF]*(L) for _ in range(N+1)]
    for i in range(N+1):
        DP[i][0] = 0

    for i in range(N):
        for j in range(L):
            DP[i+1][j] = DP[i][j]
            if 0 <= j-v[i] < L:
                DP[i+1][j] = min(DP[i+1][j], DP[i][j-v[i]]+w[i])

    for j in range(L-1, -1, -1):
        if DP[N][j] <= W:
            print(j)
            return

    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 = [[10**10] * (10**5 + 1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for j in range(10**5 + 1):
    for i in range(n):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if j + wv[i][1] < 10**5 + 1:
            dp[i+1][j+wv[i][1]] = min(dp[i][j] + wv[i][0], dp[i][j+wv[i][1]])

for i in range(10**5,0,-1):
    if dp[-1][i] <= w:
        print(i)
        exit()

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

dp = [[10**11] * (n * (10**3) + 1) for _ in range(n+1)]

for i in range(1,n+1):
    dp[i-1][0] = 0
    w_temp, v_temp = wv[i-1]
    for j in range(1, (n*10**3)+1):
        if(j >= v_temp):
            dp[i][j] = min(dp[i-1][j],
                            dp[i-1][j-v_temp] + w_temp)
        else:
            dp[i][j] = dp[i-1][j]

last = dp[-1]
ans = 0
for j in range((n*10**3)+1):
    if(last[j] <= w):
        ans = j

print(ans)

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

weight = [0]*n
value = [0]*n

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

v_sum = sum(value)

dp = [[10**12 for _ in range(v_sum+1)] for i in range(n)]

for i in range(n):
    if i == 0:
        dp[i][0] = 0
        dp[i][value[0]] = weight[0]
    else:
        for k in range(v_sum+1):
            if k < value[i]:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-value[i]]+weight[i])

for i in range(v_sum, -1, -1):
    if dp[n-1][i] <= w:
        print(i)
        exit()

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

weight = []
value = []

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

v_sum = sum(value)

dp = [[10**12 for _ in range(v_sum+1)] for i in range(n)]

for i in range(n):
    if i == 0:
        dp[i][0] = 0
        dp[i][value[0]] = weight[0]
    else:
        for k in range(v_sum+1):
            if k < value[i]:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-value[i]]+weight[i])

for i in range(v_sum, -1, -1):
    if dp[n-1][i] <= w:
        print(i)
        exit()

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

weight = []
value = []

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

v_sum = sum(value)

dp = [[float('inf') for _ in range(v_sum+1)] for i in range(n)]

for i in range(n):
    if i == 0:
        dp[i][0] = 0
        dp[i][value[0]] = weight[0]
    else:
        for k in range(v_sum+1):
            if k < value[i]:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-value[i]]+weight[i])

for i in range(v_sum, -1, -1):
    if dp[n-1][i] <= w:
        print(i)
        exit()

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

dp = [[float('inf') for _ in range(10**5+1)] for i in range(n)]

v_sum = 0

for i in range(n):
    wi, vi = map(int, input().split())
    v_sum += vi
    if i == 0:
        dp[i][0] = 0
        dp[i][vi] = wi
    else:
        for k in range(v_sum+1):
            if k < vi:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-vi]+wi)

for i in range(v_sum, -1, -1):
    if dp[n-1][i] <= w:
        print(i)
        exit()

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

dp = [[float('inf') for _ in range(10**5+1)] for i in range(n)]

for i in range(n):
    wi, vi = map(int, input().split())
    if i == 0:
        dp[i][0] = 0
        dp[i][vi] = wi
    else:
        for k in range(10**5+1):
            if k < vi:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-vi]+wi)

for i in range(10**5+1)[::-1]:
    if dp[n-1][i] <= w:
        print(i)
        exit()

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

for i in range(N):
    dp[i][0] = 0
    for j in range(sum(value)+1):
        if j < value[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-value[i]]+weight[i])
            
for j in range(sum(value), -1, -1):
    if dp[N][j] <= W:
        ans = j
        break
        
print(ans)

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

N, W = map(int, input().split())
ws = [0]
vs = [0]

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

inf = sum(ws)+1
V = int(sum(vs))   


Weight = [[inf for _ in range(V+1)] for __ in range(N+1)]

if ws[1] <= W:
  Weight[1][vs[1]] = ws[1]
  value_max = vs[1]
else:
  value_max = 0

for _ in range(N+1):
  Weight[_][0] = 0



for num in range(2, N+1):
  for value in range(1, V+1):
    if value >= vs[num]:   
      Weight[num][value] = min(Weight[num][value], Weight[num-1][value], Weight[num-1][value-vs[num]] + ws[num])
      if Weight[num][value] <= W:
        value_max = max(value_max, value)
      else:
        Weight[num][value] = inf
    else:   
      
      Weight[num][value] = Weight[num-1][value]
      


print(value_max)

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

N, W = map(int, input().split())
ws = [0]
vs = [0]

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

inf = 2e11
V = int(sum(vs))   


Weight = [[inf for _ in range(V+1)] for __ in range(N+1)]

if ws[1] <= W:
  Weight[1][vs[1]] = ws[1]
  value_max = vs[1]
else:
  value_max = 0

for _ in range(N+1):
  Weight[_][0] = 0



for num in range(2, N+1):
  for value in range(1, V+1):
    if value >= vs[num]:   
      Weight[num][value] = min(Weight[num][value], Weight[num-1][value], Weight[num-1][value-vs[num]] + ws[num])
      if Weight[num][value] <= W:
        value_max = max(value_max, value)
      else:
        Weight[num][value] = inf
    else:   
      
      Weight[num][value] = Weight[num-1][value]
      


print(value_max)

Solution (Python):
N, W = map(int, input().split())
V = 10**5
weight = [[float("inf") for i in range(V + 1)] for j in range(N + 1)]
weight[0][0] = 0
for i in range(1, N + 1):
    w, v = map(int, input().split())

    for j in range(V + 1):
        if j - v >= 0:
            weight[i][j] = min(weight[i-1][j-v] + w, weight[i-1][j])
        else:
            weight[i][j] = weight[i-1][j]

ans = 0
for j in range(V + 1):
    if weight[N][j] <= W:
        ans = max(ans, j)

print(ans)

Solution (Python):
N, W = map(int, input().split())
INF = 10 ** 9 + 7
wvLst = [list(map(int, input().split())) for _ in range(N)]
dp = [[INF for i in range(10 ** 5 + 1)] for _ in range(N + 1)]

dp[0][0] = 0
for i in range(N):
    for j in range(10 ** 5 + 1):
        if j - wvLst[i][1] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - wvLst[i][1]] + wvLst[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
ans = 0
for i in range(10 ** 5 + 1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Solution (Python):
n,w=map(int,input().split())
sum_val=0
ws=[]
vs=[]
for i in range(n):
    wi,vi=map(int,input().split())
    ws.append(wi)
    vs.append(vi)
    sum_val+=vi
dp=[10**12 for i in range(sum_val+1)]
dp[0]=0
for i in range(n):
    for j in range(sum_val-vs[i],-1,-1):
        dp[j+vs[i]]=min(dp[j+vs[i]],dp[j]+ws[i])
ans=0
for i in range(sum_val+1):
    if dp[i]<=w:
        ans=max(ans,i)
print(ans)

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)
max_v = n*max(v)
c = [[0 for j in range(max_v)] for i in range(n)]

for i in range(max_v):
    if i+1 > v[0]:
        c[0][i] = float('inf')
    else:
        c[0][i] = w[0]

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

Solution (Python):
N, W = map(int, input().split())
INF = float('inf')
MAX_V = 100100

dp = [[INF for _ in range(MAX_V+1)] for _ in range(N+1)]
dp[0][0] = 0
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_v in range(MAX_V + 1):
        
        if sum_v - value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i])
        
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0
for sum_v in range(MAX_V + 1):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Solution (Python):

 
import math
import itertools
import sys
import copy
 

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

Hw = 0
Hv = 1
 

Vmax = (10**3) * N

 

dp = [[sys.maxsize for _ in range(Vmax+1)] for _ in range(N+1)]

for i in range(1, N+1) :
  
  dp[i][H[i][Hv]] = min(H[i][Hw], dp[i][H[i][Hv]])
  
  for j in range(Vmax+1) :
    if dp[i-1][j] != sys.maxsize :
      
      dp[i][j] = min(dp[i-1][j], dp[i][j])
      
      if (j + H[i][Hv]) <= Vmax+1 :
        dp[i][j + H[i][Hv]] = min(dp[i-1][j] + H[i][Hw], dp[i][j + H[i][Hv]])
        
  
  """
  out = copy.deepcopy(dp[i][:])
  line = ""
  for x in range(len(out)) :
      if out[x] == sys.maxsize :
        line += "_" + "\t"
      else :    
        line += str(out[x]) + "\t"
  print(line)
  """

for k in range(Vmax) :
  if dp[N][Vmax-k] <= W :
    print(Vmax-k)
    exit()

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

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wv = np.array(wv)
V = max(wv[:, 1])
dp = np.array([float('inf')]*(N*V+1))

dp[0] = 0
for i in range(N):
    w, v = wv[i]
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
print(max(np.where(dp<=W)[0]))

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

v_max = 100*(10**3) + 1
INF = 10**18

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

for i in range(n):
    weight, val = info[i]
    for j in range(v_max):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if j - val >= 0:
            dp[i+1][j] = min(dp[i][j-val] + weight, dp[i+1][j])

ans = 0
for i, num in enumerate(dp[n]):
    if num <= w:
        ans = i
print(ans)

Solution (Python):
import sys
import numpy as np

input = sys.stdin.readline


def main():
    N, W = [int(i) for i in input().strip().split()]
    MAX_V = 10**3 * N

    dp = np.full([N + 1, MAX_V + 1], np.inf)
    dp[0][0] = 0
    for n in range(N):
        w, v = [int(i) for i in input().strip().split()]
        dp[n + 1] = dp[n]
        dp[n + 1][v:] = np.minimum(dp[n][v:], dp[n][:-v] + w)

    ans = np.max(np.where(dp <= W))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import collections


MAX_N = 110
MAX_V = 100100

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 = [[float('inf')] * MAX_V for _ in range(MAX_N)]

    dp[0][0] = 0

    for i in range(N):
        item = items[i]
        for sum_v in range(MAX_V):
            
            if sum_v - item.value >= 0:
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item.value] + item.weight)
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])

    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_right

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

sum_v_max = n * 1000
dp = [0] + [float('inf')] * sum_v_max

for i in range(n):
    for j in range(sum_v_max, 0, -1):
        dp[j] = min(dp[j], dp[max(j - lst[i][1], 0)] + lst[i][0])

print(bisect_right(dp, w) - 1)

Solution (Python):
N,W=map(int,input().split())
INF=10**9+1
import numpy as np
dp=np.full(N*1000+1,INF,dtype=int)
dp[0]=0
for i in range(N):
  w,v=map(int,input().split())
  np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])

for i in range(len(dp)-1,-1,-1):
  if dp[i]<=W:
    print(i)
    break

Solution (Python):
N, W = map(int, input().split())
INF = 10**12
goods = [tuple(map(int, input().split())) for _ in range(N)]
total_val = 0
for item in goods:
    total_val += item[1]
dp = [[INF for i in range(total_val+1)] for j in range(N+1)]
dp[0][0] = 0
for i, item in enumerate(goods):
    i += 1
    for v in range(total_val+1):
        if v < item[1]:
            dp[i][v] = dp[i-1][v]
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-item[1]] + item[0])

for i in range(total_val+1):
    if dp[N][i] <= W:
        ans = i
print(ans)