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):
N,W = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

dp = [{0:0} for i in range(N+1)]
for i,(w,v) in enumerate(src):
    for v0,w0 in dp[i].items():
        if v0 in dp[i+1]:
            dp[i+1][v0] = min(dp[i+1][v0], w0)
        else:
            dp[i+1][v0] = w0
        if w0+w > W: continue
        if v0+v in dp[i+1]:
            dp[i+1][v0+v] = min(dp[i+1][v0+v], w0+w)
        else:
            dp[i+1][v0+v] = w0+w
print(max(dp[-1].keys()))

Solution (Python):

n, w = map(int, raw_input().split())
oo = w + 1
items = []
v = 0
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))
    v += vi

dp = [[oo] * (v + 1) for _ in range(n + 1)]
for i in xrange(n + 1):
    dp[i][0] = 0
for i in xrange(1, n + 1):
    wi, vi = items[i - 1]

    for j in range(1, vi):
        dp[i][j] = dp[i - 1][j]

    for j in range(vi, v + 1):
        if j >= vi:
            dp[i][j] = min(dp[i - 1][j], wi + dp[i - 1][j - vi])
for i in xrange(v, -1, -1):
    if dp[n][i] <= w:
        print(i)
        break

Solution (Python):
from sys import stdin

INF = float('inf')

MAX = 100000
n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

dp = [[INF for i in xrange(MAX + 1)] for j in xrange(n)]

i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][vi] = wi
        dp[0][0] = 0
    else:
        for V in xrange(vi):
            dp[i][V] = dp[i - 1][V]
        
        dp[i][vi] = wi
        
        for V in xrange(vi, MAX + 1):
            dp[i][V] = min(dp[i][V], dp[i - 1][V], dp[i - 1][V - vi] + wi)

    i += 1

ans = 0
for v in xrange(MAX + 1):
    if dp[n - 1][v] <= W: ans = max(ans, v)

print ans

Solution (Python):
import numpy as np

N, W = map(int, input().split())
dp = np.full(N*1000+1,W+1,dtype=np.int)
dp[0] = 0

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

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

Solution (Python):
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+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] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Solution (Python):
from sys import stdin
N, W = map(int, input().split())
s = list(list(map(int, line.split())) for line in stdin.read().splitlines())

sumv = sum(s[i][1] for i in range(N))

INF = 10e12
dp = [INF] * (sumv + 1)  
dp[0] = 0

for n in range(N):
    w0, v0 = s[n]
    for v in range(sumv, v0 - 1, -1):
        dp[v] = min(dp[v], dp[v - v0] + w0)

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

Solution (Python):
from sys import stdin
N, W = map(int, input().split())
s = list(list(map(int, line.split())) for line in stdin.read().splitlines())

sumv = sum(s[i][1] for i in range(N))

INF = 10e12
dp = [INF] * (sumv + 1)  
dp[sumv] = sum(s[i][0] for i in range(N))
dp[0] = 0

for n in range(N):
    w0, v0 = s[n]
    for v in range(sumv, v0 - 1, -1):
        dp[v] = min(dp[v], dp[v - v0] + w0)

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

Solution (Python):
from sys import stdin
N, W = map(int, input().split())
s = list(list(map(int, line.split())) for line in stdin.read().splitlines())

sumv = sum(s[i][1] for i in range(N))

INF = float('inf')
dp = [INF] * (sumv + 1)  
dp[sumv] = sum(s[i][0] for i in range(N))
dp[0] = 0

for n in range(N):
    w0, v0 = s[n]
    for v in range(sumv, v0 - 1, -1):
        dp[v] = min(dp[v], dp[v - v0] + w0)

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

Solution (Python):
n,k=(int(i) for i in input().split())
e = [[int(i) for i in input().split()] for j in range(n)]

maxv=0
for i in range(n):
    maxv+=e[i][1]


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


for i in range(1, maxv+1):
    dp[0][i] = float('inf')


