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())
inf1 = 10**9+10
inf = 10**5+10
dp = [inf1]*inf

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

print(j)

Solution (Python):
import numpy as np
MaxW=int(1e5)
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[1e30 for i in range(MaxW+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[WV[i][1]:]=np.minimum(dp[WV[i][1]:],dp[:MaxW-WV[i][1]+1]+WV[i][0])
for i in reversed(range(MaxW+1)):
    if dp[i]<=W:
        print(i)
        break

Solution (Python):
a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0


for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])



inf=float('inf')
n_list = [[inf for i in range(max_value + 1)] for j in range(N)]


n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):
  
  n_list[i][wv_list[i][1]] = wv_list[i][0]
  for j in range(max_value):

    s = j + wv_list[i][1]
    
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])

    
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
  
for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,weight=map(int,input().split())
    WV=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[10**10]*(10**5+1) for _ in range(n+1)] 
    dp[0][0]=0
    for i in range(n):
        ni=i+1
        w,v=WV[ni-1]
        for j in range(10**5+1):
            if dp[i][j]+w<=weight and (j==0 or dp[i][j]!=10**10):
                dp[ni][j+v]=min(dp[ni][j+v],dp[i][j]+w)
            dp[ni][j]=min(dp[i][j],dp[ni][j])
    for i in range(10**5,-1,-1):
        if dp[-1][i]!=10**10:
            print(i)
            break

if __name__=='__main__':
    main()

Solution (Python):
n,w = map(int,input().split())
v = 10**5
dp = [[n*w+1]*(v+1) for i in range(n)]
ans = 0
for i in range(n):
    W,V = map(int,input().split())
    if i == 0:
        for j in range(v+1):
            if j <= V:
                dp[0][j] = W
    else:
        for j in range(v+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)
kouho = dp[-1]
for i in range(v+1):
    if kouho[i] <= w:
        ans = i
print(ans)

Solution (Python):
N,W=map(int,input().split(' '))
w,v=[0]*N,[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split(' '))
dp=[[0]+[W+1]*(sum(v)+1) for _ in range(N+1)]
for i in range(N):
    for nv in range(sum(v),0,-1):
        if nv<v[i]:
            dp[i+1][nv]=min(dp[i][nv],dp[i+1][nv+1])
        else:
            dp[i+1][nv]=min(dp[i][nv],dp[i][nv-v[i]]+w[i])

print(dp[N].index(W+1)-1)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
maxn=10000000000000000
we=[0]*n
val=[0]*n
su=0
for i in range(n):
    ww,v=map(int,input().split())
    we[i]=ww
    val[i]=v
    su+=v
dp=[maxn]*(su+1)
dp[0]=0
for i in range(n):
    for j in range(su-val[i],-1,-1):
        dp[j+val[i]]=min(dp[j+val[i]],we[i]+dp[j])
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=[0]*(N+1)
v=[0]*(N+1)
for i in range(N):
  w[i+1],v[i+1]=map(int,input().split())
res=0

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

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


for i in range(sum(v)+1):

  if dp[N][i]>W: continue
  res=i

print(res)

Solution (Python):
def main():
    import sys
    input = lambda: sys.stdin.buffer.readline().rstrip()
    n, w_max = map(int, input().split())
    import numpy as np

    v,w = [],[]
    for i in range(n):
        w_, v_ = map(int, input().split())
        v.append(v_)
        w.append(w_)
    dp = np.array([10**10]*(10**5+1),dtype=int)
    dp[0] = 0
    for i in range(n):
        dp[v[i]:] = np.minimum(dp[v[i]:], w[i]+dp[:-v[i]])
    ans = 0
    for i,w in enumerate(dp):
        if w<= w_max:
            ans = i
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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)

def chmin(a,b):
    if a >= b:
        return b
    else:
        return a
    
V = sum(value)
inf = float('inf')
dp = [[inf]*(V+1) for _ in range(N+1)]
dp[0][0] = 0

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

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

    
    inf = 10**18
    vmax = sum(list(zip(*wv))[1])
    dp = [[inf]*(vmax+1) for _ in range(n+1)]

    
    dp[0][0] = 0
    for i in range(n):
        w,v = wv[i]
        for j in range(vmax+1):
            
            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]

    res = 0
    for i in range(vmax+1):
        if wmax >= dp[-1][i]:
            res = max(res,i)
    print(res)

