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())
a=[]
dp=[]
res=0
for c in range(n):
   a.append(list(map(int,input().split())))
for v in range(n):
    tmp=a[v][0]
    a[v][0]=a[v][1]
    a[v][1]=tmp
b=max(a)[0]
for k in range(n+1):
  dp.append([])
  for l in range(n*b+1):
      if l==0 and k==0:
          dp[k].append(0)
      else:
          dp[k].append(10000000000)
for i in range(n):
   for j in range(b*n+1):
       if j>=a[i][0]:
           dp[i+1][j]=min(dp[i+1][j],dp[i][j-a[i][0]]+a[i][1],dp[i][j])
       else:
           dp[i+1][j]=min(dp[i+1][j],dp[i][j])
for s in range(n*b+1):
    if dp[n][s]<=w:
        res=s
print(res)

Solution (Python):
MAX_V = 100000
INF = 10 ** 10

n,w = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(n)]
dp = [[INF] * (MAX_V + 5) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(MAX_V + 1):
		if j + wv[i][1] <= MAX_V:
			dp[i + 1][j + wv[i][1]] = min(dp[i + 1][j + wv[i][1]],dp[i][j] + wv[i][0])
		dp[i + 1][j] = min(dp[i + 1][j],dp[i][j])
ma = 0
for i in range(MAX_V + 1):
	if dp[n][i] <= w:
		ma = max(ma,i)
print(ma)

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

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

dp = [[MAX_WEIGHT for _ in range(MAX_VAL+1)] for _ in range(N+1)]

dp[0][0] = 0
for i in range(N):
    value = wv[i][1]
    for v in range(MAX_VAL+1):
        dp[i+1][v] = dp[i][v]
        if v >= value:
            dp[i+1][v] = min(dp[i+1][v], dp[i][v-value]+wv[i][0])
max_v = 0
for i in range(MAX_VAL+1):
    if dp[N][i] <= W:
        max_v = i
print(max_v)

Solution (Python):
N,W=map(int,input().split())
import numpy as np
lst=np.array([list(map(int,input().split())) for _ in range(N)])
max_value=np.sum(lst[:,1])

a=np.array([W+1]*(max_value+1))

a[0]=0
for w,v in lst:
    
    a[v:]=np.minimum(a[:-v]+w,a[v:])
print(np.max(np.where(a<=W)))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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=[INF]*(V+1)
    dp[0]=0
    for i in range(n):
        newdp=dp[:]
        for x in range(V+1):
            if(x+v[i]<V+1):
                newdp[x+v[i]]=min(newdp[x+v[i]],dp[x]+w[i])
        dp=newdp
    for i in range(V,-1,-1):
        if(dp[i]<=W):
            print(i)
            return
resolve()

Solution (Python):
n,W = map(int,input().split())
dp = [[10**12] * (10**5+1) for i in range(n+1)]
dp[0][0] = 0
ma = 0
for i in range(1,n+1):
  w,v = map(int,input().split())
  ma += v
  for j in range(v):
    dp[i][j] = dp[i-1][j]
  for j in range(v,ma+1):
    dp[i][j] = min(dp[i-1][j-v]+w,dp[i-1][j])
m = 0
for i in range(ma+1):
  if dp[-1][i] <= W:
    m = i
print(m)

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

INF = 10**9+1
M = 10**5+1
dp = [INF]*M 
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(M-1, v-1, -1):
        dp[i] = min(dp[i], dp[i-v]+w)
        
for i in range(M-1, -1, -1):
    if dp[i] <= W:
        print(i)
        break

Solution (Python):
N, W = map(int, input().split())
dp = [{ 0: 0 }]
for i in range(N):
  w, v = map(int, input().split())
  d = dp[i]
  d2 = {}
  for v0 in d:
    w0 = d[v0]
    d2[v0] = w0
  for v0 in d:
    w0 = d[v0]
    if v0+v not in d:
      d2[v0+v] = w0+w
    else:
      d2[v0+v] = min(d2[v0+v], w0+w)
  dp.append(d2)
r = max([v for v in dp[N] if dp[N][v] <= W])
print(r)

Solution (Python):
import numpy as np

MAX_VALUE = 100100
INF_WEIGHT = 1 << 30


def main(n, w, items):
    dp = np.full(
        shape=(n + 1, MAX_VALUE),
        fill_value=INF_WEIGHT,
        dtype=int,
    )
    dp[0][0] = 0
    for i in range(0, n):
        weight, value = items[i]
        dp[i + 1][:value] = np.minimum(dp[i][:value], dp[i + 1][:value])
        dp[i + 1][value:] = np.minimum(dp[i][value:], dp[i][:MAX_VALUE - value] + weight)

    return np.max(np.where(dp[-1] <= w))


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Solution (Python):
import numpy as np


def main(n, w, items):
    MAX_VALUE = 100100
    dp = np.ones((n + 1, MAX_VALUE), dtype=int)
    dp = dp * (1 << 30)
    dp[0][0] = 0
    for i in range(0, n):
        weight, value = items[i]
        dp[i + 1][:value] = np.minimum(dp[i][:value], dp[i + 1][:value])
        dp[i + 1][value:] = np.minimum(dp[i][value:], dp[i][:MAX_VALUE - value] + weight)

    result = 0
    for v in range(MAX_VALUE):
        if dp[-1][v] <= w:
            result = v
    return result


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Solution (Python):


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

INF = float("inf")
"""
Wの最大が大きすぎるのでふつうのDPはできない
総重量W以下で、価値Vを得るときの最小重さをDPで求める感じ
"""

dp = [{} for _ in range(N+1)]

dp[0][0] = 0

for i,(w,v) in enumerate(wv):
    for v_sum,w_sum in dp[i].items():

        
        if v_sum in dp[i+1]:
            dp[i+1][v_sum] = min(dp[i+1][v_sum], w_sum)
        else:
            dp[i+1][v_sum] = w_sum

        
        if w + w_sum > W: continue

        
        if v + v_sum in dp[i+1]:
            dp[i+1][v+v_sum] = min(dp[i+1][v+v_sum], w + w_sum)
        else:
            dp[i+1][v+v_sum] = w + w_sum


print(max(dp[N].keys()))

Solution (Python):
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
 
V = 10**3+1
baggage = [0]*N
 
for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)
 
