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 _ in range(N):
    tmp = list(map(int, input().split()))
    w.append(tmp[0])
    v.append(tmp[1])
V = sum(v)
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] = min(dp[i + 1][j], dp[i][j])


ans = []
for j in range(V+1):
    if dp[N][j] <= W:
        ans.append(j)
print(max(ans))

Solution (Python):
n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
V=sum(v)+1
dp=[10**10 for i in range(sum(v)+1)]
dp[0]=0
for i in range(n):
    for j in range(V-1,-1,-1):
        if dp[j]!=10**10:
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
for i in range(V-1,-1,-1):
    if dp[i]<=W:
        print(i)
        exit()

Solution (Python):
N,W = map(int,input().split())
INF = 10**12
V = 1000 * N
Data = []
Data.append([0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))

DP = [[INF]*(V+1) for _ in range(N+1)]
for n in range(N+1):
    DP[n][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        wi,vi = Data[n]
        if v >= vi:
            DP[n][v] = min(DP[n][v],DP[n-1][v-vi]+wi)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

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

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

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


dp = [[float("inf")]*(MAXV+1) for i in range(N+1)]


dp[0][0] = 0


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

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

Solution (Python):
n, w = map(int, input().split())
wt = []
v = []
for _ in range(n):
    a, b = map(int, input().split())
    wt.append(a)
    v.append(b)

total_value = 0
for i in v:
    total_value += i

dp = [float("inf")] * (total_value + 1)
dp[0] = 0
for i in range(len(wt)):
    for j in range(total_value, v[i] - 1, -1):
        dp[j] = min(dp[j], dp[j - v[i]] + wt[i])
ans = 0
for i in range(len(dp)):
    if dp[i] <= w:
        ans = max(ans, i)
print(ans)

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)
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i-1]:
            dp[i][j]=min(dp[i-1][j-v[i-1]]+w[i-1],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Solution (Python):
n, w = map(int, input().split(' '))
items = [[]] * n
for i in range(n):
  weight, val = map(int, input().split(' '))
  items[i] = [weight, val]



MAX_V = 100100


dp = [[0]] * (n+1)
for i in range(n+1):
  dp[i] = [10**10 for num in range(MAX_V)]


dp[0][0] = 0

for i in range(n):
  weight , val = items[i]
  for sum_v in range(MAX_V):
    
    if sum_v - val >= 0:
      dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - val] + weight)
    
    dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0
for sum_v in range(MAX_V):
  if dp[n][sum_v] <= w:
    
    ans = sum_v


print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def solve():
  n,wmax = (int(i) for i in input().split())
  query = []
  v = 101000
  for i in range(n):
    tw,tv = (int(i) for i in input().split())
    query.append((tw,tv))
  dp = [[-1]*(v+1) for _ in range(n+1)]
  for i in range(n):
    dp[i][0] = 0

  for i in range(n):
    nw,nv = query[i]
    for value in range(v-nv):
      if dp[i][value] == -1:
        a = 1
      if dp[i][value] > -1 and dp[i][value]+nw <=wmax:
         if dp[i+1][value+nv] == -1:
           dp[i+1][value+nv] = dp[i][value]+nw
         else:
           dp[i+1][value+nv] = min(dp[i][value]+nw,dp[i+1][value+nv])
      if dp[i][value] > -1:
        if dp[i+1][value] == -1:
          dp[i+1][value] = dp[i][value]
        else:
          dp[i+1][value] = min(dp[i+1][value],dp[i][value])

  ans = 0
  for value in range(v):
    if dp[n][value] <= wmax and dp[n][value]!= -1:
      ans = max(ans,value)
  print(ans)
