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())
w_list = []
v_list = []
for _ in range(N):
    w,v = map(int,input().split())
    w_list.append(w)
    v_list.append(v)
dp = [[10**12]*(10**5+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w = w_list[i-1]
    v = v_list[i-1]
    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]
maxer = 0
for j in range(10**5+1):
    if dp[i][j] <= W:
        maxer = j
print(maxer)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
INF=10**9+1
def main():
    n, W = map(int, input().split())
    dp = np.full(n*1000+1,INF,dtype=int)
    dp[0]=0
    for i in range(1,n+1):
        w,v=map(int,input().split())
        dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
    for i in range(len(dp)-1, -1, -1):
        if dp[i] <= W:
            print(i)
            break

if __name__ == '__main__':
    main()

Solution (Python):

import sys
inf = sys.maxsize

n,mw = map(int,input().split())

mv = 1000 * n

dp = [[inf for _ in range(mv+ 1)] for _ in range(n + 1)] 

dp[0][0] = 0

for i in range(n):
    w, v = map(int,input().split())
    for sv in range(mv + 1):
        if sv - v >= 0:
            dp[i + 1][sv] = min(dp[i][sv], dp[i][sv - v] + w)
        else:
            dp[i + 1][sv] = dp[i][sv]

ans = 0
for sv in range(mv + 1):
    if dp[n][sv] <= mw:
        ans = sv

print(ans)

Solution (Python):
N,W=map(int,input().split())
w_list=[0]*N
v_list=[0]*N
for i in range(N):
    w_list[i],v_list[i]=map(int,input().split())
    
V=N*1000
inf=float("inf")
dp=[[inf]*(V+1) for _ in range(N+1)]
dp[0][0]=0

for v in range(V+1):
    for n in range(N):
        if v>=v_list[n]:
            dp[n+1][v] = min(dp[n][v-v_list[n]]+w_list[n],dp[n][v])
        else:
            dp[n+1][v]=dp[n][v]

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

Solution (Python):
n, W = map(int, input().split())
w = []
v = []
V = 0
for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    w.append(tmp1)
    v.append(tmp2)
    V += tmp2

dp = [[float('inf') for _ in range(V+1)] for _ 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] = dp[i][j]

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


print(ans)

Solution (Python):
import sys
from collections import namedtuple


INF = sys.maxsize
Item = namedtuple('Item', 'w v')

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

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))
  
max_value = 10 ** 3 * 100  

memo = [0] + [INF] * max_value

for item in items:
  for v in range(max_value, item.v - 1, -1):
    memo[v] = min(memo[v], memo[v - item.v] + item.w)
  
print(max([v for v, w in enumerate(memo) if w <= W]))

Solution (Python):

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

V = 1000 * N


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

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

print(ans)

Solution (Python):
N,W=map(int,input().split())
w,v=[0]*N,[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[float('inf')]*(sum(v)+1) for i in range(N+1)]

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

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

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

v = sum(list(map(lambda x: x[1], wv)))
dp = [[float("inf")]*(v+1) for _ in range(n+1)]
dp[0][0] = 0

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

dpl = dp[-1]
for i in range(v, -1, -1):
    if dpl[i] <= w:
        print(i)
        break

Solution (Python):
import sys
from collections import namedtuple

INF = sys.maxsize

Item = namedtuple('Item', 'w v')

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

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))
  
memo = [0] + [INF] * 100000
  
for item in items:
  for v in range(100000, item.v - 1, -1):
    memo[v] = min(memo[v], memo[v - item.v] + item.w)

print(max([v for v, w in enumerate(memo) if w <= W]))

Solution (Python):



import numpy