if __name__ == '__main__':
    main()

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

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

Solution (Python):
import  numpy as np

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

INF = 1e100

dp = [INF] * (10 ** 5 + 1)
dp = np.array(dp)

dp[0] = 0

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


for v,num in enumerate(dp):
    if num <= W:
        ans = v

print(ans)

Solution (Python):

import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div

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

Solution (Python):

from pprint import pprint

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

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

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

dp[0][0] = 0

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

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000) 

def main():
    input = sys.stdin.readline  
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

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

    max_value = 0
    for i, item in enumerate(item_list, 1):
        for v in range(100001):
            
            if dp[i-1][v] + item[0] <= W:
                dp[i][v+item[1]] = min(dp[i][v+item[1]], dp[i-1][v]+item[0])
                max_value = max(max_value, v+item[1])
            
            dp[i][v] = min(dp[i][v], dp[i-1][v])
    print(max_value)

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, stdout


def solve(mw, iw, iv):
    vs = sum(iv)
    A = [[float('inf') for i in range(vs+1)] for i in range(len(iv) + 1)]        
    A[0][0] = 0
    rs = 0
    for i in range(1, len(iv) + 1):
        rs += iv[i-1]
        for j in range(vs + 1):
            if i > rs: break
            if j < iv[i-1]: A[i][j] = A[i-1][j]
            else: A[i][j] = min(A[i-1][j], A[i-1][j-iv[i-1]] + iw[i-1])
    ans = 0
    for i in range(len(A[0])-1, -1, -1):
        if A[-1][i] != float('inf') and A[-1][i] <= mw:
            return i



























def main():
    iw, iv = [], []
    n, mw = [int(i) for i in stdin.readline().split()]
    for _ in range(n):
        w,v = [int(i) for i in stdin.readline().split()]
        iw.append(w)
        iv.append(v)
    print(solve(mw, iw, iv))

main()

Solution (Python):
INF = 1000000000000
n, W = map(int, input().split())
values = []
weights = []
total = 10
for _ in range(n):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)
    total += v
dp = [[INF for j in range(total)] for i 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(1,total):
        if v < values[i-1]:
            dp[i][v] = dp[i-1][v]
        else:
            dp[i][v] = min(dp[i-1][v],dp[i-1][v-values[i-1]]+weights[i-1]) 
res = 0
for i in range(total):
    if dp[n][i] <= W:
        res = i
print(res)

Solution (Python):
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,W=mp()
dp=[[10**10]*(n*1000+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    w,v=mp()
    for k in range(n*1000+1):
        dp[i][k]=dp[i-1][k]
        if k-v>=0:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k-v]+w)
ans=0
for i in range(n*1000+1):
    if dp[-1][i]<=W:
        ans=i
print(ans)

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, W = geta(int)
    INF = 10 << 60
    VMAX = 10**5
    cur = [INF] * (VMAX + 1)
    cur[0] = 0

    for i in range(N):
        w, v = geta(int)
        update = cur[:]

        for j in range(v, VMAX + 1):
            if cur[j - v] == INF: continue
            tmp = cur[j - v] + w
            if tmp < cur[j]: update[j] = tmp

        cur = update

    ans = 0
    for v in range(VMAX + 1):
        if cur[v] <= W: ans = v
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, W = map(int, input().split())
w_list = [0]
v_list = [0]
ans = 0

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

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

for i in range(1, N + 1):
    for j in range(100001):
        if j - v_list[i] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v_list[i]] + w_list[i])
        else:
            dp[i][j] = dp[i - 1][j]

for i in range(100001):
    if dp[N][i] != INF and dp[N][i] <= W:
        ans = max(ans, i)

print(ans)

Solution (Python):
n,W = map(int,input().split())
w = []
v = []
for _ in range(n):
    weight,value = map(int,input().split())
    w.append(weight)
    v.append(value)

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

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

