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())
wt,values=[],[]
for _ in range(n):
    w,val=map(int,input().split())
    wt.append(w)
    values.append(val)



max_profit=max(values)*n 
dp=[float('inf')]*(max_profit+1)
dp[0]=0

for i in range(n):
    for j in range(max_profit,values[i]-1,-1):
        dp[j]=min(dp[j],wt[i]+dp[j-values[i]])
    
ans=0

for i in range(1,max_profit+1):
    if dp[i]<=W:
        ans=i
print(ans)

Solution (Python):
import sys
 
import numba as nb
import numpy as np
 
input = sys.stdin.readline
 
 
@nb.njit("i8(i8,i8,i8[:],i8[:])")
def solve(N, W, w, v):
    dp = np.full(shape=(N + 1, np.sum(v) + 1), fill_value=(N * W), dtype=np.int64)
    dp[:, 0] = 0
    for i in range(N):
        np.minimum(w[i], dp[i][:v[i]], dp[i + 1][:v[i]])
        np.minimum(w[i] + dp[i][: - v[i]], dp[i][v[i]:], dp[i + 1][v[i]:])
    return np.where(dp[-1] <= W)[0][-1]
 
 
def main():
    N, W = map(int, input().split())
 
    w = np.empty(shape=N, dtype=np.int64)
    v = np.empty(shape=N, dtype=np.int64)
    for i in range(N):
        w[i], v[i] = map(int, input().split())
 
    ans = solve(N, W, w, v)
    print(ans)
 
 
if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numpy as np

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    wv = [0] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    INF = 10 ** 10
    V = sum(v for _, v in wv)
    dp = np.full(shape=(V + 1), fill_value=INF, dtype=np.int64)
    dp[0] = 0
    for w, v in wv:
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

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


if __name__ == "__main__":
    main()

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

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

for n_i in range(1, n+1):
  for v_i in range(n*10**3+1):
    if v_i-WV[n_i-1][1]>=0:
      dp[n_i][v_i] = min(dp[n_i-1][v_i], dp[n_i-1][v_i-WV[n_i-1][1]]+WV[n_i-1][0])
    else:
      dp[n_i][v_i] = min(dp[n_i][v_i], dp[n_i-1][v_i])
      
ans = 0
for v_i in range(n*10**3+1):
  if dp[n][v_i]<=w:
    ans = v_i
  
print(ans)

Solution (Python):
n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[float('inf') for _ in range(10**5+10)]for _ in range(n+1)]

dp[0][0]=0
for i in range(n):
    w,v=l[i]
    for j in range(10**5+10):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        if j+v<10**5+10:
            dp[i+1][j+v]=min(dp[i+1][j+v],dp[i][j]+w)
    for j in range(10**5+9):
        dp[i+1][-2-j]=min(dp[i+1][-2-j],dp[i+1][-1-j])
for i in range(10**5+10):
    if dp[-1][i]>mw:
        print(i-1)
        break

Solution (Python):


INF = float('inf')


def tc():
    n, cap = map(int, input().split())
    weights, values = [], []
    for _ in range(n):
        w, v = map(int, input().split())
        weights.append(w)
        values.append(v)
    
    
    
    value_sum = sum(values)
    dp = [INF] * (value_sum + 1)
    dp[0] = 0

    for i in range(n):
        w, v = weights[i], values[i]
        
        
        for prev_v in reversed(range(value_sum - v + 1)):
            dp[prev_v + v] = min(dp[prev_v + v], dp[prev_v] + w)

    ans = 0
    for v, w in enumerate(dp):
        if w <= cap:
            ans = max(ans, v)

    print(ans)


tc()

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








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


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

ans=V
while dp[N-1][ans]>W:
    ans-=1
print(ans)

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**18


def main():

    N, W = in_nn()
    w, v = [], []
    for i in range(N):
        a, b = in_nn()
        w.append(a)
        v.append(b)

    V = 10**5 + 1
    dp = [INF] * (V + 1)
    dp[0] = 0

    for i in range(N):
        next_dp = copy(dp)
        for j in range(V):
            if j + v[i] <= V:
                next_dp[j + v[i]] = min(next_dp[j + v[i]], dp[j] + w[i])
            else:
                break
        dp = next_dp

    ans = 0
    for i in range(V):
        if dp[i] <= W:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

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

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

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

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,w=MI()
WV=[LI() for i in range(n)]
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-WV[i][1]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j],dp[i][j-WV[i][1]]+WV[i][0])
        else:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
for i in range(10**5+1):
    j=10**5-i
    if dp[-1][j]<=w:
        print(j)
        sys.exit()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, w = LI()