def main():
  n, w = map(int, input().strip().split())
  Ws, Vs = numpy.array([[int(x) for x in input().strip().split()] for _ in range(n)]).T
  v_max = 10**5
  dp = numpy.full((n, v_max+1), 10**9+1, dtype=numpy.int)
  dp[0, 1:Vs[0]+1] = Ws[0]
  dp[:, 0] = 0
  for i in range(1, n):
    dp[i, :Vs[i]+1] = numpy.minimum(dp[i-1, :Vs[i]+1], Ws[i])
    if v_max - Vs[i] + 1 > 0:
      dp[i, Vs[i]:v_max+1] = numpy.minimum(dp[i-1, Vs[i]:v_max+1], dp[i-1,:v_max-Vs[i]+1]+Ws[i])
  print(numpy.max(numpy.where(dp[n-1] <= w)))


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)
inf=float("inf")
dp = [[inf for i in range(V)] for j in range(N)]

for i in range(N):
    for j in range(v[i]):
        dp[i][j] = w[i]

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

cnt = 0
for i in dp[-1]:
    if i <= W:
        cnt += 1
print(cnt)

Solution (Python):
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

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

N, W = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]
INF = 10**10
dp = [[INF]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = B[i]
    for j in range(10**5+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]
for i in range(10**5, -1, -1):
    if dp[N][i] <= W:
        print(i)
        break

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

val_max = 0
for i in range(N):
  val_max += value[i]
dp = [float('inf') for i in range(val_max+1)] 

dp[0] = 0
for i in range(N):
  for v in range(val_max-value[i], -1, -1): 
    dp[v + value[i]] = min(dp[v + value[i]], dp[v] + weight[i])
    
sol = 0
for i in range(val_max+1):
  if dp[i] <= W:
    sol = i
print("%s" % sol)

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])
V = 10 ** 5
inf = float("inf")

dp = [[inf] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
ans = -1

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

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

    maxw = 10 ** 11  
    maxv = 10 ** 5

    n, w = map(int, readline().split())

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

    for i in range(1, n + 1):  
        wi, vi = map(int, readline().split())
        for j in range(vi):
            dp[i][j] = dp[i - 1][j]
        for j in range(vi, maxv + 1):
            dp[i][j] = min(
                dp[i - 1][j],
                dp[i - 1][j - vi] + wi
            )

    ret = next(j for j in reversed(range(maxv + 1)) if dp[n][j] <= w)

    print(ret)


if __name__ == '__main__':
    main()

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

    n,m = map(int,input().split())
    dp = [[float("inf")]*(10**5+1) 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(10**5+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]
    ans = 0

    for i in range(10**5+1):
        if dp[n][i] <= m:
            
            ans = i
    print(ans)
if __name__ == "__main__":
    main()

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):
    weight,value = map(int,input().split())
    for j in range(10**5+1):
        if j < value:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-value]+weight)


ans = 0

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

Solution (Python):


n,w=map(int,input().split())
v=n*10**3
dp=[[100000000000] * (v+1) for i in range(n+1)]

dp[0][0]=0

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



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


result=0
for i in range(v+1):
    if dp[n][i]<=w:
        result=i

print(result)

Solution (Python):
N, W = list(map(int, input().split()))
WE = []
V = []
INF = float('inf')
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

MAX_V = (10 ** 3) * 100 + 1


DP = []
for i in range(N+1):
    a = [INF] * (MAX_V + 1)
    DP.append(a)

DP[0][0] = 0

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

r = 0
for i in range(MAX_V+1):
    if DP[N][i] <= W:
        r = i

print(r)

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

dp = np.zeros(10 ** 5 + 1) + 10 ** 10
dp[0] = 0

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

dp_meet_index = [i for i, v in enumerate(dp) if v <= Limit]

print(dp_meet_index[-1])

Solution (Python):
import bisect
N, W = map(int, input().split())
min_w = []
for i in range(N):
  w, v = map(int, input().split())
  l = [w] * v + [i + w for i in min_w]
  min_w = [min(min_w[i], l[i]) for i in range(len(min_w))] + l[len(min_w):]

