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):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, w = ns()
    a = [na() for _ in range(n)]

    idx = n * 10 ** 3 + 1
    dp = [INF for _ in range(idx)]
    dp[0] = 0

    for wi, vi in a:
        for i in range(idx - 1, -1, -1):
            if dp[i] + wi <= w and i + vi < idx and dp[i] > -1:
                dp[i + vi] = min(dp[i + vi], dp[i] + wi)

    for i in range(idx - 1, -1, -1):
        if dp[i] != INF:
            print(i)
            break


if __name__ == '__main__':
    main()

Solution (Python):
import sys


def resolve():
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for x in [0] * N]

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

    for i in range(N):
        for sum_v in range(V):
            weight, value = lst[i]
            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])

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

resolve()

Solution (Python):
N,W = map(int,input().split())
dp = [0] + [float('inf')]*10**5

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

Solution (Python):
n, W = map(int, input().split())
w, v = [], []
for i in range(n):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
dp = [[float("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(10 ** 5 + 1):
        if j - v[i - 1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(100000, -1, -1):
    if dp[n][i] <= W:
        break
print(i)

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

def main():
  
  def knapsack_price(single=True):
    V = sum(price_list)
    dp_max = W + 1
    dp = [dp_max] * (V+1)
    dp[0] = 0
    
    for i in range(N):
      if single:
        S = list(reversed(range(price_list[i], V+1)))
      else:
        S = list(range(price_list[i], V+1))
      for price in S:
        dp[price] = min(dp[price], dp[price - price_list[i]] + weight_list[i])
    
    return max(price for price in range(V+1) if dp[price] <= W)
  
  N,W = map(int,input().split())
  
  price_list = []
  weight_list = []
  for _ in range(N):
    weight, price = map(int,input().split())
    price_list.append(price)
    weight_list.append(weight)
    
  print(knapsack_price(single=True))

if __name__ == '__main__':
    main()

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

n, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]

v = 10**5 + 4
D = [float("inf")] * v
D[0] = 0
for i in range(n):
    for j in range(v-1,-1,-1):
        if j-A[i][1] >= 0:
            D[j] = min(D[j], D[j-A[i][1]] + A[i][0])

ans = 0
for i in range(v):
    if D[i] <= w:
        ans = i
print(ans)

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

INF = int(1e16)

dp = [[INF] * (int(1e5) + 1) for _ in range(n + 1)]


dp[0][0] = 0

for i in range(1, n + 1):
    weight, value = map(int, input().split())
    for v in range(int(1e5) + 1):
        dp[i][v] = min(dp[i-1][v], dp[i][v])
        if v >= value:
            dp[i][v] = min(dp[i][v], dp[i-1][v-value] + weight)



for v in range(int(1e5), -1, -1):
    if dp[n][v] <= W:
        print(v)
        break

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

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):


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

    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(V,-1,-1):
            if j-v >= 0:
                dp[j] = min(dp[j],dp[j-v]+w)
    
    ans = -1
    for i in range(V+1):
        if dp[i] <= W:
            ans = i
    print(ans)

if __name__ == "__main__":
    main()

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

N,W = map(int,readline().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,readline().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
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    N, W = list(map(int, input().strip().split()))
    items = [[0, 0]]
    for i in range(N):
        items.append(list(map(int, input().strip().split())))
    V = 10**5
    dp = [[0]+[INF]*(V) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, V+1):
            if j-items[i][1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-items[i][1]]+items[i][0])
    for i in reversed(range(V+1)):
        if dp[N][i] <= W:
            print(i)
            return
    
if __name__ == '__main__':
    main()

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


def main():
    
    def knapsack_price(single=True):
        """
        重さが小さい時のナップサックDP
        :param single: True = 重複なし
        """
        """ dp[price <= V] = 価値を固定した時の最小重量 """
        V = sum(price_list)
        dp_max = W + 1
        dp = [dp_max] * (V + 1)
        dp[0] = 0  

        for item in range(N):
            if single:
                S = reversed(range(price_list[item], V + 1))
            else:
                S = range(price_list[item], V + 1)
            for price in S:
                dp[price] = min2(dp[price], dp[price - price_list[item]] + weight_list[item])
        return max(price for price in range(V + 1) if dp[price] <= W)

    


    def max2(x, y):
        """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
        if x > y:
            return x
        else:
            return y

    def min2(x, y):
        """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
        if x < y:
            return x
        else:
            return y

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

    price_list = []
    weight_list = []
    for _ in range(N):
        """ price と weight が逆転して入力されている場合有り """
        weight, price = map(int, input().split())
        price_list.append(price)
        weight_list.append(weight)

    print(knapsack_price(single=True))

if __name__ == '__main__':
    main()

Solution (Python):
def knapsack_price(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[price <= V] = 価値を固定した時の最小重量 """
    V = sum(price_list)
    dp_max = W+1
    dp = [dp_max] * (V + 1)
    dp[0] = 0   

    for item in range(N):
        if single:
            S = reversed(range(price_list[item], V + 1))
        else:
            S = range(price_list[item], V + 1)
        for price in S:
            dp[price] = min2(dp[price], dp[price - price_list[item]] + weight_list[item])
    return max(price for price in range(V+1) if dp[price] <= W)



import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


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

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)

print(knapsack_price(single=True))

Solution (Python):



"""

経路を状態の添え字に取るような事は無い
経路の末端の情報のみを横軸の添え字に取ることが多い
例：一年生　⇒　k項目までの総和
   パスタ　⇒　k日目に食べたパスタ
   暑い日々⇒　k日目に着た服

DPテーブルにおいて、ある値以降の全てで 1 となる場合、
その値でDPテーブルを切ってしまって、
indexがその値を超えるごとに、DPテーブルの上限に +1 をしていくというアイデアで計算量を減らせる
例: https://atcoder.jp/contests/tdpc/submissions/14958104

初期条件を常に意識するように！

ベンチマーク
（重複なし）
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4641577
(重複あり)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4641577

"""


import sys
input = sys.stdin.readline



M, W = map(int, input().split())                                
single = True                                                   

price_list = [0]
weight_list = [0]
for _ in range(M):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)




V = sum(price_list)
dp_max = W + 1                                                  


dp = [[dp_max] * (V + 1) for _ in range(M + 1)]                 
""" dp[item <= M ][weight <= V] = 価値を固定した時の"最小"重量 """

for item in range(M+1):                                         
    dp[item][0] = 0                                             





for item in range(1,M+1):                                       
    for price in range(1, V+1):
        if price < price_list[item]:                            
            dp[item][price] = dp[item - 1][price]
        else:
            temp = dp[item - single][price - price_list[item]] + weight_list[item]  
            if temp < dp[item-1][price]:                        
                dp[item][price] = temp
            else:
                dp[item][price] = dp[item-1][price]

print(max(price for price in range(V+1) if dp[M][price] <= W))

Solution (Python):
N,W = map(int,input().split(" "))
INF =  1e11
v = [INF]*100010
v[0] = 0
for i in range(N):
  weight,value = map(int,input().split(" "))
  for j in range(100001,0,-1):
    if j < value:
      break
    v[j] = min(v[j],v[j-value]+weight)

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

Solution (Python):
n, w = map(int, input().split())
dp = [1001001001] * (1000 * n + 1)
dp[0] = 0
for _ in range(n):
    wi, vi = map(int, input().split())
    for i in range(1000 * n, vi - 1, -1):
        dp[i] = min(dp[i], dp[i-vi] + wi)
print(max(filter(lambda v: dp[v] <= w, range(1000 * n + 1))))

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


def main():
    N, W = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(N)]

    dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(10**5 + 1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if 0 <= j - A[i][1]:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - A[i][1]] + A[i][0])
    ans = 0
    for j in range(10**5+1)[::-1]:
        if dp[N][j] <= W:
            ans = j
            break
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



n,we=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
dp=[[float('inf')]*(n+1) for _ in range(sum(v)+1)]
for i in range(n+1):
    dp[0][i]=0
for j in range(1,n+1):
  for i in range(1,sum(v)+1):
    if(v[j-1]<=i):
      dp[i][j]=min(w[j-1]+dp[i-v[j-1]][j-1],dp[i][j-1])
    else:
      dp[i][j]=dp[i][j-1]
ans=0
for i in range(sum(v)+1):
  
  if(dp[i][n]<=we):
  	ans=i
print(ans)

Solution (Python):
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
maxValue=sum(values)
dp=[[float("inf")]*(maxValue+1) for i 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,maxValue+1):
        if(values[i-1]<=j):
            dp[i][j]=min(weights[i-1]+dp[i-1][j- values[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
 
ans=0
for i in range(maxValue+1):
    if(dp[n][i]<=capacity):
        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())

INF = 10**13 

V = (10**5)+1

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

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

print(ans)

Solution (Python):

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


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


sum = 1
for i in range(N):
    sum += array[i][1]

weights = [[float('inf')] * (sum + 1) for _ in range(N + 1)]

weights[0][0] = 0

for n in range(N):
    
    for v in range(sum + 1):
        
        weights[n + 1][v] = weights[n][v]
        weight = weights[n][v - array[n][1]] + array[n][0]
        if weight < weights[n + 1][v]:
            weights[n + 1][v] = weight

ans = 0
for i in range(sum):
    if weights[N][i] <= W:
        ans = i
print(f"{ans}")

Solution (Python):
import sys

input = sys.stdin.readline

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


MAX_V = 0
for line in array:
    MAX_V += line[1]
MAX_V += 1

f_inf = float('inf')


def chmin(a, b):
    if a <= b:
        return a
    else:
        return b


def knapsack(n, w):
    
    dp = [[f_inf] * MAX_V for j in range(N + 1)]
    
    dp[0][0] = 0
    
    
    for i in range(N):
        
        for sum_v in range(MAX_V):
            
            if sum_v - array[i][1] >= 0:
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v],
                                         dp[i][sum_v - array[i][1]] + array[i][0])
            
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)


knapsack(N, W)

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

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

res = 0

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

print(res)

Solution (Python):

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


memo = [10**10]*(10**5+1)
memo[0] = 0

for weight, value in items:
    for i in reversed(range(len(memo)-value)):
            memo[i+value] = min(memo[i+value],memo[i] + weight)

ans = 0
for i in range(len(memo)):
    if memo[i] != 10**10 and memo[i] <= W:
        ans = i

print(ans)

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

    max_v = 10**5 + 10
    dp = [[float('inf') for i in range(max_v)] for j in range(100+10)]

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(max_v):

            
            if sum_v - val[i] >= 0:
                dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v - val[i]] + wei[i])
            else:
                
                dp[i+1][sum_v] = dp[i][sum_v]

    res = 0
    for i in range(100+10):
        for sum_v in range(max_v):
            if dp[i][sum_v] <= w and res < sum_v:
                res = sum_v

    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
IN=lambda:map(int,input().split())
N,W=IN()
INF=float("inf")
dp=[INF]*(1000*N)
dp.insert(0,0)
c=0
ans=0
for i in range(N):
    w,v=IN()
    for j in range((1000*N+1),-1,-1):
        if dp[j-v]!=INF:
            dp[j]=min(dp[j],dp[j-v]+w)
for i in range(1000*N+1):
    if dp[i]<=W:
        ans=i
print(ans)

Solution (Python):
import sys


import numpy as np

input = sys.stdin.readline



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 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 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):
        
        dp[i + 1][:v[i]] = 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]:])
    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 numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit
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):
        
        dp[i + 1][:v[i]] = 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]:])
    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):

N,W=map(int,input().split())
w=[]
v=[]
vmax=100010
nmax=110

for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    
DP= [[10**12 for j in range(vmax)] for i in range(nmax)]

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

DP[0][0]=0

for i in range(N):
    for j in range(vmax):
        if  j-v[i]>=0:
            DP[i+1][j]=chmin(DP[i][j],DP[i][j-v[i]]+w[i])
        else:
            DP[i+1][j]=DP[i][j]

ans=0            
for i in range(nmax):
    for j in range(vmax):
        if DP[i][j]<=W and ans<j:
            ans=j
print(ans)

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
val_max=sum(v)
dp=[1000000001]*(val_max+1)


dp[0]=0
for i in range(N):
    for j in range(val_max,-1,-1):
        if dp[j]!=1000000001:
            if dp[j]+w[i]<=W:
                dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])

for i in range(val_max,-1,-1):
    if dp[i]!=1000000001:
        print(i)
        break

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

INF = float("inf")
dp = [0] + [INF] * 10**5

for _ in range(N):
  w, v = map(int, input().split())
  for j in range(10**5, v-1, -1):
    dp[j] = min(dp[j], dp[j-v] + w)

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

print(ans)

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

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][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][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

Solution (Python):
N, W = map(int, input().split())
max_val = N * 1000 + 1
dp = [[float("inf") for _ in range(max_val)] for _ in range(N+1)]
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int,input().split())

dp[0][0] = 0
ans = 0
for i in range(1, N+1):
    for sum_v in range(max_val):
        if sum_v - v[i-1] >= 0: 
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v - v[i-1]] + w[i-1])
        else:
            dp[i][sum_v] = dp[i-1][sum_v]
    for val, weight in enumerate(dp[i]):
        if weight <= W:
            ans = max(ans, val)

print(ans)

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

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

INF = 1001001000100

dp = [[INF]*mv for i in range(110)]

dp[0][0] = 0

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

print(ans)

Solution (Python):

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
inf = float("inf")
dp = [[inf for i in range(100100)] for j in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for v in range(100100):
        if wv[n][1] <= v:
            dp[n+1][v] = min(dp[n][v - wv[n][1]] + wv[n][0], dp[n][v])
        else:
            dp[n+1][v] = dp[n][v]

for v in reversed(range(100100)):
    if dp[-1][v] > 0 and dp[-1][v] <= W:
        print(v)
        break

Solution (Python):
IN=lambda:map(int,input().split())
N,W=IN()
INF=float("inf")
dp=[INF]*(1000*N)
dp.insert(0,0)
c=0
ans=0
for i in range(N):
    w,v=IN()
    for j in range((1000*N+1),-1,-1):
        if dp[j-v]!=INF:
            dp[j]=min(dp[j],dp[j-v]+w)
for i in range(1000*N+1):
    if dp[i]<=W:
        ans=i
print(ans)

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

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


def solve(N, W, WV):
    MAX_VALUE = N * 10 ** 3
    weights = [INF] * (MAX_VALUE + 1)
    weights[0] = 0
    for i in range(N):
        next_weights = weights[:]
        weight, value = WV[i]
        for j in range(MAX_VALUE - value + 1):
            next_weights[j + value] = min(
                weights[j + value],
                weights[j] + weight)
        weights = next_weights
    for i in range(MAX_VALUE, -1, -1):
        if weights[i] <= W:
            return i


T1 = """
3 8
3 30
4 50
5 60
"""


def main():
    N, W = map(int, input().split())
    WV = [
        list(map(int, input().split()))
        for i in range(N)
    ]
    print(solve(N, W, WV))


def _test():
    """
    >>> as_input(T1)
    >>> main()
    90
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):

def knapsack(W,weight,value):
    n = len(weight)
    dp = [[0]*(W+1) for _ in range(n+1)]
    
    for j in range(W):
        dp[0][j] = 0
    for i in range(n):
        for j in range(W+1):
            if weight[i] <= j:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]
    sol = dp[-1][-1]
    return dp,sol





def knapsack2(W,weight,value):
    n = len(weight)
    max_v = n*max(value)
    dp = [[0 for j in range(max_v)] for i in range(n)]
    
    for i in range(max_v):
        if i+1 > value[0]:
            dp[0][i] = float('inf')
        else:
            dp[0][i] = weight[0]
    
    for i in range(1,n):
        for j in range(max_v):
            if j+1 > value[i]:
                dp[i][j] = min(dp[i-1][j], weight[i]+dp[i-1][j-value[i]])
            else:
                dp[i][j] = min(dp[i-1][j], weight[i])
    for i in range(1,max_v+1)[::-1]:
        if dp[-1][i-1] <= W:
            sol = i
            break
    return dp,sol

N,W = map(int,input().split())
values, weights = [],[]
for _ in range(N):
    ｗ,ｖ = map(int,input().split())
    values.append(v)
    weights.append(w)

W = min(W,sum(weights))
dp,sol = knapsack2(W,weights,values)
print(sol)

Solution (Python):
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
maxValue=sum(values)
dp=[[float("inf")]*(maxValue+1) for i 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,maxValue+1):
        if(values[i-1]<=j):
            dp[i][j]=min(weights[i-1]+dp[i-1][j- values[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

ans=0
for i in range(maxValue+1):
    if(dp[n][i]<=capacity):
        ans=i
print(ans)

Solution (Python):
def solve(w,v,tv,W):
    dp=[float('inf')]*(tv+1)
    dp[0]=0
    for i in range(len(w)):
        for j in range(tv-v[i],-1,-1):
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
    maxx=0
    for i in range(tv+1):
        if dp[i]<=W:
            maxx=max(maxx,i)
    return maxx
if __name__=='__main__':
    n,W=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        p,q=map(int,input().split())
        w.append(p)
        v.append(q)
    print(solve(w,v,sum(v),W))

Solution (Python):



INF = 10**15

N,W = map(int,input().split())
w = []
v = []
for i in range(N):
    tmpW,tmpV = map(int,input().split())
    w.append(tmpW)
    v.append(tmpV)

dp = [[INF]*(100*1000+1) for i in range(N)]
dp[0][0]=0
dp[0][v[0]]=w[0]

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

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

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

INF = 10**12


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

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

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def knapsack(wt,sm,W,n,V):
    K = [float('inf')]*(sm+1)
    K[0] = 0
    for i in range(n):
        for j in range(sm-V[i],-1,-1):
                K[j+V[i]] = min(K[j+V[i]],K[j]+W[i])
    
    return max([i for i in range(sm+1) if K[i] <= wt])

n,wt = ip()
V,W = [0]*n,[0]*n
for i in range(n):
    w,v = ip()
    V[i] = v
    W[i] = w
ans = knapsack(wt,sum(V),W,n,V)
print(ans)

Solution (Python):
n,lw=map(int,input().split())
item=[]
for i in range(n):
    inp0,inp1=map(int,input().split())
    item.append((inp0,inp1))

dp=[10**13 for i in range(1002*n)]
dp[0]=0

for i in range(n):
    w=item[i][0]
    v=item[i][1]
    for q in range(1002*n-1,-1,-1):
        if q<=v:
            dp[q]=min(dp[q], w)
        else:
            dp[q]=min(dp[q], dp[q-v]+w)

for i in range(1002*n):
    if dp[i]>lw:
        print(i-1)
        break

Solution (Python):
import copy

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

min_w_per_v = [10**11] * (10**5+3)
min_w_per_v[0] = 0

for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(min_w_per_v)
    for j in range(v, len(min_w_per_v)):
        min_w_per_v[j] = min(tmp[j], tmp[j-v]+w)
        
for n, i in enumerate(min_w_per_v[::-1]):
    if i <= W:
        print(10**5+3-n-1)
        break

Solution (Python):
N ,W = map(int,input().split())
INF = float('inf')
w = [0] * N
v = [0] * N

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

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