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 = []
v = []

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

V = sum(v)

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


dp[0][0] = 0

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

        else:
            dp[i][j] = dp[i-1][j]

resp = 0

for i in range(V + 1):
    if dp[-1][i] <= W:
        resp = max(i,resp)

print(resp)

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

INF = 10**10

dp = [[INF for i in range(100010)] for j in range(n+1) ]

dp[0][0] = 0

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

for j in range(100010):
    if dp[n][100009-j] <= W:
        print(100009-j)
        break

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

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

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

Solution (Python):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
lim = int(1e5) + 1
inf = float("inf")


dp = [[inf for _ in range(lim)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(lim):
        if wv[i][1] <= j:
            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(lim):
    if dp[N][i] <= W:
        ans = i
print(ans)

Solution (Python):
import sys
def main():
    INF=sys.maxsize
    Vmax=1000
    N,W=tuple(map(int,sys.stdin.readline().split()))
    V,w,v=N*Vmax,[0],[0]
    for _ in [0]*N:
        ww,vv=tuple(map(int,sys.stdin.readline().split()))
        w.append(ww)
        v.append(vv)
    dp=[[INF for _ in range(V+1)] for _ in range(N+1)]
    dp[0][0]=0
    for i in range(1,N+1):
        for j in range(V+1):
            dp[i][j]=min(dp[i][j],dp[i-1][j])
            if 0<=j-v[i]<=V:dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i])
    res=0
    for j in range(V+1):
        if dp[N][j]<=W:res=j
    print(res)
if __name__=='__main__':main()

Solution (Python):
import numpy as np

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 18
V_MAX = 10 ** 3 * N

dp = np.full(V_MAX + 1, INF)
dp[0] = 0

for w, v in wv:
    dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 18
V_MAX = 10 ** 3 * N

dp = np.full(V_MAX + 1, INF)
dp[0] = 0

for w, v in wv:
    dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

ans = 0
for i in range(V_MAX, -1, -1):
    if dp[i] <= W:
        ans = i
        break

print(ans)

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

INF = float('inf')
V = max(v)
dp = [[INF for i in range(V * n + 1)] for j in range(n + 1)]
dp[0][0] = 0

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

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

print(ans)

Solution (Python):