print(bisect.bisect_right(min_w, W))

Solution (Python):
import bisect
N, W = map(int, input().split())
min_w = []
for i in range(N):
  w, v = map(int, input().split())
  l = [w] * v + [i + w for i in min_w]
  min_w = [min(min_w[i], l[i]) for i in range(len(min_w))] + l[len(min_w):]

print(bisect.bisect_right(min_w, W))

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







import bisect

def main():
	N,W=map(int,input().split())
	
	li=[list(map(int,input().split())) for _ in range(N)]
	V=sum(v for w,v in li)
	
	dp=[[10**15]*(V+2) for _ in [0]*(N+1)]
	
	for i in range(N):
		w = li[i][0]
		v = li[i][1]
		dp[i + 1][v] = min(dp[i + 1][v], w)
		for j in range(V+1)[::-1]:
			if j-v>=0:
				dp[i+1][j]=min(dp[i+1][j],dp[i+1][j+1],dp[i][j],dp[i][j-v]+w)
			else:
				dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j + 1], dp[i][j])


	
	print(bisect.bisect_right(dp[-1],W)-1)
	
	
	
if __name__ == "__main__":
	main()

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

sv = sum(v)
dp = [[float("inf")]*(sv+1) for _ in range(n+1)]
dp[0][0] = 0

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

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

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

V = sum([v for _, v in data])
dp = [[float("inf")] * (V + 1) for i in range(n + 1)]
dp[0][0]= 0

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

print(max([i for i, x in enumerate(dp[-1]) if x != "inf" and x <= W]))

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

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, W = na()
vmax = 10**5
inf = 10**11
dp = [[inf] * (vmax+1) for _ in range(n)]

w, v = na()
for i in range(0, v+1):
    dp[0][i] = w
for i in range(1, n):
    w, v = na()
    for j in range(v+1):
        dp[i][j] = min(dp[i-1][j], w) 
    for j in range(v+1, vmax+1):
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w) 

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

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

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])


    dp = np.full(10**5 + 1, W+1)
    dp[0] = 0

    for i in range(N):
        w, v = item[i]
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

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

if __name__ == "__main__":
    main()

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

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])


    dp = np.full(10**5 + 1, W+1)
    dp[0] = 0

    for i in range(N):
        w, v = item[i]
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

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

if __name__ == "__main__":
    main()

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

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])


    dp = np.full(10**5 + 1, 10**12+1)
    dp[0] = 0

    for i in range(N):
        w, v = item[i]
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

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

if __name__ == "__main__":
    main()

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

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])


    dp = np.full((N+1, 10**5 + 1), 10**12+1)
    dp[0][0] = 0

    for i in range(N):
        dp[i+1] = dp[i]
        w, v = item[i]
        np.minimum(dp[i][v:], dp[i][:-v] + w, out=dp[i+1][v:])

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

if __name__ == "__main__":
    main()

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

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])


dp = np.full((N+1, 10**5 + 1), 10**12+1)
dp[0][0] = 0

for i in range(N):
    dp[i+1] = dp[i]
    w, v = item[i]
    np.minimum(dp[i][v:], dp[i][:-v] + w, out=dp[i+1][v:])

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

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

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

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

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

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

print(res)

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