solve()

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)
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i-1]:
            dp[i][j]=min(dp[i-1][j-v[i-1]]+w[i-1],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Solution (Python):
N,W=map(int,input().split())
taple=[]
for i in range(N):
    w,v=map(int,input().split())
    taple.append((w,v))
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    w,v=taple[i-1]
    for j in range(N*(10**3)+1):
        if j>=v:
            dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Solution (Python):


"""
20191120
93分
test:
6 8
2 3
1 2
3 6
2 1
1 3
5 85
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())
    V = sum(vs)

    
    dp = [[None for _ in range(V+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    dp[0][vs[0]] = ws[0]
    existance[0].add(vs[0])

    for n in range(N-1):
        for v in existance[n]:
            
            if dp[n+1][v] is None:
                dp[n+1][v] = dp[n][v]
            else:
                dp[n+1][v] = min(dp[n][v], dp[n+1][v])
            existance[n+1].add(v)

            
            if dp[n+1][v+vs[n+1]] is None:
                if dp[n][v] + ws[n+1] <= W:
                    dp[n+1][v+vs[n+1]] = dp[n][v] + ws[n+1]
                    existance[n+1].add(v+vs[n+1])
            else:
                dp[n+1][v+vs[n+1]] = min(dp[n][v] + ws[n+1], dp[n+1][v+vs[n+1]])
                

    ans = 0
    for v in range(V, 0, -1):
        if dp[-1][v] is not None:
            ans = v
            break

    return ans


def miss_main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


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

Solution (Python):
import sys
if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

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 = int(pow(10,3)+1) * N
dp = [[float('INF') for _ in range(V+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
	for sum_v in range(V):
		if sum_v - v[i] >= 0:
			dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])
		dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

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

print(max_v)

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

Solution (Python):
inf = 10**9 + 7

n, W = map(int, input().split())
dp = []
w = []
v = []
for _ in range(n):
    dp.append([inf for _ in range(10**5+1)])
    line = list(map(int, input().split()))
    w.append(line[0])
    v.append(line[1])
dp.append([inf for _ in range(10**5+1)])
for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(10**5+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] = min(dp[i][j], w[i])
ans = 0
for j in range(10**5+1):
    if dp[n][j] <= W:
        ans = j

print(ans)

Solution (Python):
def main():
    N, W_MAX = (int(i) for i in input().split())
    W = []
    V = []
    for _ in range(N):
        w, v = (int(i) for i in input().split())
        W.append(w)
        V.append(v)
    V_SUM = sum(V)
    INF = (1 << 60)
    dp = [INF] * (V_SUM + 1)
    dp[0] = 0
    for i in range(N):
        for j in range(V[i], V_SUM + 1)[::-1]:
            dp[j] = min(dp[j], dp[j - V[i]] + W[i])
    print(max(j for j in range(V_SUM+1) if dp[j] <= W_MAX))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())

dp = [defaultdict(int) for _ in range(n)]
w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for vb, wb in dp[i-1].items():
        dp[i][vb] = min(wb, dp[i].get(vb, wb))
        tmp = min(wb + w, dp[i].get(vb+ v, wb + w))
        if tmp <=W:
            dp[i][v+ vb] = tmp
    dp[i][v] = min(dp[i].get(v, w), w)


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

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

table = {i: [10**10]*(10**5+1) for i in range(N+1)}
table[0][0] = 0
def dp(N, V):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(V+1):
      table[i][j] = min(table[i-1][j-v]+w, table[i-1][j])
  for k in range(V, 0, -1):
    if table[N][k] <= W:
      return k

print(dp(N, 10**5))

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)
sum_v = sum(v)
dp = [float('inf')] * (sum_v + 1)
dp[0] = 0
for i in range(n):
	for j in range(sum_v - v[i], -1, -1):
		dp[j + v[i]] = min(dp[j] + w[i], dp[j + v[i]])
res = 0
for vi, wi in enumerate(dp):
	if wi <= W:
		res = vi
print(res)

Solution (Python):

import sys
n, W = map(int, sys.stdin.readline().split())

dp = [dict() for _ in range(n)]
w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][v] = min(w , dp[i].get(v, w))
    for vb, wb in dp[i-1].items():
        dp[i][vb] = min(dp[i].get(vb, wb), wb)
        tmp = min(wb + w, dp[i].get(vb+ v, wb+w))
        if tmp <=W:
            dp[i][v+ vb] = tmp
    

print(sorted(dp[-1].items())[-1][0])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
import numpy as np
inf = 10**13
V = 10**5
N, W = map(int, input().split())
dp = np.array([inf]*(V+1), dtype = np.int64)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    np.minimum(dp[:-v]+w, dp[v:], out = dp[v:])
print(np.where(dp<=W)[0][-1])

Solution (Python):
N,W=map(int,input().split())
stones=[None]*N
allv=0
for i in range(N):
  w,v=map(int,input().split())
  allv+=v
  stones[i]=[w,v]
  
import numpy as np
MAXW=10**9+1
dp=np.full(allv+1,MAXW,dtype=int)
dp[0]=0
for i in range(len(stones)):
  w=stones[i][0]
  v=stones[i][1]
  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,m=map(int,input().split())
wv=[tuple(map(int,input().split())) for _ in range(n)]
x=10**5
dp=[[float("inf")]*(x+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=wv[i-1]
    dp[i][v]=min(dp[i-1][v],w)
    for j in range(x+1):
        if dp[i-1][j]==float("inf"):
            continue
        if j+v<=x:
            dp[i][j+v]=min(dp[i][j+v],dp[i-1][j]+w)
        dp[i][j]=min(dp[i-1][j],dp[i][j])

ans=0
for i in range(x+1):
    if dp[n][i]<=m:
        ans=i

print(ans)

Solution (Python):

import sys
n,W = map(int, sys.stdin.readline().split())

dp = [[1000000001 for i in range(100001)] for _ in range(n)]


w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for va in range(100001): 
        if va < v: 
            dp[i][va] = dp[i-1][va]
        else: 
            dp[i][va] = min(dp[i-1][va], dp[i-1][va-v] + w)
    dp[i][v] = min(dp[i][v], w)

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

Solution (Python):
import sys

import numpy as np

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


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])
    UV = np.sum(WV[:, 1])
    UW = np.sum(WV[:, 0])

    dp = np.full([UV+1], UW*2, np.int64)
    dp[0] = 0

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

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


main()

Solution (Python):
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]
vMax = 10**5
dp = [[10**9+1 for i in range(vMax + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    wi, vi = wv[i-1]
    for j in range(vMax + 1):
        if vi > j:
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
        else:
            dp[i][j] = min(dp[i- 1][j], dp[i - 1][j - vi] + wi)
for i in range(vMax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, input().rstrip('\n').split()))
    dp = [10 ** 10] * (1000 * n + 1)
    dp[0] = 0
    mw = 0
    for _ in range(n):
        wv, vv = list(map(int, input().rstrip('\n').split()))
        for i in range(1000 * n - vv, -1, -1):
            dp[i+vv] = min(dp[i+vv], dp[i] + wv)
    mt = 0
    for i in range(len(dp)):
        if dp[i] <= w:
            mt = max(mt, i)
    print(mt)


if __name__ == '__main__':
    solve()

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

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

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

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

Solution (Python):
INF = 2000000000
n,limit_w = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())

sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]


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


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

Solution (Python):
INF = 2000000000
n,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1 ,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v, -1, -1):
    if dp[i] <= limit_w:
        print(i)
        break

Solution (Python):
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
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())
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)]




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


max_value = 0
for i in range(sum_v + 1):
    if dp[n][i] <= W:
        max_value = i
print(max_value)

Solution (Python):
INF = 2000000000
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v ,-1,-1):
    if dp[i] <= limit_w:
        print(i)
        break

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [10 ** 10] * (10 ** 3 * n + 1)
    dp[0] = 0
    max_v = 0
    for ww, vv in wv:
        for i in range(max_v, -1, -1):
            dp[i+vv] = min(dp[i+vv], dp[i] + ww)
            max_v = max(max_v, i+vv)
    mt = 0
    for i in range(len(dp)):
        if dp[i] <= w:
            mt = max(mt, i)
    print(mt)


if __name__ == '__main__':
    solve()

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

dp=np.full(10**5+10,10**18,int)
dp[0]=0
for w,v in WV:
  np.minimum(dp[v:], dp[:-v].copy()+w, out=dp[v:])
print(np.where(dp<=W)[0][-1])

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

dp[0][0] = 0
sum_v = 0
for i in range(1, N + 1):
    w, v = [int(_) for _ in input().split()]
    sum_v += v

    for j in range(len(dp[i])):
        if j > sum_v: break
        
        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)

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

Solution (Python):
n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-v-1,-1,-1):
    if dp[j]+w<dp[j+v]:
      dp[j+v]=dp[j]+w
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)

Solution (Python):
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[[0 for i in range(10**5+1)] for j in range(N+1)]
dp[0][1:]=[10**18 for i in range(10**5)]
for i in range(N+1):
    for j in range(10**5+1):
        if i>0:
            if j-WV[i-1][1]>=0:
                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]
for i in reversed(range(10**5+1)):
    if dp[N][i]<=W:
        print(i)
        break

Solution (Python):
def Knapsack2(W,w,v): 
    n=len(w)
    v_max=10**5+5
    
    dp=[0]+[float('inf') for _ in range(v_max+1)]
    for i in range(n):
        for j in range(v_max,v[i]-1,-1):
            if j >= v[i]:
                dp[j]=min(dp[j],dp[j-v[i]]+w[i])
    ans=0
    for i in range(v_max+1):
        if dp[i]<=W:
            ans=i
    print(ans)

def main():
    n,W = 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())
    Knapsack2(W,w,v)
if __name__ == "__main__":
    main()

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

INF = 9999999999
MAXN = 110
MAXV = 100010
weights = [0]*(MAXN)
values = [0]*(MAXN)

dp = [[INF]*(MAXV) for i in range(MAXN)]
dp[0][0] = 0

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_v in range(MAXV):
        if sum_v >= values[i]:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],
                                 dp[i][sum_v-values[i]]+weights[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v],
                             dp[i][sum_v])
ans = 0
for sum_v in range(MAXV):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Solution (Python):
INF = 2000000000
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v ,-1,-1):
    if dp[i] <= limit_w:
        print(i)
        break

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,W = map(int,readline().split())
m = map(int,read().split())
WV = zip(m,m)


INF = 10**18
dp = np.full(10**5+10,INF,np.int64)

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

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

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""



INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]




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


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

Solution (Python):
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    t = sum(v)
    l = [m + 1] * (t + 1)
    l[0] = 0
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            k = l[j - v[i]] + w[i]
            if k < l[j]:
                l[j] = k
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()

Solution (Python):
def printdp(dp):
    return
    print({i:v for i, v in enumerate(dp) if v < 10000})

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(N)]
    V = sum(v for _, v in wv)
    dp = [0] + [float('inf')] * V
    for wi, vi in wv:
        for i in range(V, vi - 1, -1):
            t = dp[i - vi] + wi
            if t < dp[i]:
                dp[i] = t
    for i in range(V, -1, -1):
        if dp[i] <= W:
            print(i)
            return


if __name__ == '__main__':
    main()

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""



INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)] 




dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 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 = 0
for i in range(sum_v + 1):
    if dp[n][i] <= limit_w:
        ans = i
print(ans)

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


def main():
    N, W = map(int, readline().split())
    wv = map(int, read().split())
    dp = np.full(10 ** 5 + 1, W + 1, np.int64)
    dp[0] = 0

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

N, W = map(int, input().split())
WV = np.array([list(map(int, input().split())) for _ in range(N)])
max_v = np.sum(WV[:, 1])

dp = np.full(max_v+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())

dp=[]
for i in range((10**5)+1):
    dp.append([0,float("inf")])
dp[0][0]=1
dp[0][1]=0
it=[]
val=[]
for i in range(n):
    a,b=input().split()
    it.append(int(a))
    val.append(int(b))
for i in range(n):
    x=val[i]
   
    ac=[]
    for j in range(len(dp)-x,-1,-1):
        if dp[j][0]==1:
            if it[i]+dp[j][1]<=w:
                dp[j+x][1]=min(dp[j+x][1],it[i]+dp[j][1])
                ac.append(j+x)
   
    for i in ac:
        dp[i][0]=1
  
print(max([j for j,i in enumerate(dp) if i[0]==1]))

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""



INF = 2000000000
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)
dp = [[INF for i in range(V + 1)] for j in range(n + 1)]


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

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""



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


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

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""



INF=2*10**9
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())
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]


dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+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=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""



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


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

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""



INF=2*10**9
n,W = map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]


dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+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=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
INF = float("inf")

def main():
    N, W = map(int, input().split())
    weight = [0]*N
    value = [0]*N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())
    
    V = 100010
    dp = [[INF]*V for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(V):
            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])
    
    ans = 0
    for j in range(V):
        if dp[N][j] <= W:
            ans = j
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):




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

l=[10**10]*(10**5+1)
l[0]=0
dp=l[:]


for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=10**10 and item+w<=W:
            dp[index+v]=min(l[index+v],item+w)
    l=dp[:]

ans=0
for index, item in enumerate(l):
    if item!=10**10:
        ans=index
    else:
        continue
print(ans)