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):
INF=float('inf')
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[INF]*(sum(l[i][1] for i in range(n))+1)
dp[0]=0
for i in range(n):
    for j in range(len(dp)-1,l[i][1]-1,-1):
        dp[j]=min(dp[j],dp[j-l[i][1]]+l[i][0])
for i in range(len(dp)-1,-1,-1):
    if dp[i]<=w:
        print(i)
        break

Solution (Python):
max_v = 100001
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[float('inf') for _ in range(max_v+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(max_v):
    if j - wv[i][1] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
    else:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

print(ans)

Solution (Python):
import sys

inf = sys.maxsize
N, W = map(int, input().split())
wvs = []
v_len = 0
for _ in range(N):
    wvs.append(list(map(int, input().split())))
    v_len += wvs[-1][1]


def chmin(x, v1, v2, diff):
    if dp[x][v1] > dp[x-1][v2]+diff:
        dp[x][v1] = dp[x-1][v2]+diff
        return True
    return False


dp = [[inf]*(v_len+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(v_len+1):
        if sum_v-wvs[i][1] >= 0:
            
            chmin(i+1, sum_v, sum_v-wvs[i][1], wvs[i][0])
        chmin(i+1, sum_v, sum_v, 0)  
max_i = 0
for i in range(v_len+1):
    if dp[N][i] <= W and max_i < i:
        max_i = i
print(max_i)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    wv = []
    for _ in range(N):
        wv.append(LI())


    
    dp_table = [[None for _ in range(10**5+1)] for _ in range(N)]
    
    
    w0, v0 = wv[0]
    dp_table[0][0] = 0
    dp_table[0][v0] = w0

    
    for i, item in enumerate(wv):
        if i== 0: continue
        w,v = item
        for val, weight in enumerate(dp_table[i-1]):
            if weight is not None:
                
                dp_table[i][val] = min(dp_table[i][val], weight) if dp_table[i][val] is not None else weight
                
                dp_table[i][val+v] = weight + w

    v  = 10**5
    for w in reversed(dp_table[N-1]):
        if w and w <= W:
            print(v)
            break
        v -= 1


main()

Solution (Python):
from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = inpl()
dp = [[mod for i in range(sum(vv)+1)] for j in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum(vv)+1):
        if j >= vv[i]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-vv[i]]+ww[i])
        else:
            dp[i+1][j] = dp[i][j]
for i in range(sum(vv)+1)[::-1]:
    if dp[n][i] <= w:
        print(i)
        break

Solution (Python):
def main():

    N, W = map(int, input().split())
    goods = []
    tot_v = 0
    for _ in range(N):
        w, v = map(int, input().split())
        goods.append([w, v])
        tot_v += v
    dp = [[float('inf') for _ in range(tot_v+1)] for _ in range(N+1)]
    dp[0][0] = 0

    max_v = 0
    for i in range(N):
        w, v = goods[i]
        for j in range(tot_v+1):
            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]

            if dp[i+1][j] <= W:
                max_v = max(max_v, j)

    return max_v

if __name__ == '__main__':
    print(main())

Solution (Python):
import numpy as np
N,W = map(int,input().split())
l = []
for i in range(N):
  y,x =  map(int,input().split())
  l.append((x,y))
V = sum([x[0] for x in l])
dp = np.full((N+1,V+1), np.inf)
dp[0][0]=0
for i in range(N):
  v = l[i][0]
  w = l[i][1]
  dp[i+1]=dp[i]
  dp[i+1][v:] = np.minimum(dp[i][v:],dp[i][:V-v+1]+w)
i = V
while True:
    if dp[N][i] <= W:
      print(i)
      break
    i -= 1

Solution (Python):
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

sum_v = sum(v)
dp = [[10**15 for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    dp[i][0] = 0
    for j in range(sum_v+1):
        if j != 10**15:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
weights=[[float("inf")]*(10**5+1) for i in range(n+1)]
for i in range(n):
    weights[i+1][wv[i][1]]=min(weights[i+1][wv[i][1]], wv[i][0])
    for j in range(10**5+1):
        if weights[i][j]!=0:
            weights[i+1][j]=min(weights[i+1][j], weights[i][j])
            if weights[i][j]+wv[i][0]<=w:
                weights[i+1][j+wv[i][1]]=min(weights[i+1][j+wv[i][1]], weights[i][j]+wv[i][0])

for i in range(10**5+1):
    if weights[-1][10**5-i]!=float("inf"):
        print(10**5-i)
        quit()

Solution (Python):
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
V = max([wv[i][1] for i in range(N)]) * N

dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N) :
    for j in range(V+1) :
        if j >= wv[i][1] :
            dp[i+1][j] = min(dp[i][j-wv[i][1]] + wv[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]

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

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

def knapsack01(items, capW):
    dp = {0: 0}
    for wi, vi in sorted(items, key=lambda x: x[1]):
        for v, w in list(dp.items()):
            v2 = v + vi
            if w+wi <= capW:
                w2 = w + wi
                if v2 in dp:
                    if w2 < dp[v2]:
                        dp[v2] = w2
                else:
                    dp[v2] = w2
    return max(dp.keys())

print(knapsack01(items, capW))

Solution (Python):
INF = float('inf')

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

def knapsack01(items, capW, INF):
    sumV = sum([v for w, v in items])
    dp = [0] + [INF]*sumV
    accV = 0
    for wi, vi in sorted(items, key=lambda x: x[1]):
        accV += vi
        for v in reversed(range(vi, min(sumV, accV)+1)):
            w0 = dp[v-vi] + wi
            if w0 < dp[v]:
                dp[v] = w0
    for v in reversed(range(sumV+1)):
        if dp[v] <= capW:
            return v

print(knapsack01(items, capW, INF))

Solution (Python):
import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))

Solution (Python):



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

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






V = N*1000+1
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]


