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):
def main():
    N,W=map(int,input().split())
    w=[0]*(N+1)
    v=[0]*(N+1)
    for i in range(1,N+1):
        a,b=map(int,input().split())
        w[i]=a
        v[i]=b
    v_sum=sum(v)
    inf=10**12
    dp=[[inf]*(v_sum+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(1,v_sum+1):
            dp[i][j]=min(dp[i-1][j],dp[i-1][max(0,j-v[i])]+w[i])

    for j in range(v_sum+1):
        if dp[N][j]>W:
            result=j-1
            break
        if j==v_sum:
            result=j
    print(result)

if __name__=="__main__":
    main()

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

    Wi, Vi = [], []
    for _ in range(N):
        w, v = tuple(map(int, input().split()))
        Wi.append(w)
        Vi.append(v)

    
    

    return N, W, Wi, Vi


def solve(N, W, Wi, Vi):
    DP = [[float("inf")] * (sum(Vi) + 1) for _ in range(N + 1)]

    DP[0][0] = 0

    for i in range(N):
        value = Vi[i]
        w_max = sum(Vi) + 1
        for v in range(w_max):
            remain = v - value
            if 0 <= remain:
                
                DP[i + 1][v] = min(DP[i + 1][v], DP[i][remain] + Wi[i])
            
            DP[i + 1][v] = min(DP[i + 1][v], DP[i][v])

    
    ans = 0
    for line in DP:
        for v, e in enumerate(line):
            if not e == float("inf") and e <= W:
                
                ans = max(ans, v)

    

    return ans


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Solution (Python):
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(2001 * N + 10)] for _ in range(N + 2) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 1000):
      	
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)

Solution (Python):
n, w = map(int,input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[float("inf")] * (10**5+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(1, 10**5+1):
        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):
n, w = map(int, input().split())

import numpy as np 

dp = np.full(1000*n+1, w+1, dtype=int)

dp[0] = 0

for i in range(n):
    weight, value = map(int, input().split())
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight)

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

Solution (Python):
N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
sumv=0
for i in range(N):
    weight[i],value[i]=map(int,input().split())
    sumv+=value[i]
dp=[[1000000000000]*(sumv+1) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(sumv+1):
        if(value[i]<=j):
            dp[i+1][j]=min(dp[i][j-value[i]]+weight[i],dp[i][j])
        else:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
res=0
for i in range(sumv+1):
    if(dp[N][i]<=W):
        res=max(res,i)
print(res)

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**9 for i in range(N*max(v)+1)] for j in range(N+1)]
dp[0][0]=0
for i in range(N):
    for sumv in range(N*max(v)+1):
        if (sumv-v[i])>=0:
            m=dp[i][sumv-v[i]]+w[i]
            dp[i+1][sumv]=min(dp[i+1][sumv],m)
        dp[i+1][sumv]=min(dp[i+1][sumv],dp[i][sumv])
ans=10**9
for i in range(N*max(v)+1):
    if (dp[-1][i]<=W):
        ans=i
print(ans)

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

def resolve():
    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 = [[sum(w)]*(sum_v+1) for i in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for j in range(sum_v+1):
            if j-v[i-1] >= 0:
                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]

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

if __name__ == '__main__':
    resolve()

Solution (Python):
n ,c = map(int,input().split())
wt =[]; val=[]
wt.append(0);val.append(0)

for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  


max_val = sum(val)
INF = 10 **10
dp = [[INF for i in range(max_val+1)]for j in range(n+1)]

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

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

res = 0

for i in range(max_val+1):
  if dp[n][i] <= c:
    res = i
    
print(res)

Solution (Python):
n ,c = map(int,input().split())
wt =[]; val=[]
wt.append(0);val.append(0)
for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  

INF = 10 **10
max_val = sum(val)
dp = [[INF for i in range(max_val+1)]for j in range(n+1)]

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

for i in range(1,n+1):
  wi = wt[i];vi = val[i]
  for V in range(1,max_val+1):
    if vi<=V:
      dp[i][V] = min(wi+dp[i-1][V-vi] , dp[i-1][V])
    else:
      dp[i][V] = dp[i-1][V]
      
res = 0
for i in range(max_val+1):
  if dp[n][i] <= c:
    res = i
    
print(res)

Solution (Python):
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)

f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)

Solution (Python):
n, W = list(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 = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
dp[0][0] = 0

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

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


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)

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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

N, W = input_nums()

weights = []
values = []

for i in range(N):
    w, v = input_nums()
    weights.append(w)
    values.append(v)

MAXV = 10**5+100
INF = 10**18

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

dp[0][0] = 0
weights.append(0)
values.append(0)

for i in range(N):
    for sum_v in range(MAXV):
        if sum_v - values[i] >= 0:
            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])

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

Solution (Python):

n,w=map(int,input().split())
data=[]
for i in range(n):
    u,v=map(int,input().split())
    data.append((u,v))