dp = [[10**9+1]*(N*V+1) for _ in range(N+1)]
dp[0][0] = 0  
 
for i in range(N):
    for v in range(N*V+1):
        if v - baggage[i][1] >= 0:
            dp[i+1][v] = min(dp[i+1][v], baggage[i][0]+dp[i][v-baggage[i][1]])
 
        dp[i+1][v] = min(dp[i][v], dp[i+1][v])
ans = 0
for K in range(N*V+1):
    if dp[N][K] <= W:
        ans = max(ans, K)
print(ans)

Solution (Python):
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]

V = 10**3+1
baggage = [0]*N

for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)

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

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

        else:
            dp[i+1][v] = min(dp[i][v], dp[i+1][v])
ans = 0
for K in range(N*V+1):
    if dp[N][K] <= W:
        ans = max(ans, K)
print(ans)

Solution (Python):
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
    left = v if v < 100001 else 100001
    right = left + ans + 1 if left + ans + 1 < 100001 else 100001
    for i in range(left, right)[::-1]:
        if bag[i-v] + w < bag[i] and bag[i-v] + w < W+1:
            bag[i] = bag[i-v] + w
            if i > ans:
                ans = i
print(ans)

Solution (Python):
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        ans = max(ans, i)
print(ans)

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

vmax = N*(10**3)

dp = [[W+1 for _ in range(vmax+1)] for _ 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(vmax+1):
    if j >= WV[i-1][1]:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-WV[i-1][1]] + WV[i-1][0])
    else:
      dp[i][j] = dp[i-1][j]

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

Solution (Python):

v_max = 100010
INF = 1000000100
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

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

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

result = 0
for j in range(v_max+1):
    if dp[n][j] <= w:
        result = j
print(result)

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

INF = 1e9+7
MAX_v = 100100
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[INF]*MAX_v for _ in range(n+1)]
dp[0][0]= 0
for i in range(1, n+1):
    for sum_v in range(MAX_v):
        dp[i][sum_v] = dp[i-1][sum_v]
        if sum_v-wv[i-1][1]>=0:
            dp[i][sum_v]=min(dp[i][sum_v], dp[i-1][sum_v-wv[i-1][1]]+wv[i-1][0])

ans = 0
for i in range(MAX_v):
    if dp[n][i]<=w:
        ans = i
print(ans)

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

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

for i in range(1,n+1):
    for j in range(10**5+1):
        if j >= item[i-1][1]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-item[i-1][1]]+item[i-1][0])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(10**5+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())
Vmax = max(v)*N+1
Wmax = max(w)*N+1
dp = [[Wmax] * (Vmax) for _ in range(N + 1)]
ans = int(0)
dp[0][0] = int(0)

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

for j in range(Vmax):
    if 0<=dp[N][j]<=W:
        ans = max(ans,j)

print(ans)

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