ans = 0
for value in range(order):
    if dp[n][value] <= W:
        ans = max(ans,value)
print(ans)

Solution (Python):


import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * N + 1 
    
    dp = np.full(V, W+1)
    
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

    
    print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
N, W = map(int, input().split())
 
items = [tuple(map(int, input().split())) for _ in range(N)]
 
dp = np.full(N*1000 +1, W+1) 
dp[0] = 0
 
for i, (w, v) in enumerate(items):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
 
print(np.max(np.where(dp <= W)))

Solution (Python):
import numpy as np

if __name__=='__main__':
    N,Max_w = map(int,input().split())
    v,w = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        w.append(a)
        v.append(b)
    
    sum_v = sum(v)+1
    dp = [10**10 for _ in range(sum_v + 1)]
    dp[0] = 0
    dp = np.array(dp)
    
    for a,b in zip(w,v):
        x = dp[:-b]+a
        y = dp[b:]
        np.minimum(x,y,out=dp[b:])


    ans = np.where( dp <= Max_w )
    print(np.max(ans))

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

def main():
    n, w_max = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    inf = float('inf')
    dp = [[inf] * 100001 for _ in range(n + 1)]
    dp[0][0] = 0
    for i1 in range(1, n + 1):
        w, v = items[i1 - 1][0], items[i1 - 1][1]
        for col in range(1, 100001):
            if v >= col:
                tmp1 = w
            else:
                tmp1 = dp[i1 - 1][col - v] + w
            dp[i1][col] = min(dp[i1 - 1][col], tmp1)
    for i2 in range(100000, 0, -1):
        if dp[-1][i2] <= w_max:
            print(i2)
            sys.exit()

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N, W = map(int, input().split())

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

dp = np.full(N*1000 +1, W+1) 
dp[0] = 0

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

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

Solution (Python):
import numpy as np

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

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


dp = np.full(fill_value=10**15+1,shape=(n,10**5+1), dtype='int64')
w, v = map(int, input().split())
dp[0,v] = w
dp[0,0] = 0
for i in range(1,n):
    w, v = map(int, input().split())
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.fmin(dp[i-1, v:], dp[i-1,:-v]+w)
ans = 0
for j in range(100001):
    if dp[n-1][j] <= W:
        ans = max(ans, j)
print(ans)

Solution (Python):
import numpy as np

N , W = map(int,input().split())
dp = np.full(N * 1000 + 1,W + 1)
dp[0] = 0

for i 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=list(map(int,input().split()))
N=N_W[0]
W=N_W[1]
items=[]
for i in range(N):
	sets=list(map(int,input().split()))
	items.append(sets)
V=0
for i in range(N):
	V=max(V,items[i][1])

f_inf=float('inf')

knapsack=[[f_inf for v in range(N*V+1)] for i in range(N+1)]
knapsack[0][0]=0

for i in range(N):
	for v in range(0,N*V+1):
		if v-items[i][1]>=0:
			knapsack[i+1][v]=min(knapsack[i+1][v],knapsack[i][v],knapsack[i][v-items[i][1]]+items[i][0])
		else:
			knapsack[i+1][v]=min(knapsack[i+1][v],knapsack[i][v])
value=0
for i in range(len(knapsack)):
	for j in range(len(knapsack[0])):
		if knapsack[i][j]<=W:
			value = max(value,j)
print(value)

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

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









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

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]
        if val-v[i-1]<0:
            tmp2=w[i-1]
        else:
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]
        res=min(tmp1,tmp2)
        dp[i][val]=res

max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Solution (Python):
import numpy as np


def main():
    INF = 10**15
    V = 10**5 + 1
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.full((N, V + 1), INF)
    dp[0, :(items[0, 1] + 1)] = items[0, 0]
    dp[0, 0] = 0
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, value:] = np.fmin(
            dp[n, value:],
            weight + dp[n - 1, :(- value)]
        )
    ans = 0
    for v in range(V):
        if dp[N - 1, v] <= W:
            ans = v
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


N, W = (int(x) for x in input().split())
w = [0 for x in range(N)]
v = [0 for x in range(N)]
for i in range(N):
	w[i], v[i] = (int(x) for x in input().split())