inf=10**20
pack_min=[[10**20 for i in range(10**5+1)]for _ in range(101)]

for i in range(101):
    pack_min[i][0]=0
    
for i in range(n):
    a,b=data[i][0],data[i][1]
    
    for j in range(10**5+1):
        if j>=b:
            pack_min[i+1][j]=min(pack_min[i][j],pack_min[i][j-b]+a)
        else:
            pack_min[i+1][j]=pack_min[i][j]

        
ans=0

for i in range(10**5+1):
    if pack_min[n][i]<=w:
        try:
            ans=i
        except:
            break
print(ans)

Solution (Python):
def main():
  N,W=map(int,input().split())
  Wlist=[]
  Vlist=[]
  for i in range(N):
    w,v=map(int,input().split())
    Wlist+=[w]
    Vlist+=[v]
  Vmax=max(Vlist)
  V=Vmax*N
  dp=[[float('inf') for p in range(V+1)] for i in range(N)]
  for i in range(V+1):
    if i<=Vlist[0]:
      dp[0][i]=Wlist[0]
  dp[0][0]=0
  for i in range(1,N):
    vi=Vlist[i]
    wi=Wlist[i]
    for j in range(V+1):
      if j-vi>=0:
        dp[i][j]=min(dp[i-1][j-vi]+wi,dp[i-1][j])
      else:
        dp[i][j]=min(dp[i-1][j],dp[i][j])
  dpn=dp[N-1]
  ans=0
  for i in range(V+1):
    if dpn[i]<=W:
      ans=i
  print(ans)
if __name__ == '__main__':
  main()

Solution (Python):
def main():
    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 = [[float('inf')] * (max_v * N + 5) for _ in range(N + 5)]

    dp[0][0] = 0

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

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

    print(ans)

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 collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().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

N,W = imn()
wv = [iln() for _ in range(N)]
maxv = 100 * 1000 + 1

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

dp[0][0] = 0

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

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

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


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


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

print(ans)

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

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

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

print(ret)

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

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

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

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

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

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

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

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

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

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

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

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

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

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,w = get_nums_l()
ppp = list(map(lambda s: tuple(map(int,s.strip().split())), sys.stdin.readlines()))


dp = [9999999999999999999] * (n*1000+1)
dp[0] = 0

for p in ppp:
    we = p[0]
    va = p[1]
    for i in reversed(range(len(dp))):
        if i+va >= len(dp):
            continue
        ne = i+va
        dp[ne] = min(dp[ne], dp[i]+we)



for i,we in reversed(list(enumerate(dp))):
    if we <= w:
        print(i)
        exit()

Solution (Python):
def main():

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

    INF = 10 ** 20
    dp = [INF] * (n * 100001)
    dp[0] = 0

    max_vi = 0
    for _ in range(n):
        wi, vi = map(int, input().split())
        max_vi += vi

        for vj in range(max_vi + 1, vi - 1, -1):
            nw = dp[vj - vi] + wi
            if dp[vj] > nw:
                dp[vj] = nw

    for i in range(max_vi, -1, -1):
        if dp[i] <= w:
            print(i)
            return

main()

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)


