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

w = [w_v[i][0] for i in range(N)]
v = [w_v[i][1] for i in range(N)]


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

for i in range(N):
    for j in range(max(v)*N+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]

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

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

    INF = float('inf')
    dp = [list([INF] * (10 ** 5 + 101)) for _ in range(N)]
    dp[0][wv[0][1]] = wv[0][0]
    dp[0][0] = 0

    for i in range(1,N):
        w = wv[i][0]
        v = wv[i][1]
        for j in range(10 ** 5 + 1):
            sum_v = j + v
            if dp[i-1][j] + w <= W:
                dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][j] + w)
            dp[i][j] = min(dp[i][j], dp[i-1][j])
    
    max_v = 0
    for i in range(10 ** 5 + 1):
        if dp[N-1][i] <= W:
            max_v = i
    print(max_v)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  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=sum(v)
  dp=[[float('inf')]*(v_sum+1) for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(v_sum+1):
      dp[i+1][j]=dp[i][j - v[i]] + w[i] if j - v[i]>=0 else dp[i+1][j]
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=0
  for j in range(v_sum+1):
    if dp[n][j] <= W:
      ans = j
  print(ans)
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)]
mv=pow(10,3)*n+1
mw=pow(10,9)*n+1
dp=np.full(mv,mw,np.int64)

dp[0]=0
for i in range(n):
      w_=wv[i][0]
      v_=wv[i][1]
      dp[v_:]=np.minimum(dp[v_:],dp[:-v_]+w_)
print(np.where(dp<=w)[-1][-1])

Solution (Python):
import sys
from io import StringIO
import unittest

def resolve():
    N, W = map(int, input().split())

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

    
    
    inf = 10 ** 10
    max_v = sum([v for w, v in wv])+ 10
    sum_w = sum([w for w, v in wv])

    dp = [[inf for _ in range(max_v + 2)] for __ in range(N + 1)]

    
    

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

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

    
    
    
    
    print(max([i for d in dp for i, w in enumerate(d) if w <= W]))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 8
3 30
4 50
5 60"""
        output = """90"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1 1000000000
1000000000 10"""
        output = """10"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6 15
6 5
5 6
6 4
6 6
3 5
7 2"""
        output = """17"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):






"""Module docstring
"""

import sys
from collections import defaultdict


def solve(values, _nb, max_capacity):
    dp = {}
    dp[0] = 0
    for w, v in values:
        keys = sorted(dp.keys(), reverse=True)
        for vk in keys:
            if vk + v in dp:
                dp[vk + v] = min(dp[vk + v], dp[vk] + w)
            else:
                dp[vk + v] = dp[vk] + w
    result = 0
    for v, w in dp.items():
        if w <= max_capacity and v > result:
            result = v
    return result


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    
    return dp[nb][max_capacity]


INF = pow(10, 9) * 100


def solve_errichto(values, _nb, max_capacity):
    sum_values = sum(v for _w, v in values)
    
    dp = [INF] * (sum_values + 1)
    dp[0] = 0
    for w, v in values:
        for value_already in range(sum_values - v, -1, -1):
            tmp = dp[value_already] + w
            if dp[value_already + v] > tmp:
                dp[value_already + v] = tmp
    result = 0
    for v, w in enumerate(dp):
        if w <= max_capacity:
            result = max(result, v)
    return result


def do_job():
    "Do the work"
    
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve_errichto(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(10**3 * N + 1)
    dp[0] = 0
    ans = 0
    for w, v in wv:
        for j in range((10**3 * N) - v, -1, -1):
            if dp[j] >= 0 and dp[j] + w <= W:
                if dp[j+v] < 0 or dp[j+v] > dp[j] + w:
                    dp[j+v] = dp[j] + w
                if ans < j+v:
                    ans = j+v
    print(ans)


main()

Solution (Python):
N,W = map(int,input().split())
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
max_v,max_w = 0,0
for i,j in zip(w,v):
    max_w += i
    max_v += j
dp = [[float("inf")]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(max_v+1):
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(1,max_v+2):
    if W >= dp[N][-i]:
        print(max_v+1-i)
        break

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

Solution (Python):
import numpy as np
N,W = map(int,input().split())
dp = np.full(N*1000+1,W+1)
dp[0] = 0
for _ 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][-1])

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