import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    
    
    

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

    dp = [defaultdict(int)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = sorted(list(dp[i].keys()))
        new_dp = defaultdict(int)
        for key in keys:
            new_dp[key] = max([new_dp[key], dp[i][key]])
            new_w = key + w
            if new_w <= W:
                new_dp[new_w] = max([new_dp[new_w], dp[i][key] + v])

        max_value = 0
        for key in sorted(new_dp.keys()):
            if max_value > new_dp[key]:
                del new_dp[key]
            else:
                max_value = new_dp[key]

        dp.append(new_dp)
    print(max(dp[N].values()))


if __name__ == '__main__':
    main()

Solution (Python):
N, W = (int(x) for x in input().split())
weights = []
values = []
for _ in range(N):
  w, v = (int(x) for x in input().split())
  weights.append(w)
  values.append(v)

sumValues = sum(values)
dp = [float('inf')] * (sumValues + 1) 
dp[0] = 0
for item in range(N):
  for value in range(sumValues-values[item], -1, -1):
    dp[value+values[item]] = min(dp[value+values[item]], dp[value]+weights[item])

res = 0
for i in range(sumValues+1):
  if dp[i] <= W:
    res = max(res, i)
print(res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def sub(w, v, b):
    """重みリストw, 価値リストv, 重さ上限bのナップサックを解く
    ※ 価値で回すパターン
    """
    sv = sum(v)
    n = len(w)
    dp = [float("inf")] * (sv+1) 
    dp[0] = 0
    for i in range(n):
        for j in range(sv, -1, -1):
            if j>=v[i]:
                dp[j] = min(dp[j], dp[j-v[i]]+w[i])
    return dp
n,w = map(int, input().split())
ws = [None]*n
vs = [None]*n
for i in range(n):
    ws[i], vs[i] = map(int, input().split())
dp = sub(ws, vs, w)
ans = 0
for i,item in enumerate(dp):
    if item<=w:
        ans = i
print(ans)

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

import numpy as np
import math

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

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

for i in range(N):
  w,v = map(int,readline().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())
wv = [list(map(int, input().split())) for _ in range(n)]

sum_v = sum([wv[i][1] for i in range(n)])


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

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

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

for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(10**5+10):
        if j >= item[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-item[i][1]]+item[i][0])
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for i in range(10**5+10):
    if dp[n][i] <= w:
        ans = i

print(ans)

Solution (Python):
import numpy as np

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 = np.full(10**5 + 1, W + 1, dtype=np.int64)
dp[0] = 0

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

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

Solution (Python):


LI = lambda: list(map(int, input().split()))


N, W = LI()
WV = [LI() for _ in range(N)]

INF = 10 ** 10
MAX = 10 ** 5


def main():
    dp = [[INF] * (MAX + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(1, N + 1):
        w, v = WV[i - 1]
        for j in range(MAX + 1):
            if j < v:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
    for i in range(MAX, -1, -1):
        if dp[-1][i] <= W:
            print(i)
            return


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

N, W = map(int, input().split())
dp = np.ones(int(1e5+1)) * np.inf
dp[0] = 0
total = 0
for i in range(N):
    w, v = map(int, input().split())
    dp[v:total+v+1] = np.minimum(dp[v:total+v+1], dp[:total+1] + w)
    total += v

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

Solution (Python):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 5
V = 10 ** 5 + 5
dp = [[INF] * V for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V):
        w = wv[i][0]
        v = wv[i][1]
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - v >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v] + w)

for i in range(V):
    if dp[N][i] <= W:
        MV = i    
print(MV)

Solution (Python):
import sys
import numpy as np

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

N, lim = map(int, readline().split())
WV = np.array(read().split(), np.int64)

W = WV[::2]
V = WV[1::2]


INF = 10**18
dp = np.full(V.sum() + 1, INF, np.int64)
dp[0] = 0
for w, v in zip(W, V):
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

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

Solution (Python):
import numpy as np
n, targw = map(int,input().split())
w = [0 for _ in range(n)]
v = [0 for _ in range(n)]
for i in range(n):
	w[i], v[i] = map(int,input().split())
"""
定義
dp[i] := v == i のときのwが最小なるもの.
"""
dp = np.full(100001, targw+1, dtype=np.int64)
dp[0] = 0
for i in range(n):
	dp[v[i]:] = np.minimum(dp[:-v[i]]+w[i], dp[v[i]:])
print(np.where(dp <= targw)[0][-1])

Solution (Python):
N,W=map(int,input().split())
w=[0]*(N+1)
v=[0]*(N+1)
for i in range(N):
    w[i],v[i] = map(int,input().split())
maxi=sum(v)
    
dp=[[float("inf") for _ in range(N+1)] for _ in range(maxi+1)]
for _ in range(N+1):
    dp[0][_]=0
    
last=0
for i in range(1,N+1):
    for j in range(1,maxi+1):
        if j<v[i-1]:
            dp[j][i]=min(w[i-1], dp[j][i-1])
        else:
            tmp=w[i-1]+dp[j-v[i-1]][i-1]
            if tmp<=W:
                dp[j][i]=min(tmp, dp[j][i-1])
            else:
                dp[j][i]=dp[j][i-1]


for j in range(maxi,-1,-1):
    if dp[j][-1]!=float("inf"):
        k=j
        break

ans=0
for i in range(N,0,-1):
    if dp[k][i]==dp[k-v[i-1]][i-1]+w[i-1]:
        k = k-v[i-1]
        ans += v[i-1]
print(ans)

Solution (Python):
inf=10**10
def knapsackBottomUp(wt,price,c,n,m):
    dp=[[inf for x in range(m+1)] for y in range(n+1)]
    for l in range(n+1):
        dp[l][0]=0


    for i in range(1,n+1):
        wi=wt[i];vi=price[i]
        for V in range(1,m+1):
            if vi <= V:
                dp[i][V]=min(wi+dp[i-1][V-vi],dp[i-1][V])
            else:
                dp[i][V]=dp[i-1][V]

    res=0
    for i in range(m+1):
        if dp[n][i]<=c:
            res=i
    print(res)
n,c=map(int,input().split())
wt=[]
price=[]
wt.append(0)
price.append(0)
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
max_val=sum(price)
knapsackBottomUp(wt,price,c,n,max_val)

Solution (Python):
n,w=[int(x) for x in input().split()]

lw=w
totval=0
wei=[]
val=[]
for test in range(n):
    cw, v = [int(x) for x in input().split()]
    wei.append(cw)
    val.append(v)
    totval+=v

dp=[float('inf')]*(totval+1)
dp[0]=0
for item in range(n):
    for j in range(totval,val[item]-1,-1):
        dp[j]=min(dp[j-val[item]]+wei[item],dp[j])
    
ans=0
for i in range(totval+1):
    if dp[i] <=w:
        ans=i
print(ans)

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

MAX_V = sum(x[1] for x in wv)

INF = 1 << 60
dp = [0] + [INF] * MAX_V

for w, v in wv:
    
    dp_tmp = dp[:]
    for j in range(1, MAX_V + 1):
        prev = max(0, j - v)
        dp_tmp[j] = min(dp[j], dp[prev] + w)
    dp = dp_tmp


print(bisect.bisect_right(dp, W) - 1)

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


Wl=[]
Vl=[]
for i in range(N):
  w,v=map(int,input().split())
  Wl.append(w)
  Vl.append(v)
V=max(Vl)
dp=[ [10**20]*((V+1)*(N+1)) for i in range(N+1) ]
dp[0][0]=0

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

ans=0
for i in range(len(dp[N])):
  if dp[N][i]<=W and i>ans:
    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)