V = sum(v)

inf = 10000000000000
dp = [[inf for x in range(V+1)] for y in range(N+1)]

dp[0][0] = 0

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









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

print(max_v)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    N, W = map(int, input().split())
    weight, value = [0] * N, [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())

    
    

    INF = 10**20  

    I = N
    
    J = sum(value)
    dp = [[INF]*(J+1) for _ in range(I+1)]
    
    dp[0][0] = 0
    
    for i in range(1,I+1):
        for j in range(J+1):
            if j-value[i-1] >= 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j-value[i-1]]+weight[i-1])
            dp[i][j] = min(dp[i][j], dp[i-1][j])
    ans = 0
    for j in range(J+1):
        if dp[I][j] <= W:
            ans = j
    print(ans)

resolve()

Solution (Python):
import numpy as np

N, W = map(int, input().split())
wv = np.array([[int(i) for i in input().split()] for j in range(N)])

max_v = 10**3*(N+1)
dp = np.full([N+1,max_v], np.inf)
dp[0,0] = 0
 
for i in range(N):
    
    dp[i+1,:wv[i,1]] = dp[i,:wv[i,1]]
    
    dp[i+1,wv[i,1]:] = np.minimum(dp[i,wv[i,1]:], dp[i,:max_v-wv[i,1]]+wv[i,0])

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

Solution (Python):


def main():
    N, W = map(int, input().split())
    weight = [0]
    value = [0]
    for i in range(N):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    V = sum(value)
    dp = [[float('inf')]*(V+1) for i in range(N+1)]
    for i in range(N):
        dp[i][0] = 0
    
    for i in range(1, N+1):
        for val in range(1, V+1):
            if val >= value[i]:
                dp[i][val] = min(dp[i-1][val], dp[i-1][val-value[i]]+weight[i])
            else:
                dp[i][val] = dp[i-1][val]
    ans = 0
    for v in range(V, -1, -1):
        if dp[N][v] <= W:
            ans = v
            break
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def chmin(dp, i, j, b):
    if dp[i][j] > b:
        dp[i][j] = b
        return True
    return False
