Problem:
0-1 Knapsack Problem II You have N items that you want to put them into a knapsack. Item i has value v i and weight w i . You want to find a subset of items to put such that:  The total value of the items is as large as possible.  The items have combined weight at most W , that is capacity of the knapsack.  Find the maximum total value of items in the knapsack. Input  N  W  v 1  w 1  v 2  w 2 : v N  w N  The first line consists of the integers N and W . In the following N lines, the value and weight of the i -th item are given. Output Print the maximum total values of the items in a line. Constraints  1 ≤ N ≤ 100  1 ≤ v i ≤ 100  1 ≤ w i ≤ 10,000,000  1 ≤ W ≤ 1,000,000,000  Sample Input 1 4 5
4 2
5 2
2 1
8 3 Sample Output 1 13 Sample Input 2 2 20
5 9
4 10 Sample Output 2 9

Solution (Python):
N, W = map(int, input().split())
dp = [0] + [W+1] * (N*100)
for i in range(N):
    v, w = map(int, input().split())
    for j in range(i*100, -1, -1):
        if dp[j+v] > dp[j] + w:
            dp[j+v] = dp[j] + w

for v, w in zip(range(N*100, -1, -1), dp[::-1]):
    if w < W+1:
        print(v)
        break

Solution (Python):
N, W = map(int, input().split())
INF, V = 1 << 40, 100
dp = [[INF for j in range(N*V+1)] for i in range(N+1)]


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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_N, MAX_V = 100, 100


