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

max_v = N * 1000

ans_array = [[10 ** 12] * (max_v + 1) for _ in range(N + 1)]

ans_array[0][0] = 0

for n in range(1, N + 1):
    ans_array[n][0] = 0
    for v in range(1, max_v + 1):
        if wv_array[n - 1][1] > v:
            ans_array[n][v] = ans_array[n - 1][v]
        else:
            ans_array[n][v] = min(
                ans_array[n - 1][v], ans_array[n - 1][v - wv_array[n - 1][1]] + wv_array[n - 1][0])

for v in range(max_v, -1, -1):
    if ans_array[N][v] <= W:
        print(v)
        exit()

Solution (Python):
import numpy as np


n, capacity = map(int, input().split())
value_max = 10 ** 5
dp = np.full(value_max + 1, capacity + 1)
dp[0] = 0

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

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

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

def main():
    N, W = map(int, input().split())
    inf = float('inf')
    dp = [inf] * (10**5+1)
    dp[0] = 0
    for n in range(1, N+1):
        w, v = map(int, input().split())
        for i in range(v, 10**5+1)[::-1]:
            if dp[i-v] + w <= W:
                dp[i] = min(dp[i], dp[i-v] + w)
    for i in range(10**5+1)[::-1]:
        if dp[i] < inf:
            print(i)
            break
if __name__ == '__main__':
    main()

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    m = sum(v)
    dp = [[float("inf")] * (m+1) for _ in range(N + 1)]
    dp[0][0] = 0

    for n in range(N):
        for kati in range(m+1):
            if kati - v[n] >= 0:
                dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati-v[n]] + w[n])
            dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati])

    ans = 0
    for i in range(m+1):
        if dp[-1][i] <= W:
            ans = i

    print(ans)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