wv = LIR(n)
vv = 10 ** 5
dp = [INF] * (vv + 1)
dp[0] = 0
for i in range(n):
    wi, vi = wv[i]
    for j in range(vv, vi - 1, -1):
        dp[j] = min(dp[j], dp[j - vi] + wi)

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

Solution (Python):
INF = 10**15
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[INF]*100100 for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  for j in range(100100):
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    if 0 <= j-value[i]:
      dp[i][j] = min(dp[i][j], dp[i-1][j-value[i]] + weight[i])

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

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

memo = [[10**9] * (sum_v + 1) for _ in range(n+1)]
memo[0][0] = 0

for i in range(n):
  for v_i in range(sum_v + 1):
    memo[i+1][v_i] = min(memo[i+1][v_i], memo[i][v_i])
    if v_i - V[i] >= 0:
      memo[i+1][v_i] = min(memo[i+1][v_i], memo[i][v_i-V[i]] + W[i])

ans = 0
for i in range(sum_v + 1):
  if memo[-1][i] <= w:
    ans = i
print(ans)

Solution (Python):
n,w_limit = map(int,input().split())

item_ls = [[0,0]]
total_value = 0
for i in range(n):
    cost, value = map(int,input().split())
    item_ls.append([cost, value])
    total_value += value


dp = [[float('inf')] * (total_value+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    item_cost, item_value = item_ls[i]
    for sum_value in range(0,total_value+1):
        if sum_value-item_value >= 0:
            dp[i][sum_value] = min(dp[i][sum_value], dp[i-1][sum_value-item_value] + item_cost)
        dp[i][sum_value] = min(dp[i][sum_value], dp[i-1][sum_value])

ans = 0
for value, cost in enumerate(dp[n]):
    if cost <= w_limit:
        ans = max(ans, value)
print(ans)

Solution (Python):
n, w = map(int, input().split())

weights = [0]*n
values = [0]*n

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

v = sum(values)

dp = [[float('inf') for _ in range(v+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+1):
        if values[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(weights[i-1] + dp[i-1][j-values[i-1]], dp[i-1][j])

for j in range(v,-1,-1):
    if dp[-1][j] <= w:
        print(j)
        break

Solution (Python):
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate

input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]

MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
    
def knapsack(wts,P,N,W):
    if N==0 or W == 0:
        return 0
    dp = list2d(100,100001,1e10) 
    dp[0][0] = 0
    dp[0][P[0]] = wts[0]
    
    for i in range(1,N):
        dp[i][0] = 0
        for j in range(1,100000+1):
            dp[i][j] = dp[i-1][j] 
            if P[i] <= j:
                dp[i][j] = min(wts[i] + dp[i-1][j - P[i]] , dp[i][j])
            
    
    for val in range(100000,-1,-1):
        if dp[N-1][val] <= W:
            return val 
    

N,W = ilele()
P = []
A = []
for i in range(N):
    a,b =ilele()
    A.append(a)
    P.append(b)
print(knapsack(A,P,N,W))

Solution (Python):
import numpy as np
 
N, W = map(int, input().split())
dp = np.ones(int(1e5+1)) * np.inf
dp[0] = 0
total = 0
for i in range(N):
    w, v = map(int, input().split())
    dp[v:total+v+1] = np.minimum(dp[v:total+v+1], dp[:total+1] + w)
    total += v
 
print(int(np.where(dp<=W)[0][-1]))

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq

N, W = list(map(int, input().split()))
INF = 10**10

dp = [[INF]*(100005) for i in range(N+5)]

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

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

for i in range(1000001):
    if dp[N][i] > W:
        print(i-1)
        exit()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N,W = map(int, input().split())
v_max = (10**3)*N
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,v-1,-1):
		b = w + dp[j-v]		
		if b<dp[j]:
			dp[j] = b

ans = None
for i in range(v_max+1):
	z = dp[i]
	if z<=W:
		ans = i

print(ans)

Solution (Python):
INF_V = 1000*100
N, W = list(map(int, input().split()))
dp = [[W+1]*(INF_V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(INF_V-1000+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])
print([i for (i, w) in enumerate(dp[N]) if w <= W][-1])

Solution (Python):
N, W = list(map(int, input().split()))
dp = [[W+1]*(100000+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(100000+1):
        if j+v <= 100000:
            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])
i = -1
while True:
    if dp[N][i] <= W:
        print(100000+1+i)
        break
    else:
        i -= 1

Solution (Python):




from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, w = iia()
wt, val = [], []
for i in range(n):
    a, b = iia()
    wt.append(a)
    val.append(b)
tot = sum(val)
dp = [[float('inf') for i in range(tot + 1)] for j in range(n + 1)]

dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(tot + 1):
        if j < val[i - 1]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], wt[i - 1] + dp[i - 1][j - val[i - 1]])

ans = 0
for i in range(1, tot + 1):
    if dp[-1][i] <= w:
        ans = max(ans, i)
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,W = IL()
data = ILL(N)

dp = [[INF for v in range(110000)] for i in range(N+1)]
for i in range(N+1):
  dp[i][0] = 0
for i in range(N):
  w0,v0 = data[i]
  for v in range(110000):
    dp[i+1][v] = min(dp[i+1][v],dp[i][v])
    if v+v0 < 110000:
      dp[i+1][v+v0] = min(dp[i][v+v0],dp[i][v]+w0)

v = 110000-1
while dp[-1][v] > W:
  v -= 1
print(v)

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




dp = [[INF]*100100 for _ in range(110)]


dp[0][0] = 0


for i in range(N):
    weight, value = map(int, input().split())
    for sum_v in range(10**5+1):

        
        if sum_v - value >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - value] + weight)

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