INF = 10**9+1000
SUM_V = sum([A[1] for A in WV])
dp = [[INF]*(SUM_V+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N+1):
    dp[i][0] = 0

for n in range(0, N):
    for v in range(0, SUM_V+1):
        if v >= WV[n][1]:
            dp[n+1][v] = min(dp[n][v-WV[n][1]] + WV[n][0], dp[n][v])
        else:
            dp[n+1][v] = dp[n][v]

for n in range(0, N+1):
    for v in range(0, SUM_V+1):
        if dp[n][v] <= W:
            dp[n][v] = -1

print(max([max([i for i,v in enumerate(dd) if v == -1]) for dd in dp]))

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

sv = sum(v)
dp = [[float("inf")]*(sv+1) for _ in range(n+1)]
dp[0][0] = 0

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

ans = 0
for i, _dp in enumerate(dp[n]):
    if _dp <= W:
        ans = i

print(ans)

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

V = sum(v)

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


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

print(ans)

Solution (Python):
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n, w = map(int, input().split())
    WVs = [list(map(int, input().split())) for i in range(n)]
    Vs = [_[1] for _ in WVs]
    sum_v = sum(Vs)
    
    dp = [[10**11]*(sum_v+1) for i in range(n+1)]
    dp[0][0] = 0
    
    

    for i in range(n):
        for j in range(sum_v+1):
            vi = Vs[i]
            wi = WVs[i][0]
            

            if j-vi >= 0:
                dp[i+1][j] = min([dp[i][j-vi] + wi, dp[i][j]])
            else:
                dp[i+1][j] = dp[i][j]

    
    
    for k in reversed(range(sum_v+1)):
        
        if dp[n][k] <= w:
            
            print(k)
            exit()

if __name__ == '__main__':
    main()

Solution (Python):


n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
V = max(v)
vmax = 10**5+1



dp = [[inf for _ in range(vmax)] for _ in range(n+1)]

dp[0][0] = 0
for i in range(n):
    for sum_v in range(vmax):
        
        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])



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

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

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
weight=[items[i][0] for i in range(n)]
value=[items[i][1] for i in range(n)]
import numpy as np

limit=sum(value)
inf=10**9
dp=np.array([[0]+[inf]*limit for i in range(n+1)])

for i in range(n):
  w=weight[i]
  v=value[i]
  dp[i+1][:v]=dp[i][:v]
  dp[i+1][v:]=np.minimum(dp[i][v:],dp[i][:-v]+w)

ans=max([i for i in range(limit+1) if dp[n][i]<=W])
print(ans)

Solution (Python):
n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
weight=[items[i][0] for i in range(n)]
value=[items[i][1] for i in range(n)]

limit=sum(value)
inf=10**9
dp=[[0]+[inf]*limit for i in range(n+1)]

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

ans=max([i for i in range(limit+1) if dp[n][i]<=W])
print(ans)

Solution (Python):
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    INF = 10 ** 15
    MAX_V = 100 * 10**3 + 1
    dp = [INF] * MAX_V
    dp[0] = 0
    for w, v in WV:
        for i in range(MAX_V-1, v-1, -1):
            tmp_dp = dp[i-v] + w
            if dp[i] > tmp_dp:
                dp[i] = tmp_dp
    for v, w in enumerate(dp):
        if w <= W:
            ans = v
    return ans


if __name__ == "__main__":
    answer = solve()
    print(answer)

Solution (Python):
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    INF = 10 ** 15
    MAX_V = 100 * 10**3 + 10
    dp = [INF] * MAX_V
    dp[0] = 0
    for w, v in WV:
        for i in range(MAX_V-1, v-1, -1):
            tmp_dp = dp[i-v] + w
            if dp[i] > tmp_dp:
                dp[i] = tmp_dp
    for v, w in enumerate(dp):
        if w <= W:
            ans = v
    return ans


if __name__ == "__main__":
    answer = solve()
    print(answer)

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

dp=[float('inf')]*100001 

dp[0]=0

for i in range(N): 
    for j in range(100000,list1[i][1]-1,-1):
        dp[j]=min(dp[j],dp[j-list1[i][1]]+list1[i][0])

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

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    x,y=map(int,input().split())
    w+=[x]
    v+=[y]