dp[0][0] = 0


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

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])



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

print(ans)

Solution (Python):
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

f = [float("inf") for i in xrange(100001)]
f[0] = 0

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    
    for x in range(100000-v, -1, -1):
        f[x+v] = min(f[x+v], f[x] + w)



a = max([i for i in xrange(100001) if f[i] <= s])
print a

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

vsum=sum([wv[k][1] for k in range(N)])


dp=[[sys.maxsize]*(vsum+2) for _ in range(N+1)]
for k in range(N):
    dp[k][0]=0


for i in range(N):
    for v in range(vsum+1):
        if dp[i][v]+wv[i][0]<=W:
            dp[i+1][v+wv[i][1]]=min(dp[i+1][v+wv[i][1]],dp[i][v]+wv[i][0])
        dp[i+1][v]=min(dp[i+1][v],dp[i][v])



for x in range(vsum,-1,-1):
    for y in range(N,-1,-1):
        if dp[y][x]<=W:
            print(x)
            break
    else:continue
    break

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

v_max = 10**3 * 10**2
memo = [float("inf") for _ in range(v_max+1)]
memo[0] = 0

for weight,value in wv_list:
    for v in range(v_max+1-value)[::-1]:

        memo[v+value] = min(memo[v]+weight, memo[v+value])

ans = 0

for i,m in enumerate(memo):
    if m <= W:
        ans = i

print(ans)

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



max_sum = sum([i[1] for i in A])

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

for i in range(N):
    for v in range(max_sum+1):
        if v>=A[i][1]:
            dp[i+1][v] = min([dp[i][v-A[i][1]]+A[i][0], dp[i][v]])

        else:
            dp[i+1][v] = dp[i][v]






for i,w in enumerate(dp[N][::-1]):
    if w <=W:
        print(max_sum-i)
        break

Solution (Python):
N,W = map(int,input().split())
wv = [[int(x) for x in input().split()] for i in range(N)]
MAX_V = 1000*100 + 1
dp = [[0 if j==0 else 10**12 for j in range(MAX_V+1)] for i in range(N+1)]
for i in range(N):
    for sum_v in range(MAX_V+1):
        if wv[i][1] + sum_v < MAX_V+1 and dp[i+1][wv[i][1]+sum_v] > dp[i][sum_v] + wv[i][0]:
            dp[i+1][wv[i][1]+sum_v] = dp[i][sum_v] + wv[i][0]
        if dp[i+1][sum_v] > dp[i][sum_v]:
            dp[i+1][sum_v] = dp[i][sum_v]
result=0
for i in range(MAX_V+1):
    if dp[N][i] < W+1:
        result = i
print(result)