res = 0
for sum_v in range(10**5+1):
    if dp[N][sum_v] <= W:
        res = sum_v
print(res)

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




dp = [[10**12-1]*100010 for i in range(N)]

dp[0][WV[0][1]] = WV[0][0]
res = WV[0][1]

for i in range(1,N):
  w = WV[i][0]
  v = WV[i][1]
  dp[i][WV[i][1]] = WV[i][0]
  res = max(res,WV[i][1])
  for j in range(1,100010):
    if j>=v:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-v]+w,dp[i][j])
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j])
    if 0 < dp[i][j] <= W:
      res = max(res,j)
    
print(res)

Solution (Python):
"""
    Satwik_Tiwari ;) .
    24th july , 2020  - Friday
"""



from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  
from itertools import combinations as comb 
from itertools import permutations as permutate
from bisect import bisect_left as bl


from bisect import bisect_right as br
from bisect import bisect





BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)






mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True




def solve():
    n,W = sep()
    w = [0]
    v = [0]
    for i in range(n):
        a,b = sep()
        w.append(a)
        v.append(b)
    s = sum(v)
    dp = [[10**10]*((n+1)) for i in range(s+1)]

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

    for i in range(1,s+1):
        for j in range(1,n+1):
            if(v[j] <= i):
                dp[i][j] = min(dp[i][j-1],dp[i-v[j]][j-1]+w[j])
            else:
                dp[i][j] = dp[i][j-1]

    
    
    ans = 0
    for i in range(1,s+1):
        for j in range(1,n+1):
            if(dp[i][j] <= W):
                ans = max(ans,i)

    print(ans)


testcase(1)

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
def pprint(M):
	for row in M:
		print(row)
	print("~~~")


def main():
	n, W = rli()
	weights, vals = [], []
	for _ in range(n):
		w, v = rli()
		weights.append(w)
		vals.append(v)
	maxval = 10**5 + 100
	dp = [INF for _ in range(maxval+1)]
	dp[0] = 0
	for w, v in zip(weights, vals):
		for i in range(maxval, -1, -1):
			if i - v < 0: continue
			dp[i] = min(dp[i], dp[i-v] + w)
	for i in range(maxval, -1, -1):
		if dp[i] <= W:
			print(i)
			break
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
def solve():
  N, W = map(int, input().split())
  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(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)
  for i in range(10**5,-1,-1):
    if dp[-1][i]<=W:
      ans = i
      break
  return ans
print(solve())

Solution (Python):





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



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

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

dp[0][0] = 0



for i, (w, v) in enumerate(x, 1):
    for j in range(10**5 + 1):
        dp[i][j] = dp[i - 1][j]
        if j != 0 and v <= j:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - v] + w)

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

Solution (Python):
import sys


input = sys.stdin.readline


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

MAX_V = (10**3) * N +1

f_inf = float('inf')

def knapsack(n, w):
    
    dp = [f_inf] * MAX_V
    
    dp[0] = 0
    sum_v = 0
    
    
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(MAX_V, v-1, -1):
            new_weight = dp[j - v] + w
            if new_weight > W:
                continue
            if dp[j] > new_weight:
                dp[j] = new_weight

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

knapsack(N, W)

Solution (Python):
x,size=map(int,input().split())
weight=[]
value=[]
weight.append(0)
value.append(0)
for i in range(x):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
max_value=sum(value)
dp=[[float('inf') for i in range(max_value+1)] for j in range(x+1)]
for i in range(x+1):
    dp[i][0]=0