for j in range(n):
    for i in range(1, maxv+1):
        if i < e[j][1] :
            dp[j + 1][i] = dp[j][i]
        else:
            dp[j + 1][i] = min(dp[j][i], dp[j][i - e[j][1]] +e[j][0])

ans = 0
for i in range(maxv+1):
    if dp[n][i] <= k and ans < i:
        ans = i
        
print(ans)

Solution (Python):
N, W = map(int, input().split())
a = []
for i in range(N):
    x,y = map(int,input().split())
    a.append([x,y])
max_v, inf = 10**5, float("inf")
dp = [0] + [inf]*max_v
 
for w, v in a:
    for i, j in zip(range(max_v-v, -1, -1), range(max_v, -1, -1)):
        if dp[i]+w <= W and dp[j] > dp[i]+w:
            dp[j] = dp[i]+w
 
for weight, value in zip(dp[::-1], range(max_v, -1, -1)):
    if weight != inf:
        print(value)
        break

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, W = map(int, raw_input().split())
DP = [0] + [INF] * 100000
for _ in range(N):
    w, v = map(int, raw_input().split())
    for i in range(v, 100001)[::-1]:
        DP[i] = min(DP[i], DP[i - v] + w)

for i in range(100001)[::-1]:
    if DP[i] <= W:
        print i
        break

Solution (Python):
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))
upper = 10**5
dp = [float("inf") for i in range(upper+1)] 
dp[0] = 0

for item in range(N) :
    weight_i,value_i = L[item]
    for value in range(upper, value_i-1, -1) :
        if dp[value - value_i] + weight_i <= W :
            dp[value] = min(dp[value], dp[value - value_i] + weight_i)

for value in range(upper, -1, -1) :
    if dp[value] < float("inf") :
        ans = value
        break

print(ans)

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

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

for item in range(N) :
    weight_i,value_i = L[item]
    for value in range(upper, value_i-1, -1) :
        if dp[value - value_i] + weight_i <= W :
            dp[value] = min(dp[value], dp[value - value_i] + weight_i)

for value in range(upper, -1, -1) :
    if dp[value] < float("inf") :
        ans = value
        break

print(ans)

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

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

for i in range(N) :
    weight,value = map(int,input().split())
    for j in range(max_size, value-1, -1) :
        if dp[j - value] + weight <= W :
            dp[j] = min(dp[j], dp[j-value] + weight)

for i in range(max_size, -1, -1) :
    if dp[i] < float("inf") :
        ans = i
        break

print(ans)

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

n,k = IN()
dp = np.full(n*1000+1, k+1, dtype=int)
dp[0] = 0

for _ in range(n):
  w,v = IN()
  dp[v:] = np.minimum(dp[:-v]+w, dp[v:])

print(np.max(np.where(dp <= k)))

Solution (Python):


import sys
import numpy as np
N,W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))

dp = np.full(N*1000 + 1 , W+1, dtype=np.int64)

dp[0] = 0
for w,v in zip(it, it):
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])



print( ((dp<=W) * np.arange(N*1000 + 1)).max() )

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)
V = max(v)