Solution (Python):
def p_e():
    N, W = map(int, input().split())
    max_value = 10 ** 3 * N + 1
    dp = [W + 1] * max_value
    dp[0] = 0
    for _ in range(1, N + 1):
        w, v = map(int, input().split())
        NEXT = [W + 1] * max_value
        NEXT[0] = 0
        for i in range(1, max_value):
            if i - v >= 0:
                NEXT[i] = min(dp[i - v] + w, dp[i])
            else:
                NEXT[i] = dp[i]
        dp = NEXT

    ans = 0
    for i, w in enumerate(dp):
        if w <= W:
            ans = i
    print(ans)


if __name__ == '__main__':
    p_e()

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

wvlist = [list(map(int,input().split())) for _ in range(N)]
INF = 10**15
ans = INF



dp = np.full((N+1,N*1000+1),INF)
dp[0][0] = 0

for i in range(N):
    dp[i+1][:wvlist[i][1]] = dp[i][:wvlist[i][1]]
    dp[i+1][wvlist[i][1]:] = np.minimum(dp[i][wvlist[i][1]:],dp[i][:-wvlist[i][1]]+wvlist[i][0])
        
for i in range(N*1000+1):
    if W >= dp[N][i]:
        ans = i
        
print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num, lim_weight = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    dp = np.full(10 ** 5 + 1, np.inf)

    for i in range(num):
        weight, value = data[i]
        prev = dp.copy()
        dp[:value] = np.minimum(prev[:value], weight)
        dp[value:] = np.minimum(prev[value:], prev[:-value] + weight)

        
    ans = np.max(np.where(dp <= lim_weight)) + 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

def main():
	N, W = map(int, input().split())
	dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)
	dp[0] = 0
	for _ in range(N):
		w, v = map(int, input().split())
		np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
	print(((dp <= W) * np.arange(N * 1000 + 1)).max())

if __name__ == "__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N, W = map(int, input().split())
MV = N * 10**3 + 1
INF = float('inf')
dp = [[INF] * MV for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(MV):
        if v <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
        else:
            dp[i+1][j] = dp[i][j]
dp = dp[N]
for i in range(0, MV)[::-1]:
    if dp[i] <= W:
        print(i)
        break

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [float('inf')] * (10**5 + 1)
    dp[0] = 0

    for w, v in items:
        for value in range(10**5 + 1)[:: -1]:
            if value - v >= 0:
                dp[value] = min(dp[value], dp[value - v] + w)

    ans = 0
    for v in range(10**5 + 1)[:: -1]:
        if dp[v] <= W:
            ans = v
            break

    print(ans)


sol()

Solution (Python):
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = map(int, readline().split())
  maxv = 10 ** 3 * n + 1
  t = [-1] * maxv
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = map(int, readline().split())
    for i in range(cmaxv, -1, -1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i + nv] < ti - nw:
        t[i + nv] = ti - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()

Solution (Python):

n,W = list(map(int,input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1,n+1):
    w[i],v[i]=list(map(int,input().split()))
V = n*max(v)

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

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


print(max([j for j in range(V+1) if dp[n][j]<=W]))

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



dp = [0]+[float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1, -1):
        dp[j] = min( dp[j], dp[j-wv[i][1]]+wv[i][0] )
        

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

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

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

for i in range(1, N+1):
    for v in range(0, 100001):
        weight = WV[i-1][0]
        value = WV[i-1][1]
        dp[i][v] = min(dp[i-1][v], dp[i-1][v-value]+weight)
res = 0
for v, w in enumerate(dp[-1]):
    if w <= W: res = v

print(res)

Solution (Python):
def knapsack_rec(target, W, V): 
    P = {}
    P[0] = target
    max_ = 0

    for vi in range(len(V)):
        we, va = W[vi], V[vi]
        for i in range(max_, -1, -1):
            if i in P:
                piva = P.get(i + va, -1)
                if piva < P[i] - we:
                    P[i + va] = P[i] - we
                    if max_ < i + va:
                        max_ = i + va
    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Solution (Python):
import sys


n, c = list(map(int, input().split()))


M = (10 ** 3) * n + 10


if n == 1:
    w, v = map(int, input().split())
    ans = v if c >= w else 0
    print(ans)
    sys.exit()


dp = [[float("inf")] * M for i in range(n)]
dp[-1][0] = 0

for i in range(n):
    w, v = map(int, input().split())
    
    for j in reversed(range(M)):
        dp[i][j] = dp[i - 1][j]
        if j + v < M:
            dp[i][j + v] = min(dp[i - 1][j + v], dp[i - 1][j] + w)

ans = 0
for i in range(M):
    if dp[-1][i] <= c:
        ans = max(i, ans)

print(ans)

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

v_total = sum([x[1] for x in wv])
dp = [0] + [float("inf")]*v_total

for i in range(n):
    for j in range(v_total, wv[i][1]-1, -1):
        dp[j] = min(dp[j], dp[j-wv[i][1]]+wv[i][0])

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

Solution (Python):
N,W=map(int,input().split())
w=[0 for i in range(N+1)]
v=[0 for i in range(N+1)]
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())
N_max=max(v[i] for i in range(N+1))
INF=float('inf')
dp=[[INF for i in range(N*N_max+1)]for j in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  for j in range(N*N_max+1):
    if v[i]<=j:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    else:
      dp[i][j]=dp[i-1][j]
ans=0
for i in range(1,N*N_max+1):
  if dp[N][i]<=W:
    ans=i
print(ans)

Solution (Python):
import numpy as np

n, W = map(int, input().split())
w, v = [],[]
for i in range(n):
    temp = list(map(int, input().split()))
    w.append(temp[0])
    v.append(temp[1])

table = np.full(sum(v)+1, np.inf)
table[0] = 0

for i in range(n):
    l = table[:-v[i]]
    r = table[v[i]:]
    np.minimum(l + w[i], r, out = r)
    
print(np.max(np.where(table <= W)))

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    lim = 10 ** 5
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def heavy_knapsack(W: int, weight: "Array[int]", value: "Array[int]") -> int:
    lim = sum(value)
    dp = [0] + [float("inf")] * lim  
    for w, v in zip(weight, value):
        for cur_v in range(lim, v - 1, -1):
            dp[cur_v] = min(dp[cur_v], dp[cur_v - v] + w)
    ret = max(v for v, w in enumerate(dp) if w <= W)
    return ret


def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    w, v = zip(*A)
    ans = heavy_knapsack(W, w, v)
    print(ans)


if __name__ == "__main__":
    main()

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

dp = [[10**15 for sum_v in range(10**5+100)] for i in range(N+100)]

for i in range(N):
    for sum_v in range(10**5+50):

        dp[0][0] = 0

        
        if sum_v-items[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],
                                 dp[i][sum_v-items[i][1]]+items[i][0])

        
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

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

Solution (Python):
N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)
V = 10 ** 5 + 1

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

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

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