import collections
def main():
    N,W = map(int, input().split())
    I = collections.deque()
    for _ in range(N):
        I.append(tuple(map(int, input().split())))

    MV = 1 + N*(10**3)
    dp = [[0]*MV for _ in range(N+1)]
    inf = 2*10**9
    for j in range(MV):
        dp[0][j] = inf
    dp[0][0] = 0
    
    for i in range(N):
        w,v = I.popleft()
        for j in range(MV):
            if j < v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w)
    ans = 0
    for v,w in enumerate(dp[N]):
        if w <= W:
            ans = v
    print(ans)

if __name__ == '__main__':
    main()

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

import collections
def main():
    N,W = map(int, input().split())
    I = collections.deque()
    for _ in range(N):
        I.append(tuple(map(int, input().split())))

    MV = N*(10**3) + 1
    dp = [[0]*MV for _ in range(N+1)]
    inf = 2*10**9
    for j in range(MV):
        dp[0][j] = inf
    dp[0][0] = 0
    
    for i in range(N):
        w,v = I.popleft()
        for j in range(MV):
            if j < v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w)
    ans = 0
    for j in range(MV):
        if dp[N][j] <= W:
            ans = j
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = 1<<32

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[INF] * (max(v)*N+1) for i in range(N+1)]
    dp[0][0] = 0

    for i in range(N):
        for sumv in range(max(v)*N+1):
            if(sumv - v[i-1] >= 0):
                dp[i+1][sumv] = min(dp[i][sumv], dp[i][sumv-v[i-1]] + w[i-1])
            else:
                dp[i+1][sumv] = dp[i][sumv]

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

    
    

    print(ans)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

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

M = 100000
dp = [-1] * (M + 1)
dp[0] = W
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(M, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i + v] < dp[i] - w:
            dp[i + v] = dp[i] - w

for i in range(M, -1, -1):
    if dp[i] != -1:
        print(i)
        break

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

maxv = 10 ** 3 * N + 1
t = [-1] * maxv
t[0] = W
cmaxv = 0
for _ in range(N):
    nw, nv = map(int, input().split())
    for i in range(cmaxv, -1, -1):
        ti = t[i]
        if ti == -1:
            continue
        if t[i + nv] < ti - nw:
            t[i + nv] = ti - nw
            if cmaxv < i + nv:
                cmaxv = i + nv
print(cmaxv)

Solution (Python):
import sys
imput = sys.stdin.readline
def main():
    
    N, weight = map(int, input().split())
    W, V = [], []
    for _ in range(N):
        w, v = map(int, input().split())
        W.append(w)
        V.append(v)
    V_max = sum(V)

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

    
    ans = []
    for j in range(1, V_max+1):
        if dp[i+1][j] <= weight:
            ans.append(j)
    print(max(ans))

if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
max_value = N*(10**3)
dp = [[10**11]*(max_value+1) for _ in range(N+1)]
dp[0][0]=0
for j in range(1, N+1):
    w, v = map(int, input().split())
    for k in range(0, max_value+1):
        if k < v:
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = min(dp[j-1][k-v]+w, dp[j-1][k])
answer = 0
for index, weight in enumerate(dp[N]):
    if weight <= W:
        answer = index
print(answer)

Solution (Python):
def main():
    [N, W] = [int(num) for num in input().split()]

    products = []
    v_all = 0
    for i in range(N):
        w_v = [int(num) for num in input().split()]
        products.append(w_v)
        v_all += w_v[1]

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

    dp[0][0] = 0

    for i in range(N+1):
        if i == 0:
            continue
        for v in range(v_all+1):
            if v < products[i-1][1]:
                dp[i][v] = dp[i-1][v]
            else:
                dp[i][v] = min(dp[i-1][v-products[i-1][1]] + products[i-1][0], dp[i-1][v])

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

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,W = [int(s) for s in input().split()]
dp = [[10**10]*(1000*100+1) for _ in range(N+1)]

dp[0][0] = 0
for i in range(N):
    w, v = [int(s) for s in input().split()]
    for sum_v in range(1000*100+1):
        if sum_v - v >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v] + w)
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

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

print(ans)

Solution (Python):
import numpy as np

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

max_value = np.sum(np.array(WV), axis=0)[1]


dp = np.full(max_value+1, W+1, dtype='int64')

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

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

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

DP = [0] * (sum_v+1)

for i in range(N):
    for j in (reversed(range(sum_v))):
        if j == 0 or DP[j] != 0:
            if DP[j + v[i]] > DP[j] + w[i] or DP[j + v[i]] == 0:
                DP[j + v[i]] = DP[j] + w[i]
                

for j in (reversed(range(sum_v+1))):
    if DP[j] != 0 and DP[j] <= W:
        print(j)
        break

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