Vi=[0] * N
for i in range(N):
    if i==0:
        Vi[i]=v[i]
    else:
        Vi[i]=Vi[i-1]+v[i]


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

for i in range(N):
    for j in range(Vi[i] + 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 j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

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][j], dp[i][j - v[i]] + w[i])
        else:
            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):
NW = list(map(int, input().split()))
wv = []
for i in range(NW[0]):
    wv.append(list(map(int, input().split())))

dp = [[float("inf")] * 10**3*(NW[0]+1) for i in range(NW[0]+1)]
dp[0][0] = 0
for i in range(len(dp)):
    for sum_v in range(len(dp[i])):
        try:
            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])
        except:
            continue

for sum_v in range(len(dp[i])):
    if dp[NW[0]][sum_v] <= NW[1]:
        res = sum_v

print(res)

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

from collections import defaultdict

dp = defaultdict(lambda: float('inf'))

dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for nv, nw in list(dp.items()):
        if nw + w <= W:
            dp[nv+v] = min(dp[nv+v], nw+w)

print(max(dp))

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

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

dp={}
dp_up={}
V_max=0

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

    V_max+=v

    for j in range(v,V_max+1):
        if j==v:
            if j in dp:
                dp_up[j]=min(dp[j],w)
                j_max=j
            else:
                dp_up[j]=w
                j_max=j
        else:
            if j-v in dp and dp[j-v]+w<=W:
                if j in dp:
                    dp_up[j]=min(dp[j],dp[j-v]+w)
                    j_max=j
                else:
                    dp_up[j]=dp[j-v]+w
                    j_max=j
    dp=dp_up.copy()
print(max(dp))

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

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

Solution (Python):










import numpy as np

def main():
    N, W = map(int, input().split())
    max_vi = 10**3
    max_V = N*max_vi
    dp = [W+1] * (max_V+1)
    dp[0] = 0
    dp = np.array(dp)
    for _ in range(N):
        w_, v_ = map(int, input().split())
        dp[v_:] = np.minimum(dp[v_:], dp[:-v_] + w_)

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