def main():
    n,w = map(int, input().split())
    ary = [list(map(int, stdin.readline().split())) for _ in range(n)]
    xmax = sum([i[1] for i in ary])
    dp = [[float('inf')] * (xmax+1) for _ in range(n+1)]
    dp[0][0]= 0
    for i in range(n):
        for j in range(xmax+1):
            if j - ary[i][1] >= 0:
                dp[i+1][j] = min(dp[i+1][j] , dp[i][j-ary[i][1]] + ary[i][0])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    ans = 0
    for j in range(xmax+1):
        if dp[n][j] <= w:
            ans = j
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,W = map(int,input().split())
w_v = [list(map(int,input().split())) for i in range(N)]
INF = float("inf")
dp = [[INF]*100001 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
  for j in range(100001):
    if j >= w_v[i][1]:
      dp[i+1][j] = min(dp[i][j],dp[i][j-w_v[i][1]]+w_v[i][0])
    else:
      dp[i+1][j] = dp[i][j]
    
ans = 0
for j in range(100001):
  if dp[-1][j] <= W:
    ans = max(ans,j)
print(ans)

Solution (Python):




import sys
inf = 10**9+7
mod = 10**9+7
V = 10**5
n,W = map(int, input().split())
dp = [[inf for j in range(V+1)] for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    dp[i+1][0] = 0
    w,v = map(int, input().split())
    for j in range(V):
        if j+1-v >= 0:
            dp[i+1][j+1] = min(dp[i][j+1-v]+w, dp[i][j+1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], w)
for j in range(V+1):
    if dp[n][j] > W:
        print(j-1)
        sys.exit()
        break
print(V)

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

n, W = [int(x) for x in input().split()]
wv = [[int(x) for x in input().split()] for _ in range(n)]

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

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

ans = 0

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

print(ans)

Solution (Python):

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

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)

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

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

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

Solution (Python):
n, W = map(int, input().split())
w, v = [], []
inf = 10 ** 13
for _ in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
V = sum(v)


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

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

dp = np.full(N * 1001, W + 10000)
dp[0] = 0

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

ans = np.max(np.where(dp <= W))
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 ** 15
dp = [[INF]*(10**5+1) for _ in range(n+1)]
dp[0][0] = 0

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

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

print(max_v)

Solution (Python):






"""Module docstring
"""

import sys
from collections import defaultdict


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


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


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


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


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


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


if __name__ == "__main__":
    import doctest

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

Solution (Python):






"""Module docstring
"""

import sys
from collections import defaultdict


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


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


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


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


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


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


if __name__ == "__main__":
    import doctest

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

Solution (Python):
INF = 10 ** 9 + 1
MAV_V = 10 ** 5 + 1

def main():
    N, W = map(int, input().split())
    dp = [[INF] * MAV_V for _ in range(N+1)]
    dp[0][0] = 0

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

    ans = [i for i, v in enumerate(dp[-1]) if v != INF]
    print(max(ans))


if __name__ == "__main__":
    main()

Solution (Python):
INF = 10**12 + 5
MAV_V = 100001

def main():
    N, W = map(int, input().split())
    dp = [[INF] * MAV_V for _ in range(N+1)]
    dp[0][0] = 0

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

    ans = [i for i, v in enumerate(dp[-1]) if v != INF]
    print(max(ans))


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

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

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

print(((dp <= W) * np.arange(N * 1000 + 1)).max())

Solution (Python):
import numpy as np

N, W = map(int, input().split())
inf = 10**18
M = 10**5



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

Solution (Python):
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.ones(N*1000+1, dtype=int) *(W+1)
DP[0] = 0

for i in range(N):
    DP[v[i]:] = np.minimum(DP[:-v[i]]+ w[i], DP[v[i]:])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        ans = k
        
print(ans)

Solution (Python):
n,w=map(int,input().split())
INF = 10**12 + 5
cost=[[INF for i in range(100001)] for j in range(n+1)]
value=[list(map(int,input().split())) for i in range(n)]

for i in range(1,n+1):
  for j in range(100001)[::-1]:
    weight_=value[i-1][0]
    value_=value[i-1][1]
    if j < value_:
      cost[i][j]=min(cost[i-1][j],weight_)
    else:
      cost[i][j]=min(cost[i-1][j-value_]+weight_,cost[i-1][j])
for i in range(100001)[::-1]:
    if cost[-1][i]<=w:print(i+1);exit()

Solution (Python):
n,w = map(int,input().split())
w_ls, v_ls = [0] * n, [0] * n
for i in range(n):
    w_ls[i], v_ls[i] = map(int,input().split())
V = sum(v_ls)
dp = [[float("inf")] * (V+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(V+1):
        if j - v_ls[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v_ls[i]] + w_ls[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):
def solve(c, a):
    dp = [float('inf')]*(2*10**5)
    dp[0] = 0
    for w, v in a:
        for i in range(len(dp)-1, -1, -1):
            if dp[i] != float('inf'):
                dp[i+v] = min(dp[i+v], dp[i] + w)
    return next(i for i in range(len(dp)-1, -1, -1) if dp[i] <= c)
  
n, k = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
print(solve(k, a))

Solution (Python):
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = 10**10
dp = [INF]*(UV+1)
dp[0] = 0

for i in range(1, n+1):
    for j in reversed(range(1, UV+1)):
        if j-values[i-1] < 0:
            continue
        dp[j] = min(dp[j], dp[j-values[i-1]]+weights[i-1])

ans = 0
for j in reversed(range(UV+1)):
    if dp[j] <= w:
        ans = j
        break
print(ans)

Solution (Python):
N,W = map(int,input().split())
value,weight = [0],[0]
for i in range(N):
  w,v = map(int,input().split())
  value.append(v)
  weight.append(w)
V = sum(value)
dp = [[0]+[10**12]*V for _ in range(N+1)]
for i in range(1,N+1):
  for j in range(1,V+1):
    dp[i][j] = min(dp[i-1][j], dp[i-1][max(0, j-value[i])]+weight[i] )
for i in range(V,0,-1):
  if dp[N][i] <= W:
    print(i)
    quit()

Solution (Python):
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = 10**10
dp = [[INF]*(UV+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, UV+1):
        dp[i][j] = dp[i-1][j]
        if 0 <= j-values[i-1]:
            dp[i][j] = min(dp[i][j], dp[i-1][j-values[i-1]]+weights[i-1])

ans = 0
for i in reversed(range(UV+1)):
    if dp[-1][i] <= w:
        ans = i
        break
print(ans)

Solution (Python):
def resolve():
    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)
    dp = [[0 if i == 0 else W * N for i in range(N * max(value) + 1)]]
    for i in range(N):
        d = []
        for v in range(N * max(value) + 1):
            if v >= value[i]:
                d.append(min(dp[-1][v - value[i]] + weight[i], dp[-1][v]))
            else:
                d.append(dp[-1][v])
        dp.append(d)
    for i in reversed(range(N * max(value) + 1)):
        if dp[-1][i] <= W:
            print(i)
            return


if __name__ == "__main__":
    resolve()

Solution (Python):
n,w = map(int,input().split())
dpv = [10 ** 20 for i in range(10**5+1)]
dpv[0] = 0
for i in range(n):
  weight,value = map(int,input().split())
  for j in range(10**5-value,-1,-1):
    dpv[j+value] = min(dpv[j+value],dpv[j]+weight)
for i in range(10**5,-1,-1):
  if dpv[i] <= w:
    print(i)
    exit()

Solution (Python):
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = float('inf')
dp = [[0]+[INF]*UV for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, UV+1):
        dp[i][j] = dp[i-1][j]
        if 0 <= j-values[i-1]:
            dp[i][j] = min(dp[i][j], dp[i-1][j-values[i-1]]+weights[i-1])

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

Solution (Python):
"""
E-Knapsack2
Wが10**9まであるのでdpの置き方を工夫する。
dp[i]:=価値がiのときのナップザックの重さ
"""
N,W = map(int,input().split())
dp = [0]+[W+1]*(N*10**3)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(N*10**3+1-v)[::-1]:
        dp[j+v] = min(dp[j+v],dp[j]+w)
for i in range(N*10**3+1)[::-1]:
    if dp[i]<=W:
        print(i)
        exit()

Solution (Python):

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

max_value, max_weight = 0, 0
for w, v in wv:
    max_weight += w
    max_value += v
wv.sort()

dp = np.ones(max_value + 1, dtype=int) * max_weight

for w, v in wv:
    np.minimum(dp[v:] - w, dp[:-v], out=dp[:-v])

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

print(ans)

Solution (Python):
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3 * n
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

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

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


ans = 0
for i in range(v_max + 1):
    w_ = dp[n][i]
    if w_ <= w:
        ans = i
print(ans)

Solution (Python):


n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 5
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

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

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


ans = 0
for i in range(v_max + 1):
    w_ = dp[n][i]
    if w_ <= w:
        ans = i
print(ans)

Solution (Python):

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

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

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

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


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

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    INF = 10**10
    VMAX=10**3*N
    dp=[[INF for j in range(VMAX+1)] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(VMAX+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(VMAX,-1,-1):
        if dp[-1][i] <= W:
            print(i)
            break
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

INF = 10**16

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    V = max(v) * N
    dp = []
    for _ in range(N):
        l = [INF]*(V + 1)
        dp.append(l)
    
    
    for j in range(V + 1):
        dp[0][j] = w[0] if j == v[0] else INF
        dp[0][0] = 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 - v[i]] + w[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    
    res = 0
    for j in range(V + 1):
        if dp[N - 1][j] <= W:
            res = j
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Solution (Python):

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    INF = 10**10
    VMAX=10**3*N
    dp=[[INF for j in range(VMAX+1)] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(VMAX+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(VMAX,-1,-1):
        if dp[-1][i] <= W:
            print(i)
            break
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Solution (Python):

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

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

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

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


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

Solution (Python):



def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [[10**12] * 100001 for i in range(n + 1)]
    dp[0][0] = 0

    for i, item in enumerate(items):
        for i_v in range(100001):
            if item[1] - i_v > 0:
                dp[i + 1][i_v] = dp[i][i_v]
            else:
                dp[i + 1][i_v] = min(dp[i][i_v - item[1]] + item[0], dp[i][i_v])

    result = 0
    for sum_v, weght in enumerate(dp[-1]):
        if weght <= w:
            result = sum_v
    print(result)


if __name__ == '__main__':
    main()

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)
    
maxv = sum(v)
dp = [[float('inf')]*(maxv+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sumv in range(maxv+1):
        if sumv - v[i]  >= 0:
            dp[i+1][sumv] = min(dp[i+1][sumv], dp[i][sumv-v[i]] + w[i])
        dp[i+1][sumv] = min(dp[i+1][sumv], dp[i][sumv])

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = np.full(n * 1000 + 1, w + 1, dtype=int)
dp[0] = 0
for x, y in wv:
    dp[y:] = np.minimum(dp[y:], dp[:-y] + x)
print(np.max(np.where(dp <= w)))

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

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

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

res = 0
for v, e in enumerate(dp):
    if e <= W:
        res = v

print(res)

Solution (Python):
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110000 for i in range(110)]
INF=10**10
for j in range(1,110000):
  dp[0][j]=INF

for i in range(1,n+1):
  for j in range(110000):
    dp[i][j]=dp[i-1][j]
    if j-wv[i-1][1]>=0:
      dp[i][j]=min(dp[i][j],
                   dp[i-1][j-wv[i-1][1]]+wv[i-1][0])
ans=0
for v in range(110000):
  if dp[n][v]<=W:
    ans=max(ans,v)
      
print(ans)

Solution (Python):
N, W = map(int,input().split())
wn = [0]*N
vn = [0]*N
vnmax = pow(10,3)*N+1
dp = [10**9+1]*(vnmax)
dp[0] = 0

for n in range(N):
  wn, vn = map(int,input().split())
  for v in range(vnmax-1,vn-1,-1):
    dp[v] = min(dp[v],dp[v-vn]+wn)

num = 0
for v in range(1,vnmax):
  if dp[v] <= W: num = v
print(num)

Solution (Python):
N,W=map(int,input().split())
x=[0]+[-1]*110000

ma=0
for i in range(N):
    w,v=map(int,input().split())

    for j in range(len(x))[::-1]:
        if x[j]>=0:
            if  x[j]+w<=W:
                if x[j+v]<0:
                    x[j+v]=x[j]+w
                    ma=max(ma,j+v)
                else:
                    x[j+v]=min(x[j+v],x[j]+w)

print(ma)

Solution (Python):
n, w = [int(i) for i in input().split()]
dp = [10 ** 18] * (10 ** 5 + 1)
dp[0] = 0
for _ in range(n):
    u, v = [int(i) for i in input().split()]
    for i in reversed(range(len(dp))):
        if i + v < len(dp) and dp[i]+u <= w:
            dp[i + v] = min(dp[i + v], dp[i] + u)
ans = 0
for i, j in enumerate(dp):
    if j != 10 ** 18:
        ans = max(ans, i)
print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,w = map(int,readline().split())
WV = []
for i in range(n):
	WV.append(list(map(int,readline().split())))

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


for i in range(n):
	for j in range(10**5+1):
		if WV[i][1] - j > 0:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = min(dp[i][j],dp[i][j-WV[i][1]]+WV[i][0])

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

print(ans)

Solution (Python):
n, m = map(int, input().split())
W, V = [], []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
sumV = sum(V)
A = [1 << 30 for j in range(sumV+1)]
A[0] = 0
for i in range(n):
    B = []
    for j in range(V[i]):
        B.append(A[j])
    for j in range(V[i], sumV+1):
        B.append(min(A[j], A[j-V[i]]+W[i]))
    A = B
for j in range(sumV, 0, -1):
    if A[j] <= m:
        print(j)
        exit()

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

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
sv=sum(list(zip(*l))[1])
dp=[10**12]*(sv+1)
dp[0]=0

for wi,vi in l:
    for j in range(sv-vi,-1,-1):
        dp[j+vi]=min(dp[j+vi],dp[j]+wi)
        
ans=0

for i in range(sv+1):
    if dp[i]<=w:ans=i
print(ans)

Solution (Python):
INF = 10 ** 9 + 10
MAX_V = 1010

N, W = map(int, input().split())
MAX_SUM_V = N * MAX_V

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

dp = [[INF] * MAX_SUM_V for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(MAX_SUM_V):
        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])

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

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

V = sum(v)


dp = [[float('inf')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j>=v[i]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = dp[i][j]
res = 0
for j in range(V+1):
    if dp[N][j] <= W:
        res = j
print(res)

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 = [[10**9+1]*(sum(v)+1) for i in range(N+1)]
dp[0][0] = 0


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


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

Solution (Python):
import numpy as np
N,W = map(int,input().split())
V_sum = 0
w_l = []
v_l = []
for i in range(N):
    w,v = list(map(int,input().split()))
    V_sum+=v
    w_l.append(w)
    v_l.append(v)
dp = np.full(V_sum+1,W+1)
dp[0] = 0
for i in range(N):
    dp[v_l[i]:] = np.minimum(dp[v_l[i]:],dp[:-v_l[i]]+w_l[i])
for i in range(V_sum,-1,-1):
    if dp[i]<=W:
        print(i)
        break

Solution (Python):






'''
3 8
3 30
4 50
5 60
'''

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

v_max = (max(v)+1) * N
dp = [[None] * v_max for _ in range(N+1)]
dp[0] = [float('inf')] * v_max
dp[0][0] = 0

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


print(len([i for i in dp[N] if i <= W]) - 1)

Solution (Python):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
weights = list(map(lambda x: x[0], items))
values = list(map(lambda x: x[1], items))
sum_weights = sum(weights)
sum_values = sum(values)

dp = [([0] + [sum_weights*2 for _ in range(sum_values)]) for _ in range(N+1)]

for i in range(N):
    for v in range(1, sum_values+1):
        if v - values[i] >= 0:
            dp[i+1][v] = dp[i][v-values[i]] + weights[i]
        
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])
        
for i in reversed(range(sum_values+1)):
    if dp[N][i] <= W:
        print(i)
        break