DP = [[float("inf")] * (10**5+1)]
for _ in range(N):
    DP.append([float("inf")] * (10**5+1))

DP[0][0] = 0

for n in range(N):
    for v in range(10 ** 5 + 1):
        if v - WV[n][1] >= 0:
            DP[n+1][v] = min(DP[n+1][v], DP[n][v - WV[n][1]] + WV[n][0])
        DP[n+1][v] = min(DP[n+1][v], DP[n][v])

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

print(ans)

Solution (Python):
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)
MAX_V = 100100

dp = [[MOD]*(MAX_V+1) for _ in range(N+1)]
dp[0][0]=0

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


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

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int, input().split())) for i in range(n)]
c=0
d=0
for i in range(n):
    c+=l[i][1];d+=l[i][0]
dp=[[0]*(c+1) for _ in range(n)]
for i in range(1,l[0][1]+1):
    dp[0][i]=l[0][0]
for i in range(l[0][1]+1,c+1):
    dp[0][i]=d
for i in range(1,n):
    for j in range(1,c+1):
        if j<=l[i][1]:
            dp[i][j]=min(dp[i-1][j],l[i][0])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-l[i][1]]+l[i][0])

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

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

N, W = map(int, input().split())
table = []
for i in range(N):
  w,v = map(int, input().split())
  table.append((w,v))
dp = [[W+1]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(1,N+1):
  w,v = table[i-1]
  for j in range(10**3*N+1):
    dp[i][j] = dp[i-1][j]
    if j>=v:
      dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)

for i in range(10**3*N,-1,-1):
  if dp[-1][i] <= W:
    print(i)
    exit()

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

N,W=map(int,input().split())
V = 1000
INF = 1e+10
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[INF]*(N*V+1) for _ in range(N+1)]
dp[0][0] = 0

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

for i in reversed(range(N*V+1)):
    if dp[N][i] <= W:
        print(i)
        break

Solution (Python):
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


dp = [{} for i in range(n+1)]


for i in range(n):
    Lw, Lv = L[i][0], L[i][1]
    dp[i+1][Lv] = Lw 
    for v, w in dp[i].items():
        dp[i+1][v] = min(dp[i+1].get(v, w), w) 
        ww = min(dp[i+1].get(v+Lv, w+Lw), w+Lw)
        if ww <=limit:
            dp[i+1][v+Lv] =ww 

print(max(dp[-1].keys()))

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

knapsack = [ [ int(v) for v in input().split() ] for i in range(n) ]
total_value = sum([ i[1] for i in knapsack ])

dp_list = [ w+1 for i in range(total_value+1) ]
dp_list[0] = 0

for wi, vi in knapsack:
    new_dp_list = [0] + [ w+1 for i in range(total_value) ]
    for j in range(total_value+1):
        if j >= vi:
            new_dp_list[j] = min(dp_list[j], dp_list[j-vi] + wi)
        else:
            new_dp_list[j] = dp_list[j]
    dp_list = new_dp_list

ans = 0
for i, v in enumerate(dp_list):
    if v != w+1:
        ans = i
print(ans)

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

N, W = map(int, input().split())
table = []
for i in range(N):
  w,v = map(int, input().split())
  table.append((w,v))
INF = W+1
dp = [[INF]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for k in range(10**3*N+1):
    w,v = table[i-1]
    dp[i][k] = dp[i-1][k]
    if v<=k and dp[i-1][k-v] <= INF:
      dp[i][k] = min(dp[i][k],dp[i-1][k-v]+w)

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

Solution (Python):
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv = L[i][0], L[i][1] 
    dp[i+1][Lv] = min(Lw, dp[i].get(Lv, Lw))          
    for v, w in dp[i].items():
        dp[i+1][v] = min(w, dp[i+1].get(v, w)) 
        tmp_w= min(Lw+ w, dp[i+1].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i+1][Lv+ v] = tmp_w
        
print(max(dp[-1].keys()))

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

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


dp = [{} for _ in range(N+1)]
dp[0][0] = 0

for i, (w, v) in enumerate(wv):
    
    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[N].keys()))

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

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


dp = [{} for _ in range(N+1)]
dp[0][0] = 0

for i, (w, v) in enumerate(wv):
    
    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 = [int(i) for i in input().split()]
WV = [[int(i) for i in input().split()] for j in range(N)]

import numpy as np
max_value = np.sum(np.array(WV), axis=0)[1]


dp = np.full(max_value + 1, W + 1, dtype='int64')

dp[0] = 0
for w, v in WV:
    
    
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(np.max(np.where(dp <= W)))

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

sum_v = sum(v)