def solve():
    dp = [[float('inf')] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(MAX_N * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(MAX_N * MAX_V + 1):
        if dp[c_items][i] <= real_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Solution (Python):



"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_V = 100


def solve():
    dp = [[float('inf')] * (c_items * MAX_V + 1) for _ in range(c_items + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(c_items * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(c_items * MAX_V + 1):
        if dp[c_items][i] <= knapsack_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, knapsack_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Solution (Python):



"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_V = 100


def solve():
    dp = [[float('inf')] * (c_items * MAX_V + 1) for _ in range(c_items + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(c_items * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    res_list = dp[-1]
    for i in range(c_items * MAX_V + 1):
        if res_list[i] <= knapsack_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, knapsack_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Solution (Python):
from math import isfinite
from itertools import dropwhile

n, knapsack = map(int, input().split())
dpn = n * 100  
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(dpn - value, 0, -1):
        if not isfinite(dp[j]):
            continue
        new_weight = dp[j] + weight
        if new_weight <= knapsack and dp[j + value] > new_weight:
            dp[j + value] = new_weight
    if weight <= knapsack and dp[value] > weight:
        dp[value] = weight

print(next(dropwhile(lambda i: not isfinite(dp[i]), range(dpn, -1, -1))))

Solution (Python):
from math import isfinite

n, knapsack = map(int, input().split())
dpn = n * 100  
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(dpn - value, -1, -1):
        if not isfinite(dp[j]):
            continue
        new_weight = dp[j] + weight
        if new_weight <= knapsack and dp[j + value] > new_weight:
            dp[j + value] = new_weight

print(next(filter(lambda i: isfinite(dp[i]), range(dpn, -1, -1))))

Solution (Python):
N, W = map(int, raw_input().split())
P = [map(int, raw_input().split()) for i in xrange(N)]
V = sum(v for v, w in P)
dp = [W+1]*(V+1)
dp[0] = 0
for v, w in P:
    for i in xrange(V-v, -1, -1):
        dp[i+v] = min(dp[i+v], dp[i]+w)
for i in xrange(V, -1, -1):
    if dp[i] <= W:
        print i
        break

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

N, W = map(int, readline().split())
inf = float("inf")
dp = [inf]*(N*100+1)
dp[0] = 0
s = {0}

for i in range(N):
    v, w = map(int, readline().split())
    for _v in sorted(s, reverse=True):
        new_w = dp[_v] + w
        if new_w <= W:
            new_v = v + _v
            dp[new_v] = new_w if new_w < dp[new_v] else dp[new_v]
            s.add(new_v)

for i in range(N*100, -1, -1):
    if dp[i] < inf:
        print(i)
        break

Solution (Python):
from collections import defaultdict
INF = 10 ** 10


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

    dp = [[INF] * (N * 100 + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        v, w = items[i]
        for j in range(len(dp[0])):
            if dp[i][j] != INF:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
                dp[i + 1][j + v] = min(dp[i + 1][j + v], dp[i][j] + w)
    ans = 0
    for i in range(len(dp)):
        for j in range(len(dp[0])):
            if dp[i][j] <= W:
                ans = max(ans, j)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_F&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def solve(items, W, max_v):
    
    n = len(items)
    dp = [[float('inf')]*(n*max_v + 1) for _ in range(n+1)] 
    dp[0][0] = 0

    for i, item in enumerate(items):
        for j in range(n * max_v+1):
            if j < item.v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-item.v]+item.w)

    for j in range(n * max_v + 1):
        if dp[n][j] <= W:
            result = j
    return result


item = namedtuple('item', ['v', 'w'])
def main(args):
    N, W = map(int, input().split())
    items = []
    for _ in range(N):
        v, w = map(int, input().split())
        items.append(item(v, w))
    items.sort()
    max_v = items[-1].v

    result = solve(items, W, max_v)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
N, W = map(int, input().split())
dp = [0] + [W+1] * (N*100)
for i in range(N):
    v, w = map(int, input().split())
    for j in range(i*100, -1, -1):
        if dp[j+v] > dp[j] + w:
            dp[j+v] = dp[j] + w

for v, w in zip(range(N*100, -1, -1), dp[::-1]):
    if w < W+1:
        print(v)
        break

Solution (Python):



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

dp = dict()
dp[0] = 0
max_v = 0
for i in range(N):
    tmp = dp.copy()
    for k, v in tmp.items():
        dp.setdefault(k+vs[i], float('inf'))
        dp[k+vs[i]] = min(v + ws[i], dp[k+vs[i]])
        if dp[k+vs[i]] <= W:
            max_v = max(max_v, k+vs[i])


print(max_v)

Solution (Python):
INF = 10 ** 20

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

value = []
weight = []

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

sum_value = sum(value)

dp = [INF for _ in range(sum_value + 1)]
dp[0] = 0

for i in range(n):
  for j in range(sum_value, value[i] - 1, -1):
    dp[j] = min(dp[j], dp[j - value[i]] + weight[i])

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

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

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

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


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

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()
    dp = [INF for _ in range(n * 100 + 1)]
    dp[0] = 0

    for _ in range(n):
        vi, wi = ns()
        for i in range(n * 100 - vi, -1, -1):
            if dp[i] == INF:
                continue
            if dp[i] + wi <= w:
                dp[i + vi] = min(dp[i + vi], dp[i] + wi)

    for i in range(n * 100, -1, -1):
        if dp[i] != INF:
            print(i)
            exit(0)


if __name__ == '__main__':
    main()

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



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

price_list = [0]
weight_list = [0]
for _ in range(M):
    price, weight = 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):
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, W = LI()
    vw = [LI() for _ in range(N)]

    v_sum = sum([i[0] for i in vw])

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

    for i in range(N):
        for j in range(v_sum):
            v_p = max(j + 1 - vw[i][0], 0)
            if v_p >= 0:
                dp[i+1][j+1] = min(dp[i][j+1], dp[i][v_p] + vw[i][1])
            else:
                dp[i+1][j+1] = dp[i][j+1]

    
    
    
    ans = bisect.bisect_right(dp[-1], W) - 1
    print(ans)

if __name__ == '__main__':
    resolve()

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

V=max(v)*N
dp=[-1]*(V+1)
dp[0]=0

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

for i in range(V+1):
    if dp[V-i]!=-1 and dp[V-i]<=W:
        print(V-i)
        break

Solution (Python):






import sys



import collections

def solve():
  N,W = map(int,sys.stdin.readline().split())
  vw = tuple(tuple(map(int,sys.stdin.readline().split())) for _ in range(N))
  dp = {}
  dp[0] = 0
  
  for v,w in vw:
    temp = dp.copy()
    for j in list(dp.keys()):
      if j+w <= W and (not j+w in dp or dp[j+w] < dp[j]+v):
        temp[j+w] = dp[j]+v
        
    dp = temp
    
  print(max(dp.values()))


def solve1():
  N,W = map(int,sys.stdin.readline().split())
  vw = tuple(tuple(map(int,sys.stdin.readline().split())) for _ in range(N))
  V = sum(v for v,_ in vw)
  dp = [W+1]*(V+1)
  dp[0] = 0
  for v,w in vw:
    for c_v in range(V+1)[::-1]:
      if 0 <= c_v-v: 
        dp[c_v] = min(dp[c_v],dp[c_v-v]+w)
    
  for c_v in range(V+1)[::-1]:
    if dp[c_v] <= W:
      return c_v
  return V
print(solve1())

Solution (Python):
def KP(Val,Wei,N,W):
    v_sum = sum(Val)
    
    INF = 10**9+1
    dp = [[INF for _ in range(v_sum+1)] for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for j in range(v_sum+1):
            if j - Val[i] >= 0:
                dp[i+1][j] = min(dp[i][j-Val[i]]+Wei[i],dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]

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

    return output

def main():
    N,W = map(int,input().split())
    VW = [list(map(int,input().split())) for _ in range(N)]
    Val = [VW[i][0] for i in range(N)]
    Wei = [VW[i][1] for i in range(N)]
    ans = KP(Val,Wei,N,W)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N,W = map(int, raw_input().split())
vs,ws = [],[]
for i in range(N):
    v,w = map(int, raw_input().split())
    vs.append(v)
    ws.append(w)
V = sum(vs)

DP = [10**10]*(V+1)
DP[0] = 0

for v,w in zip(vs, ws):
    for i in reversed(range(v, V+1)):
        DP[i] = min(DP[i], DP[i-v] + w)

ans = max(v for v,w in enumerate(DP) if w <= W)
print ans

Solution (Python):
n, m = map(int, input().split())
VW = [tuple(map(int, input().split())) for i in range(n)]
V = [v for v, w in VW]
W = [w for v, w in VW]




sv = sum(V)
inf = 10**10
DP = [[inf for j in range(sv+1)] for i in range(n+1)]
DP[0][0] = 0
for i in range(n):
    for j in range(sv+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 j in range(sv, 0, -1):
    if DP[n][j] <= m:
        print(j)
        exit()
print(0)

Solution (Python):
n, w = map(int, input().split())
vw = [input().split() for _ in range(n)]
vw = [(int(x[0]), int(x[1])) for x in vw]
v_max = sum([x[0] for x in vw])

INF = 10 ** 9 + 1
pdp = [INF for _ in range(v_max+1)]
cdp = [INF for _ in range(v_max+1)]
pdp[0] = 0
cdp[0] = 0

for i in range(n):
    for j in range(v_max+1):
        if j + vw[i][0] < v_max + 1:
            cdp[j + vw[i][0]] = min(pdp[j + vw[i][0]], pdp[j] + vw[i][1])
        else:
            break
    pdp = cdp[:]

ans = INF
for i in range(len(cdp)):
    if cdp[i] <= w:
        ans = i

print(ans)

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    N, W = map(int, f_i.readline().split())
    
    vw = tuple(tuple(map(int, f_i.readline().split())) for i in range(N))
    
    size = sum(vw_i[0] for vw_i in vw)
    inf = 10 ** 9
    dp = [inf] * (size + 1)
    dp[-1] = 0
    
    for v, w in vw:
        for i, tpl in enumerate(zip(dp[v:], dp)):
            w1, w2 = tpl
            w1 += w
            if w1 < w2:
                dp[i] = w1
    
    ans = 0
    for i, w in enumerate(dp[-2::-1], start=1):
        if w <= W:
            ans = i
    
    print(ans)

solve()

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

V = sum(map(lambda x:x[0],item))

dp = [W+1 for _ in range(V+1)]
dp[0] = 0

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    inf=10**9+5
    n,wn=MI()
    dp=[inf]*10005
    dp[0]=0
    for _ in range(n):
        v,w=MI()
        for i in range(10004,-1,-1):
            if i-v<0:break
            dp[i]=min(dp[i],dp[i-v]+w)
    for i in range(10004,-1,-1):
        if dp[i]<=wn:
            print(i)
            break

main()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, W = iim()
    S = [list(iim()) for i in range(N)]
    NV = N * 100 + 1

    Inf = float("inf")
    dp = [Inf] * (NV+1)
    dp[0] = 0

    ans = 0
    for v, w in S:
        for i in range(ans, -1, -1):
            j = i + v
            w2 = dp[i] + w
            if dp[i] == Inf: continue
            if w2 > W: continue
            dp[j] = min(dp[j], w2)
            ans = max(ans, j)

    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
N,W = map(int,input().split())
V = 100*N
Data = []
for _ in range(N):
    v,w = map(int,input().split())
    Data.append([v,w])

INF = 10**12
DP = [[INF]*(V+1) for _ in range(N+1)]
for i in range(N+1):
    DP[i][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        tv,tw = Data[n-1]
        if tv <= v:
            DP[n][v] = min(DP[n][v],DP[n-1][v-tv]+tw)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

res = 0
for v in range(1,V+1):
    w = DP[N][v]
    if w <= W:
        res = v
print(res)

Solution (Python):
def main():
    N, W = map(int, input().split())
    values, weights = [], []
    for i in range(N):
        v, w = map(int, input().split())
        values.append(v)
        weights.append(w)

    INF = 10 ** 11
    MAX_VALUE = 100 * N
    dp = [[INF for i in range(MAX_VALUE + 1)] for j in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(MAX_VALUE + 1):
            if values[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - values[i]] + weights[i])

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

    print(ans)


main()

Solution (Python):
N,W,*L=map(int,open(0).read().split())
dp=[float("inf")]*10001
dp[0]=0
for v,w in zip(*[iter(L)]*2):
	for i in range(10000,v-1,-1):
		dp[i]=min(dp[i],dp[i-v]+w)
ans=0
for v in range(10001):
	if dp[v]<=W:
		ans=max(ans,v)
print(ans)

Solution (Python):
import sys

if __name__ == "__main__":
    MAX_V = 100 ** 2  
    N, W = map(lambda x: int(x), input().split())
    dp = [sys.maxsize] * (MAX_V + 1)
    dp[0] = 0
    for i in range(N):
        value, weight = map(lambda x: int(x), input().split())
        for v in range(MAX_V, 0, -1):
            if (v - value < 0):
                break
            dp[v] = min(dp[v], dp[v - value] + weight)

    ans = 0
    for v in range(MAX_V, 0, -1):
        if dp[v] <= W:
            ans = v
            break

    print(ans)

Solution (Python):
n,w_max = map(int, input().split( ))
v = []
w = []
for _ in range(n):
    v_in,w_in = map(int, input().split( ))
    v.append(v_in)
    w.append(w_in)


v_max = sum(v)

lrg =100000000000001

DP = [lrg]*(v_max*2)
DP[0] = 0







for i in range(n):
    for u in range(v_max,0,-1):
         DP[u] = min(DP[u], DP[u-v[i]] + w[i])



ans = []
for u in range(v_max+1):
    if DP[u] <= w_max:
        ans.append(u)
print(max(ans))

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

dp = [W+1] * (MAX_V + 1)
dp[0] = 0
for v, w in I:
    for j in range(MAX_V, v-1, -1):
        dp[j] = min(dp[j-v] + w, dp[j])
        
for i in range(MAX_V, -1, -1):
  if dp[i] <= W:
    print(i)
    break

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

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

Solution (Python):


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

MAX_V = sum(v for v, w in item)


weight = {u: float('inf') for u in range(MAX_V + 1)}
weight[0] = 0


for v, w in item:
    weight = {u: (min(weight[u - v] + w, weight[u]) if u >= v else weight[u])
              for u in range(MAX_V + 1)}

v = max(v for v in weight if weight[v] <= W)
print(v)

Solution (Python):
def knapsack(n, w, info):
    sum_v = 0
    for i in range(n):
        value = info[i][0]
        sum_v += value

    
    
    dp = [[float("inf")]*(sum_v + 1) for i in range(n + 1)]
    dp[0][0] = 0

    for i in range(n):
        for j in range(sum_v + 1):
            weight = info[i][1]
            value = info[i][0]
            if j < value:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - value] + weight)
    ans = 0
    for j in range(sum_v + 1):
        if dp[n][j] <= w:
            ans = j
    return ans


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

Solution (Python):
def knapsack_val(W, items):
    '''
        W (int): the capacity of a knapsack
        items (list of tuples): i-th element is a tuple (weight, value)
    '''
    N = len(items)
    INF = 10**12
    MAX_V = sum([v for _, v in items])
    
    dp = [[INF for j in range(MAX_V+1)] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        w, v = items[i-1]
        for j in range(MAX_V+1):
            if j - v >= 0:
                dp[i][j] = min(dp[i-1][j-v] + w, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    for v in range(MAX_V, -1, -1):
        if dp[N][v] <= W:
            break
    return v

N, W = map(int, input().split())
items = []
for _ in range(N):
    v, w = map(int, input().split())
    items.append((w, v))
print(knapsack_val(W, items))

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

N, W = [int(x)for x in input().split()]
items = []
sum_value = 0
for i in range(N):
    v, w = map(int, input().split())
    items += [(v,w)]
    sum_value += v
dp = [0]+[float('inf')]*(sum_value)

for i in range(N):
    v, w = items[i]
    for j in reversed(range(v,sum_value+1)):
        dp[j] = min(dp[j],dp[j-v]+w)

for j in reversed(range(sum_value+1)):
    if dp[j] <= W:
        print(j)
        break

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

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

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

for i in range(N):
    v,w = VW[i]
    
    for p in range(0, 10001): 
        dp[i+1][p+v] = min(dp[i+1][p+v], 
                           dp[i][p]+w )

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


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

Solution (Python):
N, W = [int(x) for x in input().split()]
vs = [0] * N
ws = [0] * N

for i in range(N):
    vs[i], ws[i] = [int(x) for x in input().split()]

vmax = sum(vs) + 1
dp = [[float('inf')] * vmax for x in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    v = vs[i - 1]
    w = ws[i - 1]
    for j in range(vmax):
        if j < v:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)

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

Solution (Python):




def max_value(total_weight, items):
    total_value = sum([v for v, _ in items])
    ws = [total_weight+1] * (total_value+1)
    ws[0] = 0

    for item in sorted(items):
        v, w = item
        for i in reversed(range(total_value-v+1)):
            ws[i+v] = min(ws[i+v], ws[i] + w)

    return max([i for i, w in enumerate(ws) if w <= total_weight])


def run():
    n, t = [int(i) for i in input().split()]
    vs = []

    for _ in range(n):
        v, w = [int(i) for i in input().split()]
        vs.append((v, w))

    print(max_value(t, vs))


if __name__ == '__main__':
    run()

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001
NUM = 10000



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

dp = [W+1]*(NUM+1)
dp[0] = 0

for loop in range(N):
    value,weight = map(int,input().split())
    for v in range(NUM,0,-1):
        if v-value < 0:
            break
        dp[v] = min(dp[v],dp[v-value]+weight) 

ans = 0
for i in range(NUM,0,-1):
    if dp[i] <= W:
        ans = i
        break

print("%d"%(ans))

Solution (Python):
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[0] for i in goods])
dp = [float("inf") for i in range(v_sum+1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j-goods[i][0]]+goods[i][1], dp[j])
for i in range(v_sum,-1,-1):
    if dp[i] <= W:
        print(i)
        break

Solution (Python):
INF = 10**20

def sack(N,W,vlist,wlist):
    sum_val = sum(vlist)
    global INF
    dp = [INF for i in range(sum_val+1)]
    dp[0] = 0 
    for i in range(N):
        for j in range(sum_val, vlist[i]-1, -1):
            dp[j] = min(dp[j], dp[j-vlist[i]] + wlist[i]) 
    
    for j in range(sum_val, -1, -1):
        if (dp[j] <= W):
            return j
            break
    

N, W  = map(int, input().split())
vlist = []
wlist = []
for i in range(N):
    v,w = map(int, input().split())
    vlist.append(v)
    wlist.append(w)
print(sack(N,W,vlist,wlist))

Solution (Python):
import bisect

n,W = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [float("INF") for i in range(10001)]
dp[0] = 0
for v,w in b:
    for i in range(10001):
        if 10000-i+v < 10001:
            dp[10000-i+v] = min(dp[10000-i+v], dp[10000-i]+w)
for i in range(1,10000):
    dp[10000-i] = min(dp[10000-i], dp[10001-i])
print(bisect.bisect_right(dp,W)-1)

Solution (Python):
N, W = map(int, input().split())
values = []
weights = []
for i in range(N):
    item = list(map(int, input().split()))
    values.append(item[0])
    weights.append(item[1])
max_value = sum(values)

dp = [[float('inf') for value in range(max_value+ 1)] for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for value in range(max_value+1):
        if value >= values[i]:
            dp[i+1][value] = min(dp[i][value - values[i]] + weights[i], dp[i][value])
        else:
            dp[i+1][value] = dp[i][value]
for value in range(max_value, 0, -1):
    if dp[N][value] <= W:
        print(value)
        exit()
print(0)