for i in range(1,x+1):
    w=weight[i]
    v=value[i]
    for knap_v in range(1,max_value+1):
        if v<=knap_v:
            dp[i][knap_v]=min(dp[i-1][knap_v],w+dp[i-1][knap_v-v])
        else:
            dp[i][knap_v]=dp[i-1][knap_v]
ans=0

for i in range(max_value+1):
    if dp[x][i]<=size:
        ans=i
print(ans)

Solution (Python):
n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[10**11+100 for _ in range(10**5+15)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(10**5+15):
      dp[i+1][j]=min(dp[i][j],dp[i][max(j-a[i][1],0)]+a[i][0])
an=0


for j in range(10**5+15):
  if dp[n][j]<=w and j>an:
    an=j
print(an)

Solution (Python):

N,W=list(map(int,input().split()))
weights=[]
value=[]
for i in range(N):
    w,v=list(map(int,input().split()))
    weights.append(w)
    value.append(v)
t=sum(value)
maxa=10**18
dp=[maxa for i in range(t+1)]
dp[0]=0
for i in range(N):
    for val in range(t-value[i],-1,-1):
       dp[val+value[i]] = min(dp[val+value[i]],dp[val]+weights[i])
ans=0
for i in range(t+1):
    if(dp[i]<=W):
        ans=max(ans,i)

print(ans)

Solution (Python):

import copy
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Value = sum(map(lambda x:x[1],Goods_List))
dp = [[0] * (Sum_Value + 1) for i in range(N)]

for i in range(N):
    if i == 0:
        dp[i][Goods_List[i][1]] = Goods_List[i][0]
    else:
        dp[i] = copy.copy(dp[i-1])
        Valid_List = [k for k, x in enumerate(dp[i]) if x != 0]
        Valid_List.append(0)
        for j in Valid_List:
            if dp[i][j + Goods_List[i][1]] == 0:
                dp[i][j + Goods_List[i][1]] = dp[i-1][j] + Goods_List[i][0]
            else:
                dp[i][j + Goods_List[i][1]] = min(dp[i-1][j] + Goods_List[i][0],dp[i][j + Goods_List[i][1]])
        

for k in range(len(dp[-1])-1,0,-1):
    if (dp[-1][k] != 0) & (dp[-1][k] <= W):
        print(k)
        break

Solution (Python):
from sys import stdin
from math import inf
n,W = map(int,stdin.readline().split())
dp = [inf]*(1000*n)
for _ in range(n):
    w,v = map(int,stdin.readline().split())
    for i in range(1000*n-v-1,-1,-1):
        if dp[i] and dp[i]+w <= W:
            dp[i+v] = min(dp[i+v],dp[i]+w)
    dp[v-1] = min(dp[v-1],w)
for i in range(len(dp)-1,-1,-1):
    if dp[i] != inf:
        print(i+1)
        break

Solution (Python):
INF, NVINF = float("inf"), 10**5
N, W = map(int,input().split())
dp = [0] + [INF] * NVINF
for _ in [None]*N:
  w, v = map(int,input().split())
  for j in range(NVINF, v-1, -1):
    dp[j] = min(dp[j], dp[j - v] + w)
for v, w in list(enumerate(dp))[::-1]:
    if w <= W:
      exit(print(v))

Solution (Python):

def resolve():
    N, max_W = map(int, input().split())
    W, V = zip(*[list(map(int, input().split())) for _ in range(N)])
    max_V = sum(V)
    dp = [[1 << 60] * (max_V + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for v in range(max_V + 1):
            dp[i + 1][v] = min(dp[i + 1][v], dp[i][v])
            if V[i] <= v:
                dp[i + 1][v] = min(dp[i + 1][v], dp[i][v - V[i]] + W[i])

    
    ans = 0
    for v in range(max_V + 1):
        if dp[N][v] <= max_W:
            ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
import bisect


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


def main():
    N, W = map(int, input().split())
    vsup = 10 ** 3 * N + 2
    dp = [10 ** 12 + 1] * (vsup)  
    dp[0] = 0

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

    print(bisect.bisect_right(dp, W) - 1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import bisect


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


def main():
    N, W = map(int, input().split())
    vsup = 10 ** 3 * N + 2
    dp = [10 ** 12 + 1] * (vsup)  
    dp[0] = 0

    for i in range(N):
        w, v = map(int, input().split())
        for j in range(vsup-2, -1, -1):
            if j - v >= 0:
                dp[j] = min(dp[j], dp[j - v] + w)
            dp[j] = min(dp[j],dp[j+1])

    print(bisect.bisect_right(dp,W)-1)

if __name__ == "__main__":
    main()