dp = [[10**18] * (sum_v + 1) for _ in range(N + 1)]

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

for i in range(N):
    for j in range(sum_v + 1):
		
        if j - v[i] == 0:
            dp[i + 1][j] = min(w[i],dp[i][j])
        if dp[i][j] != 10**18:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j]+w[i])
		
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

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

print(0)

Solution (Python):
N,W = map(int, input().split())
INF = 10**12
dp = [[INF for i in range(110000)] for j in range(N+1)]

"""
dp[i][v] i個目の品物に対して、価値vをgetしうる重さの最小値
"""
dp[0][0] = 0

for i in range(N):
    w,v = map(int, input().split())
    for j in range(110000):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if v + j < 110000 and dp[i][j] != INF:
            
            dp[i+1][v+j] = min(dp[i][v+j],dp[i][j]+w)
            


res = dp[N]
ans = 0
for v,r in enumerate(res):
    if r <= W:
        ans = v
print(ans)

Solution (Python):

n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
m=0
for i in range(n):
    m+=wv[i][1]
inf=float("inf")
dp=[[inf]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    w,v=wv[i]
    for j in range(m+1):
        if j<v:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
ans=0
for i in range(m+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,W = LI()
wv = [LI() for _ in range(n)]
V = 0
for i in range(n):
    w,v = wv[i]
    V += v
    
dp = [[inf]*(V+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    w,v = wv[i]
    for j in range(V+1):
        if j < v:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v] + w)
res = 0
for i in range(V+1):
    if dp[-1][i] <= W:
        res = i
print(res)

Solution (Python):
from heapq import heappop, heappush
from operator import itemgetter


def branchAndBound(N: int, M: int, V: list, W: list, R: list) -> int:
    def upperbound(w, v, i):
        rest = M - w
        _v = v
        for j in range(i + 1, N):
            if W[j] >= rest:
                rest -= W[j]
                v += V[j]
                _v = v
            else:
                _v += R[j] * rest
                break
        return v, _v

    prov, tmp = upperbound(0, 0, -1)
    h = [(tmp, W[0], V[0] * (W[0] >= M), 0), (upperbound(0, 0, 0)[1], 0, 0, 0)]
    while h:
        _v, w, v, cur = heappop(h)
        if _v > prov or cur == N - 1:
            continue
        nxtw, nxtv = w + W[cur + 1], v + V[cur + 1]
        if nxtw >= M:
            heappush(h, (_v, nxtw, nxtv, cur + 1))
        _prov, ub = upperbound(w, v, cur)
        if _prov < prov:
            prov = _prov
        if ub < prov:
            heappush(h, (ub, w, v, cur + 1))
    return -prov


def main():
    N, M, *L = map(int, open(0).read().split())
    t = [(v, w, v / w) for w, v in zip(*[iter(L)] * 2)]
    t.sort(key=itemgetter(2), reverse=True)
    V, W, R = [], [], []
    for v, w, r in t:
        V += [-v]
        W += [-w]
        R += [r]
    ans = branchAndBound(N, -M, V, W, R)
    print(ans)
    
if __name__=="__main__":main()

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf') for _ in range(10**5+1)] for _ in range(N)]
    dp[0][0] = 0
    dp[0][v[0]] = w[0]

    js = [0,v[0]]

    for i in range(1,N):
        for j in js[:]:
            js.append(j+v[i])
        js = list(set(js))

        for j in js:
            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]

    res = 0
    for i,j in enumerate(dp[-1]):
        if j != float("inf") and j <= W:
            res = i
    print(res)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

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

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
sum=0
for i in range(n):
  sum+=l[i][1]
dp=[[999999999999 for i in range(sum+1)] for j in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  for j in range(sum+1):
    dp[i][j]=min(dp[i-1][max(j-l[i-1][1],0)]+l[i-1][0],dp[i-1][j])
for i in range(sum,-1,-1):
  if dp[n][i]<=w:
    print(i)
    break

Solution (Python):
import sys
from collections import defaultdict
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp =[defaultdict(int) for _ in range(n)]
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], L[i][0])) 
    for v, w in dp[i-1].items():
        dp[i][v] = min(w, dp[i].get(v, w)) 
        dp[i][v+L[i][1]] = min(w + L[i][0], dp[i-1].get(v+L[i][1], w + L[i][0]) ) 
        

ans =0
for v, w in dp[-1].items():
    if w<=limit:
        if ans < v:
            ans = v

print(ans)

Solution (Python):
import sys
n, limit = map(int, sys.stdin.readline().split()) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]

dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in dp[i-1].items():
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in dp[-1].items():
    if w <=limit:
        if ans < v:
            ans = v

print(ans)