def main():
    N, W = map(int, input().split())
    goods = []
    INF = 10 ** 9 + 1
    for _ in range(N):
        goods.append(list(map(int, input().split())))
    dp = [[INF for _ in range(100001)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        w, v = goods[i][0], goods[i][1]
        for j in range(100001):
            chmin(dp, i+1, j, dp[i][j])
            if j-v >= 0:chmin(dp, i+1, j, dp[i][j-v]+w)
    ans = 0
    for i in range(100001):
        if dp[N][i] <= W:ans = i
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):

N, W = [int(_n) for _n in input().split()]
weights = []
values = []
for i in range(N):
    w,v = [int(_n) for _n in input().split()]
    weights.append(w)
    values.append(v)
V = max(values) * N+1
INF = 10**12
dp = [[INF]*(V+1) for _ in range(N)]

for v in range(V+1):
    dp[0][v] = INF if v > values[0] else weights[0]
dp[0][0] = 0
for i in range(1,N):
    for v in range(V+1):
        dp[i][v] = min(dp[i-1][v], dp[i-1][max(0,v-values[i])] + weights[i])
ok = 0
ng = V
while ng - ok > 1:
    mid = (ng+ok)//2
    if dp[N-1][mid] > W:
        ng = mid
    else:
        ok = mid
print(ok)

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

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

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

ans = 0
for i in range(1, N + 1):
    for j in range(v_total + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

        if i == N and dp[i][j] <= W:
            ans = max(ans, j)

print(ans)

Solution (Python):
import sys


def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

N, W = IL()
v_list = [0] * N
w_list = [0] * N

for i in range(N):
	w_list[i], v_list[i] = IL()

v_max = 100100
dp = [[sys.maxsize] * (v_max+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
	for j in range(v_max+1):
		if j >= v_list[i]:
			dp[i+1][j] = min(dp[i][j-v_list[i]] + w_list[i], dp[i][j])
		else:
			dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

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)
V=sum(v)

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

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

Solution (Python):
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    w, v = [0 for i in range(N)], [0 for i in range(N)]
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    ans = solve(N, W, w, v)
    print(ans)


def solve(N, W, w, v):
    INF = W + 1
    vmax = 10 ** 3 * 10 ** 2
    dp = [[INF for i in range(vmax + 1)] for j in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(vmax + 1):
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
    for v in range(vmax, -1, -1):
        if dp[N][v] <= W:
            ans = v
            break
    return ans


if __name__ == '__main__':
    main()

Solution (Python):
N,W=map(int,input().split())
waight=[0]
value=[0]
for _ in range(N):
    a,b=map(int,input().split())
    waight.append(a)
    value.append(b)
SUM_v=sum(value)
dp=[[float("inf")]*(SUM_v+1) for _ in range(N+1)]
dp[0][0]=0
ans=0
for i in range(N):
    for sum_v in range(SUM_v+1):
        dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][max(0,sum_v-value[i+1])]+waight[i+1])
        if dp[i+1][sum_v]<=W:
            ans=max(ans,sum_v)
print(ans)

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

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

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

    dp[0][0] = 0
    
    for i in range(N):
        
        for j in range(V + 1):
            w, v = WV[i]

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

    
    max_ind = 0
    for j in range(V+1):
        if dp[-1][j] <= W:
            max_ind = j
    print(max_ind)


if __name__ == "__main__":
    main()

Solution (Python):
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)

max_sumv = sum(V) 

dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0

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

Solution (Python):
import numpy as np

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

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

for i, (w, v) in enumerate(items):
  tmp = dp[:-v] + w
  dp[v:] = np.minimum(dp[v:], tmp)
print(np.max(np.where(dp <= W)))

Solution (Python):
import numpy as np
n,w,*wv=map(int,open(0).read().split())
wei=wv[0::2]
val=wv[1::2]
sack=np.array([float('inf') for i in range(sum(val)+1)])
sack[0]=0
for i in range(n):
  sack[val[i]:]=np.minimum(sack[val[i]:],sack[:-val[i]]+wei[i])
print(np.where(sack<=w)[0][-1])

Solution (Python):

import sys



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


dp = [ [sys.maxsize] * (N * 1000) for _ in range(N) ]
for i in range(N):
    for j in range(N * 1000):
        w = l[i][0]
        v = l[i][1]
        if(j == 0):
            dp[i][j] = 0
        elif(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)

    



cnt = 0
i = 0
while cnt <= W:
    cnt = dp[-1][i]
    i += 1
    if(i == N*1000):
        i += 2
        break
print(i-2)

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

dp = [[float('inf')] * (10 ** 5 + 5) for _ in range(N + 5)]
dp[0][0] = 0
for i in range(N):
    for j in range(10 ** 5 + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if 0 <= j - vt[i]:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - vt[i]] + wt[i])

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

Solution (Python):
import numpy as np
N, W = map(int, input().split())
dp = np.full(N*10**3+1, W+1)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
print(np.where(dp<=W)[0][-1])

Solution (Python):
N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9)*(N+1)
dp = [[INF] * (max_v * N+1) for _ in range(N+1)]
max_sum = max_v*N
dp[0][0] = 0

for i in range(N):
    for j in range(max_v * N+1):
        if j+v[i] > max_sum:
            break
        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 i in range(max_v * N + 1):
    if dp[N][i] <= W:
        ans = max(ans, i)
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())
V=sum(v)

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

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

Solution (Python):
import numpy as np
N,W = map(int,input().split())
s=np.full(N*1000+1,W+1)
s[0]=0
for i in range(N):
  w,v =  map(int,input().split())
  s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=W)))

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)
INF=float("inf")
max_v=max(v)*N +1
dp=[[INF for i in range(max_v)] for j in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(max_v):
        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(max_v):
    if dp[N][i] <=W:
        ans=i
print(ans)

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)
INF=float("inf")
max_v=10**5+1
dp=[[INF for i in range(max_v)] for j in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(max_v):
        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(max_v):
    if dp[N][i] <=W:
        ans=i
print(ans)