Solution (Python):
import numpy as np
N, W = map(int, input().split())
ndp = np.full(1000*100+1, 10**11, dtype=np.int64)
ndp[0] = 0

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

    np.minimum(ndp[:-v] + w, ndp[v:], out = ndp[v:])

print(np.max(np.where(ndp<=W)))

"""
https://atcoder.jp/contests/dp/submissions/6646897
から失敬

貪欲法はこの手の書き方で表現できるっぽい。
価値テープのなかで同価値のindexでは、より少ない重量の物品で済む方を残していく。
したがってテープの初期化は擬似infで行い、価値0の部分は重さも0で始める。

"""

Solution (Python):
n,W=map(int,raw_input().split())
w=[]
val=[]
for i in range(n):
    p=map(int,raw_input().split())
    w.append(p[0])
    val.append(p[1])
to = sum(val)    
dp = [float("inf")]*(to+1)
dp[0]=0
for i in range(n):
    for j in range(to,val[i]-1,-1):
        dp[j]=min(dp[j],dp[j-val[i]]+w[i])
for i in range(to,-1,-1):
    if(dp[i]<=W):
        print i
        exit()

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

import numpy as np

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


max_v = 0
INF = 10 ** 18
dp = np.full(1000 * N + 1, INF, dtype=np.int64)
dp[0] = 0
for _ in range(N):
    w,v = map(int,input().split())
    np.minimum(dp[v:max_v + v + 1], dp[:max_v + 1]+w, out = dp[v:max_v + v + 1])
    max_v += v

answer = np.where(dp <= W)[0].max()
print(answer)

Solution (Python):
N,W,*l = map(int,open(0).read().split())
wl = l[::2]
vl = l[1::2]
M = N*max(vl)
INF = float("inf")
dp = [[INF]*(M+1) for _ in range(N+1)]
dp[0][0] = 0


for i in range(N):
	w,v = wl[i],vl[i]
	for j in range(M+1):
		if j >= v:
			dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
		else:
			dp[i+1][j] = dp[i][j]
		

ans=0
for val,wei in enumerate(dp[-1]):
	if wei <= W:
		ans = max(ans,val)
print(ans)