V_sum=sum(v)+1
dp=[[float('inf')]*(V_sum) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for sum_v in range(V_sum):
        
        if sum_v-v[i-1]>=0:
            dp[i][sum_v]=min(dp[i][sum_v],dp[i-1][sum_v-v[i-1]]+w[i-1])

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

ans=0
for i in range(V_sum):
    if dp[-1][i]<=W and ans<i:
        ans=i
print(ans)

Solution (Python):
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = []
for _ in range(N + 1):
    dp_val = [float('inf') for _ in range(value_sum + 1)]
    dp.append(dp_val)
dp[0][0] = 0

for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0

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

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

Solution (Python):
import numpy as np

U = 10**5
n, W = map(int, input().split())
dp = np.full(U+1, float("inf"))
dp[0] = 0
for _ in range(n):
  w, v = map(int, input().split())
  np.minimum(dp[v:], dp[:-v]+w, out=dp[v:])
ans = np.where(dp <= W)[0][-1]
print(ans)

Solution (Python):
import numpy as np

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
Mv = 10 ** 5
Mw = 10 ** 11

table = np.full((N + 1, Mv + 1), Mw, dtype=np.int64)
table[0][0] = 0
for n in range(N):
    tmp = np.full(Mv + 1, Mw, dtype=np.int64)
    tmp[goods[n][1]:] = table[n][:Mv + 1 - goods[n][1]] + goods[n][0]
    table[n + 1] = np.minimum(table[n], tmp)

print(np.max(np.where(table[N] <= W, table[N], 0).nonzero()))

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

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

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

dp[0][0] = 0
temp = 0

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

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

Solution (Python):
INF = float('inf')
MAX_N = 110
MAX_V = 100100


N, W = map(int, input().split())
weight, value = [0]*N, [0]*N

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

dp = [[INF for _ in range(MAX_V)] for _ in range(MAX_N)]
dp[0][0] = 0


for i in range(N):
    for sum_v in range(MAX_V):
        
        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])


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

print(answer)

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

wv = [[int(x) for x in input().split()] for _ in range(N)]

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

for i in range(N):
    for sum_v in range(10**5+1):
        if sum_v - wv[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v - wv[i][1]] + wv[i][0],dp[i][sum_v])
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

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

Solution (Python):
from pprint import pprint
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
vs = [x[1] for x in s]
max_v = sum(vs)
INF = float("inf")
dp = [[INF]*(max_v+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    for sum_v in range(max_v+1):
        if vs[i-1] <= sum_v:
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v-vs[i-1]]+ws[i-1])
        else:
            dp[i][sum_v] = dp[i-1][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):
n, w_bag = map(int, input().split())
wv = [[int(x) for x in input().split()] for _ in range(n)]
v_sum = sum(x[1] for x in wv)
min_weight = [[0 for _ in range(n + 1)] for _ in range(v_sum + 1)] 

for v in range(1, v_sum + 1):
    min_weight[v][0] = w_bag + 1
    for i in range(1, n + 1):
        if v - wv[i - 1][1] >= 0:
            min_weight[v][i] = min(min_weight[v][i - 1],
                                   min_weight[v - wv[i - 1][1]][i - 1] + wv[i - 1][0])
        else:
            min_weight[v][i] = min_weight[v][i - 1]

endflag = False
for enum, m_w_v in enumerate(reversed(min_weight)):
    for m_w_v_i in m_w_v:
        if m_w_v_i <= w_bag:
            print(v_sum - enum)
            endflag = True
            break
    if endflag:
        break
if not endflag:
    print(0)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,W=map(int,input().split())
    w,v=[0]*N,[0]*N
    for i in range(N):
        w[i],v[i]=map(int,input().split())
    dp=[[INF]*(10**5+1) for _ in range(N+1)]
    dp[0][0]=0
    ans=0
    for i in range(N):
        for value in range(10**5+1):
            dp[i+1][value]=min(dp[i+1][value],dp[i][value])
            if value>=v[i]:
                dp[i+1][value]=min(dp[i+1][value],dp[i][value-v[i]]+w[i])
            if dp[i+1][value]<=W:
                ans=max(ans,value)
    print(ans)

if __name__ == '__main__':
    main()