dp = [[10**12]*((10**3)*N+1) for i in range(N+1)]
dp[0][0] = 0
v_sum = 0
for i in range(N):
    w, v = map(int,input().split())
    v_sum += v
    for j in range((10**3)*N+1):
        if j > v_sum:
            break
        if j - v >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
        else:
            dp[i+1][j] =dp[i][j]

for i in range(len(dp[-1])):
    if 0 < dp[-1][i]<= M:
        ans = i
    else:
        pass

print(ans)

Solution (Python):
n,w=map(int,input().split())
a=[10**10]*100001
a[0]=0
from copy import copy
c=0
for i in range(n):
    x,y=map(int,input().split())
    b=copy(a)
    c+=y
    for j in range(y,100001):
        if j<=c:
            b[j]=min(a[j-y]+x,a[j])
    a=copy(b)
l=[]
for i in range(len(a)):
    if a[i]<=w:
        l.append(i)
print(l[-1])

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

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

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

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

print(ans)

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




dp = [[10 ** 12] * 100100 for _ in range(110)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(100100):

        if v[i] <= sum_v:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - v[i]] + w[i])

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




for sum_v in range(100100):
    if dp[N][sum_v] <= W:
        ans = sum_v
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())

def solve(w,v):
    
    dp = [[W+1]*(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 < v[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
    for i in range(10**5,-1,-1):
        if dp[-1][i]<=W:
            ans = i
            break
    return ans
print(solve(w,v))

Solution (Python):

N,W=map(int,input().split())
A=[[0]]+[[int(x) for x in input().split()] for i in range(N)]
A_w=[]
V=N*10**3

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

for i in range(1,N+1):
    w=A[i][0]
    v=A[i][1]
    for sum_v in range(V+1):
        if sum_v-v>=0:
            dp[i][sum_v]=min(dp[i][sum_v],dp[i-1][sum_v-v]+w)
        dp[i][sum_v]=min(dp[i][sum_v],dp[i-1][sum_v])
Max=0
for i in range(V+1):
    if dp[-1][i]<=W:
        Max=i
print(Max)

Solution (Python):
n, w = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
sumv = 0
for i in range(n):
    sumv += p[i][1]
p.insert(0, [0, 0])
inf = w + 1
dp = [[inf for _ in range(sumv + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i in range(1, n + 1):
    m = 0
    for j in range(1, sumv + 1):
        if j >= p[i][1]:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(sumv, -1, -1):
    if not dp[n][i] == inf:
        print(i)
        exit()

Solution (Python):
n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
inf = 10**10
sumV = sum(V)
DP = [[inf for j in range(sumV+1)] for i in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    for j in range(V[i-1]):
        DP[i][j] = DP[i-1][j]
    for j in range(V[i-1], sumV+1):
        DP[i][j] = min(DP[i-1][j], DP[i-1][j-V[i-1]]+W[i-1])
for j in range(sumV, 0, -1):
    if DP[n][j] <= m:
        print(j)
        exit()

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write

INF=int(10e9)


def knapSack(V):
    for i in range(n + 1):
        for v in range(V + 1):
            if v == 0:
                K[i][v] = 0
            elif val[i - 1] <= v:
                K[i][v] = min(wt[i - 1] + K[i - 1][v - val[i - 1]], K[i - 1][v])
            else:
                K[i][v] = K[i - 1][v]

    return K[n][V]

n,w=mdata()
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
V=100005
K = [[1000000007 for x in range(V + 1)] for x in range(n + 1)]
knapSack(V)
m=0
for i in range(n + 1):
    for v in range(V + 1):
        if 1<=K[i][v]<=w :
            m=max(m,v)
print(m)

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

    maxvalue = sum(value)
    dp = [[float('inf')]*(maxvalue+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for v in range(maxvalue+1):
            if v - value[i] < 0:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v])
            else:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v-value[i]]+weight[i])
                dp[i+1][v] = min(dp[i+1][v], dp[i][v])
    
    ans = 0
    for i in range(N+1):
        for j in range(maxvalue+1):
            if dp[i][j] <= W:
                ans = max(ans, j)
    
    print(ans)
            
if __name__ == '__main__':
    solve()

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

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

for i in range(N+1):
    w,v=items[i]
    dp[i][v]=w

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

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

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

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

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

for i in range(1, N):
    w, v = S[i]
    for j in range(v):
        dp[i][j] = dp[i-1][j]

    if dp[i-1][v] == -1:
        dp[i][v] = w
    else:
        dp[i][v] = min(dp[i-1][v], w)

    for j in range(v+1, MAX_V+1):
        if dp[i-1][j] == -1 and dp[i-1][j-v] == -1:
            continue
        elif dp[i-1][j] == -1:
            if dp[i-1][j-v]+w > W:
                continue
            else:
                dp[i][j] = dp[i-1][j-v]+w
        elif dp[i-1][j-v] == -1:
            dp[i][j] = dp[i-1][j]
        else:
            if dp[i-1][j-v]+w > W:
                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_V, 0, -1):
    if dp[N-1][i] != -1:
        print(i)
        break

Solution (Python):
N, W = [int(i) for i in input().split()]
noValue = [[W+1 for j in range(100001)] for i in range(N)] 
w,v = [int(i) for i in input().split()]
maxValue = v
noValue[0][v] = w

for i in range(1,N) :	
	noValue[i][0] = 0
	w, v = [int(i) for i in input().split()] 
	for j in range(1,min(maxValue+v+1, 100001)) : 
		if j < v  :
			noValue[i][j] = noValue[i-1][j]
		else :
			if noValue[i-1][j - v] == W + 1 :
				if j == v :
					noValue[i][j] = w
					maxValue = max(maxValue, j)
				else :
					noValue[i][j] = noValue[i-1][j]
			elif noValue[i-1][j-v] + w > W :
				noValue[i][j] = noValue[i-1][j]
			else :
				noValue[i][j] = min(noValue[i-1][j - v] + w, noValue[i-1][j])
				maxValue = max(maxValue, j)
print(maxValue)

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())
mv = sum(v)
dp = [[float("INF")]*(mv+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for s in range(mv+1):
        if s - v[i] < 0: dp[i+1][s] = dp[i][s]
        else: dp[i+1][s] = min(dp[i][s], dp[i][s-v[i]] + w[i])
ans = 0
for x in range(1,mv+1):
    if dp[n][x] <= W: ans = x
print(ans)

Solution (Python):
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
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]: dp[i+1][j] = min(dp[i][j] ,dp[i][j-v[i]]+w[i])
        else: dp[i+1][j] = dp[i][j]
ans = 0
for i in range(V+1):
    if dp[N][i]<=W: ans=i
print(ans)

Solution (Python):
from sys import stdin



def chmin(a,b):
    if a > b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, W = list(map(int,_in[0].split(' ')))  
    w_v_arr = []
    V = 0
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  
        w_v_arr.append(_)
        V += _[1]
    
    dp = [[float('inf')] * (V+1) for _ in range(N+1)]  
    
    dp[0][0] = 0  

    
    for i in range(N):
        for v in range(0,V+1):
            if v >= w_v_arr[i][1]:
                dp[i+1][v] = chmin(dp[i+1][v],dp[i][v-w_v_arr[i][1]]+w_v_arr[i][0])
            dp[i+1][v] = chmin(dp[i+1][v],dp[i][v])
    cnt = 0
    for v in range(0,V+1):
        if dp[N][v] <= W:
            cnt = v
    
    print(cnt)

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())
mv = n*max(v)
dp = [[float("INF")]*(mv+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for s in range(mv+1):
        if s - v[i] < 0: dp[i+1][s] = dp[i][s]
        else: dp[i+1][s] = min(dp[i][s], dp[i][s-v[i]] + w[i])
ans = 0
for x in range(1,mv+1):
    if dp[n][x] <= W: ans = x
print(ans)

Solution (Python):
n,W = map(int,input().split())
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1,n+1): w[i],v[i] = map(int,input().split())
mv = n*max(v)
dp = [[float("INF")]*(mv+1) for _ in range(n+1)]
for i in range(n): dp[i][0] = 0
for i in range(1,n+1):
    for s in range(1,mv+1):
        if s - v[i] < 0: dp[i][s] = dp[i-1][s]
        else: dp[i][s] = min(dp[i-1][s], dp[i-1][s-v[i]] + w[i])
ans = 0
for x in range(1,mv+1):
    if dp[n][x] <= W: ans = x
print(ans)

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

dp = [[0 for _ in range(10**5 + 1)] for _ in range(N+1)]
for i in range(1, 10**5 + 1):
    dp[0][i] = float('inf')

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

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

print(ans)

Solution (Python):
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
    wv.append(list(map(int,input().split())))
dp=np.full(100001,w+1) 
dp[0]=0
for i in range(n):
    w_=wv[i][0]
    v_=wv[i][1]
    dp[v_:]=np.minimum(dp[v_:],dp[:-v_]+w_)

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

Solution (Python):
def main():
    N, W = list(map(int, input().split()))
    INF = float("inf")
    DP = [[INF for i in range(10**5+1)] for j in range(N+1)]
    DP[0][0] = 0
    for i in range(N):
        w, v = list(map(int, input().split()))
        for sum_v in range(10**5+1):
            if sum_v - v >= 0:
                DP[i+1][sum_v] = min(DP[i][sum_v],DP[i][sum_v-v]+w)
            
            DP[i+1][sum_v] = min(DP[i+1][sum_v],DP[i][sum_v])
            
    for i in range(10**5+1):
        if DP[N][i] <= W:
            ans = i
    print(ans)

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

Solution (Python):
import copy
n,w = map(int,input().split())
V = n*10**3+2
b = [float("inf")]*V
b[0] = 0
a = [float("inf")]*V
a[0] = 0
for _ in range(n):
  wi,vi = map(int,input().split())
  for i in range(vi):
    a[i] = min(b[i],wi)
  for i in range(vi,V):
    a[i] = min(b[i],b[i-vi]+wi)
  b = copy.copy(a)
i = 0
while b[i] <= w:
  i += 1
print(i-1)

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

    for i in range(1,N+1):
        for v in range(sum_value+1):
            if v - value[i-1] < 0:
                dp[i][v] = min(dp[i][v], dp[i-1][v])
            else:
                dp[i][v] = min(dp[i][v], dp[i-1][v-value[i-1]] + weight[i-1])
                dp[i][v] = min(dp[i][v], dp[i-1][v])
    
    ans = 0
    for i in range(N+1):
        for v in range(sum_value+1):
            if dp[i][v] <= W:
                ans = max(ans,v)
    
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

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

dp = [[INF]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0

for n in range(N):
    for sum_v in range(max_v+1):
        weight = WV[n][0]
        value = WV[n][1]
        
        if sum_v-value >= 0:
            dp[n+1][sum_v] = min(dp[n+1][sum_v], dp[n][sum_v-value]+weight)
        dp[n+1][sum_v] = min(dp[n+1][sum_v], dp[n][sum_v])
ans = 0

for sum_v in range(max_v+1):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Solution (Python):
N,W = map(int,input().split())
k,l = 0,0
lv = [0] * N
lw = [0] * N
for i in range(N):
    lw[i],lv[i] = map(int,input().split())
V = sum(lv)
dp = [[float("inf") for i in range(V+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sv in range(V+1):
        if sv-lv[i] < 0:
            dp[i+1][sv] = dp[i][sv]
        else:
            dp[i+1][sv] = min(dp[i][sv],(dp[i][sv-lv[i]]+lw[i]))

a = V
while a >= 0:
    if dp[-1][a] <= W:
        print(a)
        a = -1
    else:
        a -= 1

Solution (Python):
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())
dp = [[1000000001 for i in range(max(value)*n+1)]for j in range(n+1)]
dp[0][0] = 0

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

ans = 0
for i,j in enumerate(dp[n]):
    if j <= w:
        ans = max(ans,i)

print(ans)

Solution (Python):
import copy

N,W=map(int,input().split())
G=[0]   
for index1 in range(N):
    w,v=map(int,input().split())
    G.append((w,v))
sum_v=0
for index2 in range(1,N+1):
    sum_v+=G[index2][1]


DP=[]
inf=float('inf')
component=[0]+[inf]*sum_v
for index3 in range(N+1):
    DP.append(copy.copy(component))

for i in range(1,N+1):
    for j in range(1,sum_v+1):
        DP[i][j]=min(DP[i-1][j],DP[i-1][max(0,j-G[i][1])]+G[i][0])



ans=0
for k in range(1,sum_v+1):
    
    if DP[N][k]<=W:
        ans=max(ans,k)

print(ans)

Solution (Python):
import numpy as np
N, W = map(int, input().split())
dp = np.full(N * 10000 + 1, W + 1) 
dp[0] = 0
for n 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)))

Solution (Python):
N,W=map(int,input().split())
w=[0 for _ in range(110)]
v=[0 for _ in range(110)]
for i in range(1,N+1):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(110000)] for j in range(110)]
for i in range(1,110000):
    dp[0][i]=10**15

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

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

print(ans)

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



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

for i in range(n):
      w_=wv[i][0]
      v_=wv[i][1]
      
      dp[v_:]=np.minimum(dp[v_:], dp[:-v_]+w_)
print(np.where(dp<=w)[0][-1])

Solution (Python):
N, WW = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

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

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

ans = -1

for i in range(10 ** 5 + 1):
    if dp[N][i] <= WW:
        ans = i

print(ans)

Solution (Python):
import sys



input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 18


def main():
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

    """    
    dp[ i ] : 価値 i における重さの最小値
    　
    品物一つ w,v を見ていくたびに、
    dp[ i ] = (その品物を使うパターン) or (その品物を使わないパターン)
    = min( dp[i -v] + w , dp[ i ] ) 
    を更新していけばよい。
    """

    dp = [0] + [INF] * 10 ** 5

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

    

    ans = 0

    for i, j in enumerate(dp):
        if j <= W:
            ans = i
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n,W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
dp = [[10 ** 18] * (10 ** 5 + 1) for i in range(n+1)]
dp[0][0] = 0
for i,(w,v) in enumerate(wv):
  for j in range(1000 * i + 1):
    dp[i+1][j+v] = min(dp[i+1][j+v],dp[i][j]+w)
    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for k,w in enumerate(dp[n]):
  if w <= W:
    ans = k
print(ans)

Solution (Python):
import sys

MAX_VALUE = 10 ** 5 + 100

def input():
    return sys.stdin.readline().strip()

def main():
    N,W = map(int,input().split())
    goods = [list(map(int,input().split())) for _ in range(N)]
    
    dp = [[float('inf') for _ in range(MAX_VALUE+1)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(MAX_VALUE):
            if v >= goods[i][1]:
                dp[i+1][v] = min(dp[i][v-goods[i][1]]+goods[i][0],dp[i][v])
            else:
                dp[i+1][v] = dp[i][v]
    for v in range(MAX_VALUE):
        if dp[N][v] <= W:
            ans = v
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()

def main():

    
    import numpy as np

    n, capacity = map(int, input().split())
    value_max = 10 ** 5
    dp = np.full(value_max + 1, capacity + 1)
    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 <= capacity)[0][-1])


if __name__ == "__main__":
    main()

Solution (Python):

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N, W = imn()
weight = []
value = []
for _ in range(N):
    w,v = imn()
    weight.append(w)
    value.append(v)

max_v = 100*1000

dp = [[INF for _ in range(max_v+1)] for _ in range(N+1)]
dp[0][0] = 0

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

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

dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
  for v_sum in range(V+1):
    if v_sum >= v[i-1]:
      dp[i][v_sum] = min(dp[i-1][v_sum - v[i-1]] + w[i-1], dp[i-1][v_sum])
    else:
      dp[i][v_sum] = dp[i-1][v_sum]

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