if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
MAX_V = 10**5+1
dp = [float('inf')] * MAX_V
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V)[::-1]:
        if sum_v >= v:
            dp[sum_v] = min(dp[sum_v - v] + w, dp[sum_v])
        else:
            dp[sum_v] = min(dp[sum_v], w)
ans = 0
for v in range(MAX_V)[:: -1]:
    if dp[v] <= W:
        ans = v
        break
print(ans)

Solution (Python):
n,w=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
dp=[[0 for i in range(sum(value)+1)] for j in range(n+1)]
for i in range(sum(value)+1):
    dp[0][i]=1000000000000
for j in range(n+1):
    dp[j][0]=0
for i in range(1,n+1):
    for j in range(1,sum(value)+1):
        if value[i-1]<=j:
            dp[i][j]=min(wt[i-1]+dp[i-1][j-value[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(sum(value),-1,-1):
    if dp[-1][i]<=w:
        print(i)
        break

Solution (Python):
import numpy as np

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

r = 10 ** 5 + 100
dp = np.array([[0]+[float("inf")]*(r-1)]*(N+1))
for i in range(1, N+1):
    w, v = map(int, input().split())
    dp[i,:v] = dp[i-1,:v]
    dp[i,v:r] = np.minimum(dp[i-1,v:r], dp[i-1,:r-v]+w)
    
print(max(np.where(dp[N]<=W)[0]))

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

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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
MAX_V = (10**3) * N + 1
INF = 1 << 60

dp = np.full(MAX_V, INF)
dp[0] = 0

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

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

Solution (Python):
n,w=map(int,input().split())
l=[[0,0]]
for _ in range(n):
    l.append(list(map(int,input().split())))
dp=[[10**10]*(n*(10**3)+1) for _ in range(n+1)]
for k in range(n+1):
    dp[k][0]=0
for i in range(1,n+1):
    for j in range(0,n*(10**3)+1):
        if j>=l[i][1]:
            dp[i][j]=min(dp[i-1][j-l[i][1]]+l[i][0],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(max([i for i,x in enumerate(dp[n]) if x<=w]))

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

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

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

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

for j in range(vmax, 0, -1):
    if dp[N][j] <= W:
        print(j)
        break

Solution (Python):
def b():
    def solve(N, W, V, wv):
        dp = [10**10] * (V+1)
        dp[0] = 0

        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]

            
            for v in range(V - vi, -1, -1):
                if dp[v] == -1:
                    continue
                if dp[v+vi] > dp[v] + wi:
                    dp[v+vi] = dp[v] + wi

        light = [i for i, w in enumerate(dp) if w <= W]
        return light[-1]

    N, W = map(int, input().split())
    wv = []
    V = 0

    for i in range(N):
        w, v = map(int, input().split())
        wv.append([w, v])
        V += v

    print(solve(N, W, V, wv))

if __name__ == "__main__":
    b()

Solution (Python):
N, W = map(int,input().strip().split(" "))
Vmax = 10**5
dp = [10**9+1] * (Vmax+1)
dp[0] = 0
Vtotal = 0

for _ in range(N):
    w, v = map(int, input().strip().split(" "))
    Vtotal += v
    for i in range(Vtotal-v, -1, -1):
        dp[i+v] = min(dp[i+v], dp[i]+w)

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

Solution (Python):
n, w = map(int, input().split())
lst = [[0,0]]
vmax = 0
for _ in range(n):
    a, b = map(int, input().split())
    lst.append([a,b])
    vmax += b

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

for i in range(0, n):
    for sum_v in range(0, vmax+1):
        if sum_v  >= lst[i+1][1]:
            dp[i+1][sum_v] = min(dp[i][sum_v -  lst[i+1][1]] + lst[i+1][0], dp[i][sum_v])
        else:
            dp[i+1][sum_v] = dp[i][sum_v]
        if dp[i+1][sum_v] <= w:
            ans = max(ans, sum_v)

print(ans)

Solution (Python):
INF = 10**18
n, w = map(int, input().split())

weights = [0]
values = [0]

for i in range(n):
    x, y = map(int, input().split())
    weights.append(x)
    values.append(y)

max_value = sum(values)
dp = [[INF for i in range(max_value+1)] for j in range(n+1)]

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

for i in range(n+1):
    for j in range(max_value + 1):

        if values[i] <= j:
            dp[i][j] = min(dp[i-1][j], weights[i] + dp[i-1][j - values[i] ] )
        else:
            dp[i][j] = dp[i-1][j]

ans = 0

for i in range(max_value + 1):
    if dp[n][i] <= w:
        ans = i

print(ans)

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

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

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

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

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

Solution (Python):
import sys

stdin = sys.stdin

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

n, W = na()
wv = [na() for _ 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):
import sys

stdin = sys.stdin

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

n, W = na()
wv = [na() for _ in range(n)]
dp = [0]+[float("inf")]*(10**5)
for i in range(n):
      for j in range(10**5,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())

MAX_V = 10**5
dp = [[10**(18)]*(MAX_V+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(MAX_V+1):
    dp[i][j] = dp[i-1][j]
    if j >= v:
      dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w)

ans = 0
for j in range(MAX_V+1):
  if dp[N][j] <= W and dp[N][j] != 10**(18):
    ans = max(ans, j)
print(ans)

Solution (Python):
import numpy as np
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = np.ones(vmax, dtype='int64') * wmax
dp[0] = 0

for i in range(N):
    wi, vi = map(int, input().split())
    dp[vi:] = np.fmin(dp[vi:], dp[:-vi] + wi)

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

Solution (Python):
import numpy as np
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = np.ones(vmax, dtype='int64') * wmax
dp[0] = 0

for i in range(N):
    wi, vi = map(int, input().split())
    ndp = np.copy(dp)
    ndp[vi:] = np.fmin(dp[vi:], dp[:-vi] + wi)
    dp = ndp

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

Solution (Python):
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = [wmax] * vmax
dp[0] = 0
 
for i in range(N):
    wi, vi = map(int, input().split())
    ndp = dp[:]
    for j in range(vi, vmax):
        ndp[j] = min(dp[j], dp[j-vi] + wi)
    dp = ndp

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

Solution (Python):
n,w=map(int,input().split())
l=[]
weight=[0]
value=[0]

for _ in range(n):
    a,b=map(int,input().split())
    value.append(b)
    weight.append(a)
maxvalue=sum(value)
dp=[[10**10 for i in range(maxvalue+1)]for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    for j in range(1,maxvalue+1):
        if value[i]<=j:
            
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-value[i]]+weight[i])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(maxvalue+1):
    if dp[-1][i]<=w:
        ans=i
print(ans)

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

V = N * 1000
dp = [[INF] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
s = 0
for i in range(N):
    w = wv[i][0]
    v = wv[i][1]
    for j in range(V + 1):
        dpp = dp[i][j - v] + w
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v] + w)
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if dp[i + 1][j] <= W:
            s = max(s, j)

print(s)

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

INF = W + 10
dp = [[INF for _ in range(N*10**3+10)] for _ in range(N+1)]

dp[0][0] = 0
for sum_v in range(N*10**3+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if sum_v - Vi >= 0:
            dp[n+1][sum_v] = min(dp[n][sum_v], dp[n][sum_v-Vi] + Wi)
        dp[n+1][sum_v] = min(dp[n][sum_v], dp[n+1][sum_v])

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

print(ans)

Solution (Python):
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


n, w = map(int, input().split())
dp = [[INF for j in range(10 ** 5 + 1)] for i in range(n)]
dp[0][0] = 0
for i in range(n):
    weight, value = map(int, input().split())
    if i == 0:
        dp[i][value] = weight
        continue
    for j in range(10 ** 5 + 1):
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if 0 <= j - value:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - value] + weight)
ans = 0
for i in reversed(range(10 ** 5 + 1)): 
    if dp[-1][i] <= w:
        ans = i
        break
print(ans)