dp = [[float('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):
        if j - v[i] >= 0:
            if dp[i][j - v[i]] + w[i] < dp[i][j]:
                dp[i + 1][j] = dp[i][j - v[i]] + w[i]
            else:
                dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = dp[i][j]

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

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

from collections import defaultdict

dp = defaultdict(lambda : 10**100)
dp[0] = 0
for w, v in WV:
  ndp = defaultdict(lambda : 10**100)
  for k in dp:
    ndp[k] = min(dp[k], ndp[k])
    if dp[k] + w <= W:
   	  ndp[k+v] = min(dp[k] + w, ndp[k+v])
  dp = ndp
print(max(dp.keys()))

Solution (Python):
def main():
    
    N,W = map(int,input().split())
    dp = [W+1]*(N*10**3+1)

    
    dp[0] = 0

    
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(N*10**3, v-1, -1):
            tmp = dp[i-v] + w
            if dp[i] > tmp:
                dp[i] = tmp
        

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

if __name__ == '__main__':
    main()

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

import numpy as np

INF = 10 ** 18

N, W = map(int, input().split())
lst = np.array([0] + [INF] * (10 ** 5 + 9), dtype = np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    lst[v:] = np.minimum(lst[v:], lst[:10 ** 5 + 10 -v] + w)
    lst[1:v] = np.minimum(lst[1:v], w)


for i in range(10 ** 5 + 9, -1, -1):
    if lst[i] <= W:
        print (i)
        exit()

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

INF = 10 ** 18

N, W = map(int, input().split())
lst = [INF] * (10 **5 + 10)
lst[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(10 ** 5 + 9, v - 1, -1):
        lst[i] = min(lst[i], lst[i - v] + w)
    for i in range(v - 1, -1, -1):
        lst[i] = min(lst[i], lst[i + 1])

for i in range(10 ** 5 + 9, -1, -1):
    if lst[i] <= W:
        print (i)
        exit()

Solution (Python):
import sys
import math
from collections import deque
import copy
input = sys.stdin.readline
INF = 10**9+7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

Solution (Python):
import sys
import math
from collections import deque
import copy
INF = float("inf")
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

Solution (Python):
import sys
import math
from collections import deque
import copy
input = sys.stdin.readline
INF = float("inf")
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

Solution (Python):
import sys
import math
from collections import deque
import copy

INF = 10 ** 9 + 7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

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


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

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

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


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


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

print(answer)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,w=map(int,input().split())
WV=[tuple(map(int,input().split())) for i in range(n)]
dp=[inf]*(10**5+1); dp[0]=0
for i in range(n):
  wi,vi = WV[i]
  for di in range(10**5,-1,-1):
    if not (0<=di-vi<10**5+1): continue
    
    dp[di]=min(dp[di],dp[di-vi]+wi)
for i,di in enumerate(dp):
  if di <= w:
    ans = max(ans,i)

print(ans)

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

Solution (Python):
N,W = map(int,input().split())
INF = 10**9+7
NV = (10**3)*N
dp = [[0]+[INF for j in range(NV)] for i in range(N+1)]

for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(NV+1):
        if j < v:
            dp[i][j] = min(dp[i-1][j], w)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)

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

Solution (Python):
import sys

N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)

INF = sys.maxsize
DP = [[INF for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = min(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = min(DP[i][v], weight)

res = 0
for v, w in enumerate(DP[M]):
    if w <= W:
        res = max(res, v)

print(res + 1)

Solution (Python):
import sys

N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)

INF = sys.maxsize
DP = [[INF for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = min(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = min(DP[i][v], weight)

res = 0
for v, w in enumerate(DP[M]):
    if w <= W:
        res = max(res, v)

print(res + 1)

Solution (Python):

N,W=map(int,input().split())
w,v=[],[]
inf=10**10
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

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

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

Solution (Python):
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+1):
        if j - V[i] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): 
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    MV = max(v)*N+1
    inf = float("inf")
    dp = [[inf]*MV for i in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(MV):
            if v[i] <= j:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:
                dp[i+1][j] = dp[i][j]

    dp = dp[N]
    for i in reversed(range(MV)):
        if dp[i] <= W:
            print(i)
            exit()
if __name__ == "__main__":
    main()

Solution (Python):


N, W = map(int, input().split())
knapsack_list = []
value_max = 0
max_cost = 0
for i in range(N):
    knap =  list(map(int, input().split()))
    knapsack_list.append(knap)
    value_max = value_max + knap[1]

cost_list = [[10**12]*(value_max+1) for _ in range(N+1)]

cost_list[0][0] = 0
for i in range(N):
    cost_list[i+1][0] = 0
    weight = knapsack_list[i][0]
    value = knapsack_list[i][1]
    for j in range(value_max+1):
        if j<value:
            cost_list[i+1][j] = cost_list[i][j] 
            continue
        new_cost = cost_list[i][j-value] + weight
        new_cost = min(cost_list[i][j], new_cost)
        cost_list[i+1][j] = new_cost 

for i in range(value_max+1):
    weight = cost_list[N][i]
    if weight<=W:
        max_cost = i

print(max_cost)

Solution (Python):


def resolve():
    N, W = map(int, input().split())
    w_l = []
    v_l = []
    for _ in range(N):
        w, v = map(int, input().split())
        w_l.append(w)
        v_l.append(v)

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

    for i in range(N):
        for j in range(max_v):
            
            w = w_l[i]
            v = v_l[i]
            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 j in range(max_v):
        if dp[N][j] <= W:
            res = j

    print(res)

if __name__ == "__main__":
    resolve()

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    maxv=sum(v)+1
    dp=[[2**60]*maxv for _ in range(N+1)]
    dp[0][0]=0
    for i in range(N):
        for j in range(maxv):
            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 j in range(maxv):
        if W >= dp[N][j]:
            ans=j
    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())

import numpy as np
dp = np.full(1000*N+1, W+1, dtype=int)
dp[0]=0

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

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

Solution (Python):
N, W = map(int, input().split())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
MAX_N, MAX_V = 110, 100100
dp = [[10e+09 for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0
for i in range(N):
  for v in range(MAX_V):  
    if v-wv[2*i+1] >= 0:
      dp[i+1][v] = min(dp[i+1][v], dp[i][v-wv[2*i+1]]+wv[2*i])
    dp[i+1][v] = min(dp[i+1][v], dp[i][v])
for v in range(MAX_V):
  if dp[N][v] <= W: res = v
print(res)

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

import numpy as np
dp = np.full(N*1000+1, W+1, dtype=int)
dp[0] = 0

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

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