dp = [[float("inf")]*(N*V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
	for sum_v in range(N*V+1):
		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(N*V+1):
	if dp[N][sum_v] <= W:
		ans = sum_v
print(ans)

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, W = MAP()
wN, vN = [0]*N, [0]*N
for i in range(N):
    wN[i], vN[i] = MAP()


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

for i in range(N):
    for j in range(V+1):
        
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j + vN[i] <= V:
            
            dp[i+1][j+vN[i]] = min(dp[i+1][j+vN[i]], dp[i][j] + wN[i])
ans = 0
for i in range(V+1):
    if dp[N][i] <= W:
        ans = max(ans, i)
print(ans)

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

V = {}
V[0] = 0
for i in range(N):
  w, v = map(int, input().strip().split())
  keys = sorted(list(V.keys()), reverse=True)
  for vk in keys:
    if (vk + v) in V:
      V[vk + v] = min(V[vk + v], V[vk] + w)
    else:
      V[vk + v] = V[vk] + w

v_max = 0
for vk in V.keys():
  if ((V[vk] <= W) and (vk > v_max)):
    v_max = vk

print(v_max)

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

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

sumV = 10**5
dp = [INF] * (sumV+1)
dp[0] = 0
for wi, vi in items:
    for v in reversed(range(sumV+1)):
        if dp[v] == INF: continue
        dp[v+vi] = min(dp[v+vi], dp[v] + wi)

print(max([v for v in range(sumV+1) if dp[v] <= capW]))

Solution (Python):
from sys import stdin, stdout

INF = float('inf')
n, C = map(int, stdin.readline().split())
W = 10 ** 5

dp = [[INF for i in range(W + 1)] for j in range(2)]
dp[0][0] = 0
cur = 0

for i in range(n):
    w, c = map(int, stdin.readline().split())
    w, c = c, w
    
    for j in range(W + 1):
        dp[cur ^ 1][j] = min(dp[cur ^ 1][j], dp[cur][j])
        
        if j + w <= W:
            dp[cur ^ 1][j + w] = min(dp[cur ^ 1][j + w], dp[cur][j] + c)
        
        dp[cur][j] = INF
    
    cur ^= 1

ans = 0
for i in range(W + 1):
    if dp[cur][i] <= C:
        ans = i
        
stdout.write(str(ans))

Solution (Python):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                if nw < dp[nv]:
                    dp[nv] = nw
            else:
                dp[nv] = nw


print(max(dp.keys()))

Solution (Python):
def main():
  N, W = list(map(int, input().split()))
  Data = []
  su = 0
  for i in range(N):
    t = list(map(int, input().split()))
    su += t[1]
    Data.append(t)
  
  DP = [int(10e12) if i != Data[0][1] else Data[0][0] for i in range(su + 1)]
  DP[0] = 0
  
  for i in range(1, N):
    for j in range(su - Data[i][1], -1, -1):
      k = j + Data[i][1]
      DP[k] = min(DP[j] + Data[i][0], DP[k])
      
  for i in range(su, -1, -1):
    if DP[i] <= W:
      print(i)
      break
  
main()

Solution (Python):
import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)

for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
vmax = sum(v)
    
dp = [[10**9+7]*(vmax+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=0

for i, j in itr.product(range(1, n+1), range(1, vmax+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]

ans = [j for j in range(vmax+1) if dp[n][j] <= wmax]       
print(ans[-1])

Solution (Python):
import numpy as np
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,wmax=IL()
dp=np.full(n*pow(10,3)+1,wmax+1,dtype=int)
dp[0]=0
for i in range(n):
    w,v=IL()
    dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
for i in range(n*pow(10,3)+1):
    if dp[i]<=wmax:
        ans=i
print(ans)

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

Solution (Python):
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    vals = list(map(int, input().split()))
    w.append(vals[0])
    v.append(vals[1])
sum_v = sum(v)
inf = 10**10
dp = [inf] * (sum_v + 1)
dp[0] = 0
for i in range(n):
    for j in reversed(range(sum_v - v[i] + 1)):
        if dp[j] == inf:
            continue
        dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])
for i in reversed(range(sum_v + 1)):
    if dp[i] > W:
        continue
    print(i)
    break

Solution (Python):
import numpy as np
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
INF = 10**13

def maxvalue_dp(ws, vs, W):
    V = sum(vs)
    dp = np.zeros(V + 1, np.int64)
    dp += INF
    dp[0] = 0
    for w, v in zip(ws, vs):
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
    for v in range(V, -1, -1):
        if dp[v] <= W:
            return v

print(maxvalue_dp(ws, vs, W))

Solution (Python):
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        dp[k + v] = min(dp_o.get(k + v, float('inf')), dp_o[k] + w)
print(max([k for k, v in dp.items() if v <= W]))

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

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

V = sum(v for w,v in items)

dp = [float('inf')]*(V+1)
dp[0] = 0
for w,v in items:
  for j in reversed(range(V-v+1)):
    dp[j+v] = min(dp[j+v], dp[j]+w)

print(max(v for v,w in enumerate(dp) if w <= W))

Solution (Python):
INF = 10 ** 12
MV = 10 ** 5

N, W = map(int, input().split())
dp = [[INF for _ in range(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(MV + 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]

ans = -1
j = MV
while j >= 0:
    if dp[N][j] <= W:
        ans = j
        break
    j -= 1
print(ans)

Solution (Python):


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.ones(N*1000+1, dtype=int) *(W+1)
DP[0] = 0

for i in range(N):
    DP[v[i]:] = np.minimum(DP[:-v[i]]+ w[i], DP[v[i]:])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        ans = k
        
print(ans)

Solution (Python):


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

DP = [float("inf")] * (N*1000+1)
DP[0] = 0

for i in range(N):
    for j in range(N*1000,-1,-1):
        DP[j] = min(DP[j- v[i]] + w[i], DP[j])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        
        ans = k
print(ans)

Solution (Python):
N,W = map(int,input().split())
c = [tuple(map(int,input().split())) for i in range(N)]
DP = [[float('inf') for i in range(10**3*N+1)] for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    for v in range(10**3*N+1):
        if v-c[i][1] < 0:
            DP[i+1][v] = DP[i][v]
        else:
            DP[i+1][v] = min(DP[i][v-c[i][1]]+c[i][0],DP[i][v])

ans = 0
DP = DP[N]
for v in range(10**3*N,-1,-1):
    if DP[v] <= W:
        ans = v
        break
print(ans)

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

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


for w,v in A:
	for i in range(V,-1,-1):
		if dp[i] is not None:
			if  0<=i+v<=V:
				if dp[i+v] is None:
					dp[i+v]=dp[i]+w
				else:
					dp[i+v]=min( dp[i+v], dp[i]+w )


for i in range(V,-1,-1):
	if dp[i] is not None:
		if dp[i]<=W:
			print i
			quit()

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

print(ma)

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: 0}
for i in range(N):
    for cv, cw in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cv + v[i]] = min(
            dp.get(cv + v[i], float('inf')),
            cw + w[i])
print(max(dp))

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

dp = [10**9+1] * (V + 1)
dp[0] = 0
for i in range(N):
    for j in range(V, -1, -1):
        dp[j] = min(dp[j], dp[j-L[i][1]] + L[i][0])
ans = 0
for j in range(V+1):
    if  W >= dp[j]:
        ans = max(ans, j)
print(ans)

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

dp = [[10**9+1] * (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 - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)

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

dp = [[float('inf')] * (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 - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)

Solution (Python):
n,w=map(int, input().split())
m=10**5+1
x=[list(map(int, input().split())) for i in range(n)]
dp=[[float('inf')]*m for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(m):
        if j>=x[i][1]:
            dp[i+1][j]=min(dp[i][j],dp[i][j-x[i][1]]+x[i][0])
        else:
            dp[i+1][j]=dp[i][j]
ans=0
for i in range(m):
    if dp[-1][i]<=w:ans=max(ans,i)
print(ans)

Solution (Python):
N,W = map(int,input().split())
value,weight = [],[]
def chmin(a,b):
    if (a > b):
        a = b
        return True
    return False
for i in range(N):
    w,v = map(int,input().split())
    value.append(v)
    weight.append(w)

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

Solution (Python):
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.full(N * 1000 + 1, W + 1, dtype=np.int64)
dp[0] = 0
for w, v in zip(it, it):
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(((dp <= W) * np.arange(N * 1000 + 1)).max())

Solution (Python):
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)
dp[0] = 0
for w, v in zip(it, it):
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(((dp <= W) * np.arange(N * 1000 + 1)).max())

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = sorted([LI() for _ in range(n)])
    u = sum(map(lambda x: x[1], aa))
    r = [inf] * (u+1)
    r[0] = 0
    mx = 0
    for a,b in aa:
        mx += b
        for i in range(min(mx, u-b),-1,-1):
            if r[i+b] > a + r[i]:
                r[i+b] = a + r[i]

    for i in range(u,0,-1):
        if r[i] <= w:
            return i

    return 0


print(main())

Solution (Python):
t = int(1e5)
n, m = map(int, input().split())
ans = 0
dp = [m + 1 for _ in range(t + 1)]
dp[0] = 0
for _ in range(n):
    w, v = map(int, input().split())
    for i in range(t, v - 1, -1):
        if dp[i - v] + w <= m:
            dp[i] = min(dp[i], dp[i - v] + w)
            ans = max(ans, i)
print(ans)

Solution (Python):
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
vm=n*1000+1
dp=[[0]+[10**18]*vm]+[[0]*vm for _ in range(n)]
for i in range(1,n+1):
    w,v=g[i]
    for j in range(vm):
        k=j-v
        if k<0:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][k]+w)
for j in range(vm)[::-1]:
    if dp[n][j]<=W:
        print(j)
        break

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

v_sum = sum(v) + 1
inf = float('inf')
dp = [inf] * v_sum
dp[0] = 0

for i in range(N):
    for j in reversed(range(v_sum)):
        if j + v[i] < v_sum and dp[j] != inf:
            dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])

for i in reversed(range(v_sum)):
    if dp[i] <= W:
        print(i)
        break

Solution (Python):
import sys
raw_input = sys.stdin.readline
N,W = map(int,raw_input().split())
arr = []
tot = 0
for i in range(N):
    arr.append(map(int,raw_input().split()))
    tot += arr[i][1]
dp = [100000000000 for x in range(tot+1)]
dp[0] = 0
for i in range(N):
    a,b = arr[i]
    for j in range(tot,b-1,-1):
        dp[j] = min(dp[j],dp[j-b]+a)
for i in range(tot,-1,-1):
    if dp[i]<=W:
        print i
        break

Solution (Python):


import sys

INF = float('inf')
MOD = 10 ** 9 + 7

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


N, W = LI()
L = [LI() for _ in range(N)]
V = 0
for i in range(N): V += L[i][1]


dp = [INF] * (V + 1)
dp[0] = 0
for weight, value in L:
    for v in range(V + 1)[::-1]:
        if v - value < 0:
            continue
        dp[v] = min(dp[v], dp[v - value] + weight)

for i in range(V + 1)[::-1]:
    if dp[i] <= W:
        print(i)
        exit()

Solution (Python):


import sys

INF = float('inf')
MOD = 10 ** 9 + 7

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


N, W = LI()
L = [LI() for _ in range(N)]
V = 0
for i in range(N): V += L[i][1]


dp = [INF] * (V + 1)
dp[0] = 0
for weight, value in L:
    for v in range(V + 1)[::-1]:
        if v - value < 0:
            continue
        dp[v] = min(dp[v], dp[v - value] + weight)

for i in range(V + 1)[::-1]:
    if dp[i] != INF and dp[i] <= W:
        print(i)
        exit()

Solution (Python):
def main():
    N, W = map(int, input().split())
    VMAX = int(1e5)+1
    dp = [[float("inf")] * (VMAX) for _ in range(2)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(VMAX):
            dp[(i+1) % 2][j] = min(dp[i % 2][j], dp[i % 2][max(j-v, 0)]+w)
    left = 0
    right = VMAX
    while left < right:
        center = (left + right) // 2
        if dp[N % 2][center] <= W:
            left = center + 1
        else:
            right = center
    print(left-1)


if __name__ == "__main__":
    main()

Solution (Python):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [inf for _ in range(sum_v+1)]

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

for v in range(sum_v, -1, -1):
    if dp[v] <= W:
        print(v)
        exit()

Solution (Python):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [[inf for _ in range(sum_v+1)] for _ in range(N+1)]


dp[0][0] = 0
for i in range(N):
    for j in range(sum_v+1):
        if j - items[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j - items[i][1]] + items[i][0])
        else:
            dp[i+1][j] = dp[i][j]
for v in range(sum_v, -1, -1):
    if dp[N][v] <= W:
        print(v)
        exit()

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

V = max(w_v, key=lambda x: x[1])[1] * N

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

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

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

Solution (Python):
import numpy as np

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

dp = np.full(N*1000+1, W+1, 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())

Solution (Python):
def e_knapsack2(N, W, Goods):
    """
    Dと同じ設定だが、制約が違う(1 <= v_i <= 10^3 と価値の制約がゆるめ)
    """
    from collections import defaultdict

    
    dp = defaultdict(lambda: float('inf'))
    dp[0] = 0
    
    for w, v in Goods:
        for nv, nw in list(dp.items()):
            if nw + w <= W:
                dp[nv + v] = min(dp[nv + v], nw + w)
    
    
    return max(dp.keys())

N, W = [int(i) for i in input().split()]
Goods = [[int(i) for i in input().split()] for j in range(N)]
print(e_knapsack2(N, W, Goods))

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

dp=[[0,0] for i in range(100001)]

dp[0][0]=1

w=[]
v=[]

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

for i in range(N):
    for j in range(100001):
        if dp[100001-1-j][0]==1:
            dp[100001-1-j+v[i]][0]=1
            if dp[100001-1-j+v[i]][1]>0:
                dp[100001-1-j+v[i]][1]=min(dp[100001-1-j][1]+w[i],dp[100001-1-j+v[i]][1])
            else:
                dp[100001-1-j+v[i]][1]=dp[100001-1-j][1]+w[i]
ans=0
for i in range(100001):
    if dp[i][0]==1 and dp[i][1]<=W and i>ans:
        ans=i
print(ans)

Solution (Python):
N,W=[int(x) for x in raw_input().split()]
A=[]
maxval=0
for i in range(N):
    w,v=[int(x) for x in raw_input().split()]
    A.append([w,v])
    maxval+=v
B=[[ 1e10  for i in range(maxval+1)] for j in range(N)]
B[0][A[0][1]]=A[0][0]
for x in range(N):
    B[x][0]=0

for i in range(1,N):
    w,v=A[i]
    for j in range(1, maxval+1):
        if (j>=v and B[i-1][j-v]+w <=W):
            B[i][j]=min(B[i-1][j-v]+w, B[i-1][j])
        else:
            B[i][j]=B[i-1][j]
for j in range(maxval,-1,-1):
    if B[-1][j]!=1e10:
        print j
        break

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

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

inf = float("inf")
dp = [inf for _ in range(v_sum + 1)]

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

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

Solution (Python):

from sys import stdin
import numpy as np

s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


MAX_VALUE = 10**5
N, W = ds_in()


min_weights = np.ones(MAX_VALUE + 1) * float('inf')
min_weights[0] = 0

total_value = 0
for _ in range(N):
    wv = ds_in()  
    min_weights[wv[1]:] = np.minimum(min_weights[:-wv[1]] + wv[0],
                                     min_weights[wv[1]:])

for i in range(MAX_VALUE, 0, -1):
    if min_weights[i] <= W:
        print(i)
        exit()

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

NIL = int(1e18)
MAX = int(1e5)

dp = [NIL]*(MAX+1)
dp[0]= 0

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1)):
        if k + v <= MAX and dp[k] != NIL:
            dp[k+v] = min(dp[k+v], dp[k] + w)

ans = 0
for i in reversed(range(MAX+1)):
    if dp[i] <= W:
        ans = i
        break
print(ans)

Solution (Python):
n,w=map(int, input().split())
m=10**5+1
x=[list(map(int, input().split())) for i in range(n)]
dp=[[float('inf')]*m for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(m):
        if j>=x[i][1]:
            dp[i+1][j]=min(dp[i][j],dp[i][j-x[i][1]]+x[i][0])
        else:
            dp[i+1][j]=dp[i][j]
ans=0
for i in range(m):
    if dp[-1][i]<=w:ans=max(ans,i)
print(ans)