Problem:
Knapsack Problem You have N kinds of 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.  You can select as many items as possible into a knapsack for each kind.  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 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 ≤ 1000  1 ≤ w i ≤ 1000  1 ≤ W ≤ 10000  Sample Input 1 4 8
4 2
5 2
2 1
8 3 Sample Output 1 21 Sample Input 2 2 20
5 9
4 10 Sample Output 2 10 Sample Input 3 3 9
2 1
3 1
5 2 Sample Output 3 27

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

dp = [0]*(W+1)
for i in range(N):
    for j in range(W+1):
        if j < Weight[i]:
            continue
        dp[j] = max(dp[j], dp[j-Weight[i]]+Value[i])

print(dp[W])

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

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

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

print(dp[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():
    n,wn=MI()
    dp=[0]*(wn+1)
    for _ in range(n):
        v,w=MI()
        for i in range(wn):
            if i+w>wn:break
            dp[i+w]=max(dp[i+w],dp[i]+v)
    print(dp[-1])

main()

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




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

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()))
    dp = [[0] * (w+5) for _ in range(n+5)]
    items = [[] for _ in range(n)]
    for i in range(n):
        items[i] = list(map(int, input().strip().split()))
    for i in range(1, n+1):
        for j in range(1, w+1):
            if j-items[i-1][1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-items[i-1][1]]+items[i-1][0])
    print(dp[n][w])

if __name__ == '__main__':
    main()

Solution (Python):


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

def resolve():
    N, W = iim()
    S = [iim() for i in range(N)]

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

if __name__ == "__main__":
    resolve()

Solution (Python):





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

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

print(ans)

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

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

for _ in range(N):
    value,weight = map(int,input().split())
    for i in range(weight,W+1):
        if dp[i-weight] == -1:
            pass
        else:
            dp[i] = max(dp[i],dp[i-weight]+value)

ans = 0
for i in range(W+1):
    ans = max(ans,dp[i])

print(ans)

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



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

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

print(dp[N-1][W])

Solution (Python):
n,W=map(int,input().split())
v=[]
w=[]
for i in range(n):
    vv,ww=map(int,input().split())
    v.append(vv)
    w.append(ww)
dp=[[-1]*(W+1) for i in range(n+1)]
for i in range(W+1):
    dp[0][i]=0
for i in range(n):
    for j in range(W+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][W])

Solution (Python):



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

vw = []

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


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

for i in range(N):
    for j in range(W+1):

        if vw[i][1] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j - vw[i][1]] + vw[i][0])


print(dp[-1][-1])

Solution (Python):
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

"""
配列再利用によりdpの次元削減を行うパターン
"""

N, W = MAP()

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

for _ in range(N):
	v, w = MAP()
	for sum_w in range(W+1):
		
		if sum_w >= w:
			dp[sum_w] = max(dp[sum_w-w]+v, dp[sum_w])
		else:
			dp[sum_w] = dp[sum_w]


print(dp[-1])

Solution (Python):
N, W = map(int, input().split())
vw = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  for j in range(W+1):
    if j - vw[i][1] >= 0:
      dp[i+1][j] = max(dp[i+1][j-vw[i][1]]+vw[i][0], dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]

print(dp[N][W])

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


def knapsack(N, weight):
    dp = [0] * (weight + 1)
    for _ in range(N):
        v, w = map(int, readline().split())
        ww = w
        while ww <= weight:
            dp[ww] = max(dp[ww], dp[ww - w] + v)
            ww += 1
    return dp[-1]

if __name__ == "__main__":
    n_goods, weight = map(int, input().split())
    print(knapsack(n_goods, weight))

Solution (Python):
N,W = map(int,input().split())
Data = []
for _ in range(N):
    v,w = map(int,input().split())
    Data.append([v,w])
Data.sort(key=lambda x:x[1])
DP = [[0]*(W+1) for _ in range(N+1)]

for n in range(1,N+1):
    for w in range(1,W+1):
        tv,tw = Data[n-1]
        if tw <= w:
            DP[n][w] = max(DP[n][w],DP[n][w-tw]+tv)
        DP[n][w] = max(DP[n][w],DP[n-1][w])
print(DP[N][W])

Solution (Python):
def main():
    N, W = (int(i) for i in input().split())
    dp = [0] * (W + 1)
    for _ in range(N):
        v, w = (int(i) for i in input().split())
        for j in range(w, W+1):
            dp[j] = max(dp[j], dp[j-w]+v)
    print(dp[W])


if __name__ == "__main__":
    main()

Solution (Python):

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

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

print(max(dp))

Solution (Python):
n,W,*t=map(int,open(0).read().split())
dp=[[0]*(W+1)for _ in range(n+1)]
for i,(v,w)in enumerate(zip(*[iter(t)]*2),1):
  for j in range(W+1):
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v,dp[i][j-w]+v)if j-w>=0else dp[i-1][j]
print(dp[n][W])

Solution (Python):


N, W = map(int, input().split())
v = []; w = []

for i in range(N):
    vv, ww = map(int, input().split())
    v.append(vv); w.append(ww)

"""
def rec(pos, rest):
    if pos == N:
        return 0
    ans = 0
    for i in range(0, rest//w[pos]+1):
        ans = max(ans, rec(pos+1, rest-w[pos]*i)+v[pos]*i)
    return ans

print(rec(0, W))
"""

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

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

Solution (Python):
n,w=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(1,n+1):
    vi,wi=map(int,input().split())
    for j in range(1,w+1):
        if(j<wi):
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j-wi]+vi,dp[i-1][j],dp[i][j-wi]+vi)
print(dp[n][w])

Solution (Python):
n,w=map(int,input().split())
a=[0]*(w+1)
for i in range(n):
    s,t=map(int,input().split())
    for j in range(t,w+1):
        a[j]=max(a[j-t]+s,a[j])
print(a[-1])

Solution (Python):
_,W,*L=map(int,open(0).read().split())
l=[0]*(W+1)
for v,w in zip(*[iter(L)]*2):
	for i in range(w,W+1):
		l[i]=max(l[i],l[i-w]+v)
print(l[W])

Solution (Python):
def main():
    n,W=map(int,input().split())
    vw=[list(map(int,input().split())) for _ in [0]*n]
    memo=[0]*(W+1)
    for i in range(W):
        for v,w in vw:
            if i+w<=W:
                memo[i+w]=max(memo[i+w],memo[i]+v)
    print(max(memo))  
        
if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
dp = [[0 for i in range(W+1)] for j in range(N+1)]

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

Solution (Python):
import sys


if __name__ == "__main__":
    N, W = map(lambda x: int(x), input().split())
    items = [(0, 0)] * N
    for i in range(N):
        v, w = map(lambda x: int(x), input().split())
        items[i] = (v, w)
    table = [-sys.maxsize] * (W + 1)
    table[0] = 0

    for weight in range(W):
        for idx in range(N):
            if (-sys.maxsize == table[weight]):
                continue
            if (weight + items[idx][1] <= W):
                table[weight + items[idx][1]] = max(
                    table[weight + items[idx][1]], table[weight] + items[idx][0])

    print(max(table))

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

v = []
w = []

for i in range(n):
    v1, w1 = map(int, input().split( ))
    v.append(v1)
    w.append(w1)

DP = [0]*(w_max + 1)

w_tmp = 0
while w_tmp <= w_max:
    v_tmp = DP[w_tmp]
    for i in range(n):
        if w[i] <= w_tmp:
            v_tmp = max(DP[w_tmp - w[i]] + v[i], v_tmp)
        DP[w_tmp] = v_tmp
    w_tmp += 1

print(DP[w_max])

Solution (Python):
N, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(W + 1)]

for a in A:
  for j in range(a[1], W + 1):
    dp[j] = max(dp[j], dp[j - a[1]] + a[0])
print(max(dp))

Solution (Python):
n,W=map(int,input().split())
v=[]
w=[]
for i in range(n):
    val,wei=map(int,input().split())
    v.append(val)
    w.append(wei)

dp=[-1]*(W+1)
dp[0]=0
for i in range(n):
    for j in range(W+1):
        if dp[j]!=-1 and j+w[i]<W+1:
            dp[j+w[i]]=max(dp[j]+v[i],dp[j+w[i]])

print(max(dp))

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

Solution (Python):


def solve():
    n, w = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0] * (w+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, w+1):
            item = items[i-1]
            if j - item[1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-item[1]] + item[0])

    print(dp[-1][-1])


if __name__ == "__main__":
    solve()

Solution (Python):
length, weight = map(int, input().split(" "))
dp = [0 for n in range(weight + 1)]

for i in range(length):
    v, w = map(int, input().split(" "))

    dp[w] = max(v, dp[w])
    for j in range(weight):
        if dp[j] and j + w <= weight:
            dp[j + w] = max(dp[j] + v, dp[j + w])

print(max(dp))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,W=MAP()
VW=[]
for i in range(N):
    v,w=MAP()
    VW.append((v, w))

dp=list2d(N+1, W+1, 0)
for i in range(1, N+1):
    v,w=VW[i-1]
    for j in range(W+1):
        dp[i][j]=max(dp[i][j], dp[i-1][j])
        if j-w>=0:
            
            dp[i][j]=max(dp[i][j], dp[i-1][j-w]+v, dp[i][j-w]+v)
print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
goods = []
for i in range(N):
    goods.append(list(map(int, input().split())))
dp = [[0 for i in range(W+1)]]
for n in range(0, N):
    dp.append([0])
    g = goods[n]
    for w in range(1, W+1):
        if w>=g[1]:
            dp[-1].append(max(dp[-1][w-g[1]]+g[0],dp[-2][w]))
        else:
            dp[-1].append(dp[-2][w])
print(dp[-1][-1])

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N, W = readi(2)
    vs, ws = zip(*readi(N, 2))
    dp = arr(N + 1, W + 1)
    for i in range(N):
        for j in range(W + 1):
            if j - ws[i] >= 0:
                dp[i + 1][j] = max(
                    dp[i + 1][j], dp[i][j - ws[i]] + vs[i], dp[i + 1][j - ws[i]] + vs[i]
                )
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    print(dp[N][W])


if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, W = MAP()
vw = [LIST() for _ in range(N)]

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

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

print(dp[N][W])

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

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

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

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


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

dp = [0]*(w + 1)
for i in range(n):
    for j in range(w + 1):
        if j - info[i][1] < 0:
            continue
        else:
            dp[j] = max(dp[j], dp[j - info[i][1]] + info[i][0])
print(dp[w])

Solution (Python):

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

dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

for i in range(n + 1):
    for j in range(w + 1):
        if j == 0:
            dp[i][j] = 0
        elif i == 0:
            dp[i][j] = 0
        else:
            if j - vw[i - 1][1] >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - vw[i - 1][1]] + vw[i - 1][0])
            else:
                dp[i][j] = dp[i - 1][j]

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

print(ans)

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

items = []

def knapsack(n):
    for i in range(0, n + 1):
        res = 0
        for v, w in items:
            if i >= w:
                res = max(res, dp[i - w] + v)
        dp[i] = res
    return dp[n]

line = input()
E, W = list(map(int, line.split()))
for _ in range(0, E):
    line = input()
    v, w1 = list(map(int, line.split()))
    items += [[v, w1]]
dp = [0] * (W + 1)
used = [False] * E
knapsack(W)
print(dp[W])

Solution (Python):
N, W = [int(x)for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))
dp = [0]*(W+1)

for i in range(N):
    v, w = items[i]

    for j in range(w,W+1):
        dp[j] = max(dp[j],dp[j-w]+v)
       

print(dp[-1])

Solution (Python):
def solve(N, W, data):
    """
    >>> solve(4, 8, [(4, 2), (5, 2), (2, 1), (8, 3)])
    21
    >>> solve(2, 20, [(5, 9), (4, 10)])
    10
    >>> solve(3, 9, [(2, 1), (3, 1), (5, 2)])
    27
    """
    dp = [0] * (W + 1)

    for v, w in data:
        for i in range(w, W + 1):
            dp[i] = max(dp[i - w] + v, dp[i])

    return dp[-1]


if __name__ == '__main__':
    N, W = map(int, input().split())
    data = [tuple(map(int, input().split())) for _ in range(N)]
    print(solve(N, W, data))

Solution (Python):
N,W=map(int,input().split())
dp=[0 for i in range(W+1)]

L=[]
for i in range(N):
    v,w=map(int,input().split())
    for j in range(len(dp)):
        if j+w>W:
            pass
        else:
            if dp[j+w]<dp[j]+v:
                dp[j+w]=dp[j]+v
print(dp[W])

Solution (Python):
N,W = map(int, input().split())
VW  = [list(map(int, input().split())) for _ in range(N)]
VW  = sorted(VW, key=lambda x:x[1])



dp = [0] * (W+1) 

for i in range(W):
    for v,w in VW:
        
        if i+w <= W:
            dp[i+w] = max(dp[i+w], dp[i]+v) 


print( max(dp) )

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

for i in range(N):
  for w in range(1, W+1):
    if w - wl[i] < 0:
      dp[i+1][w] = dp[i][w]
    else:
      dp[i+1][w] = max(dp[i][w], dp[i+1][w-wl[i]] + vl[i])
      
print(dp[N][W])

Solution (Python):
N,W=map(int,input().split())
nap=[]
for i in range(N):
    nap.append(list(map(int,input().split())))
list_dp=[0]*(W+1)
for i in range(W):
    for j,k in nap:
        if i+k>W:continue
        else:list_dp[i+k]=max(list_dp[i+k],list_dp[i]+j)
print(list_dp[W])

Solution (Python):
def dump(dp, max_w):
    for i in range(max_w + 1):
        print('%3d' % dp[i], end='')
    print()

inf = 1 << 60
max_n, max_w = map(int, input().split())
v = [0] * (max_n + 1)
w = [0] * (max_n + 1)
for i in range(1, max_n + 1):
    v[i], w[i] = map(int, input().split())

dp = [0] * (max_w + 1)

for n in range(1, max_n + 1):
    for i in range(max_w + 1 - w[n]):
        dp[i+w[n]] = max(dp[i+w[n]], dp[i] + v[n])
    

print(dp[max_w])

Solution (Python):
class DP2D(object):

    def __init__(self, item_n: int, border: int, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" + \
               "table:\n" + self.__str__()

    def solve(self, expr: callable) -> list:
        raise NotImplementedError

    def fill_0_idx_with(self, value: int) -> "DP2D":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


class DP2DOptimizer(DP2D):

    def __init__(self, item_n: int, border: int, obj_coef: list, sbj_coef: list, initializer: int = 0):
        super(DP2DOptimizer, self).__init__(item_n, border, initializer=initializer)

        if len(obj_coef) == self.item_n:  
            obj_coef = [0] + obj_coef
        self.obj_coef = obj_coef

        if len(sbj_coef) == self.item_n:
            sbj_coef = [0] + sbj_coef
        self.sbj_coef = sbj_coef

    def solve(self, expr: callable) -> list:
        for weight_lim in range(1, self.border + 1):
            for item_idx in range(1, self.item_n + 1):
                self.table[weight_lim][item_idx] = expr(weight_lim, item_idx)

        return self.table

    def knapsack_expr(self, weight_lim: int, item_idx: int) -> int:
        res = self.table[weight_lim][item_idx - 1]
        if weight_lim - self.sbj_coef[item_idx] >= 0:
            res = max(res, self.table[weight_lim - self.sbj_coef[item_idx]][item_idx] + self.obj_coef[item_idx])
        return res


if __name__ == '__main__':
    N, W = map(int, input().split())
    v, w = [], []
    for _ in range(N):
        buff = [int(i) for i in input().split()]
        v.append(buff[0])
        w.append(buff[1])
    dp = DP2DOptimizer(N, W, v, w)
    print(dp.solve(dp.knapsack_expr)[W][N])

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

dp = [0] * (W + 1)

for i in range(1, N + 1):
    v, w = [int(x) for x in input().split()]
    for j in range(w, W + 1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[W])

Solution (Python):

"""
Created on Sat Jan  5 09:20:15 2019

@author: maezawa
"""

n, maxw = list(map(int, input().split()))
v = [0]*(n+1)
w = [0]*(n+1)
for i in range(1, n+1):
    vi, wi = list(map(int, input().split()))
    v[i] = vi
    w[i] = wi
    
dp = [0]*(maxw+1)
for i in range(1,maxw+1):
    candidates = [dp[i-w[j]]+v[j] 
                    for j in range(n+1) if i-w[j] >= 0]
    dp[i] = max(candidates)
    
print(dp[maxw])

Solution (Python):



from operator import itemgetter


def max_value(total_weight, items):
    values = [0] * (total_weight+1)

    for v, w in sorted(items, key=itemgetter(1)):
        for i in range(w, total_weight+1):
            values[i] = max(values[i], values[i-w] + v)

    return values[-1]


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



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


value = {0: 0}

for u in range(1, W + 1):
    value[u] = max([value[u - w] + v for v, w in item if u >= w] \
                 + [value[u - 1]])
print(value[W])

Solution (Python):
n,W=map(int,input().split())
wt=[0]*n
val=[0]*n
for x in range(n):
    va,wei=map(int,input().split())
    wt[x]=wei
    val[x]=va
    
def knapsack(n,W,wt,val):
    memo=[0]*(W+1)
    for w in range(1,W+1):
        for i in range(n):
            if wt[i]<=w:
                memo[w]=max(memo[w-wt[i]]+val[i],memo[w])                
    return memo[W]
print(knapsack(n,W,wt,val))

Solution (Python):
N, W = map(int, input().split())
objects = [tuple(map(int, input().split())) for i in range(N)]

dp = {(0, j):0 for j in range(W + 1)}

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

print(dp[(N, W)])

Solution (Python):

def knapsack(n,W,v,w):
	dp=[[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(n):
		vl = v[i]
		wt = w[i]
		for j in range(W+1):
			if j < w[i]:
				dp[i+1][j]=dp[i][j]
			else:
				dp[i+1][j]=max(dp[i][j],max(dp[i][j-wt]+vl,dp[i+1][j-wt]+vl))
	return dp[n][W]

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())
print(knapsack(n,W,v,w))

Solution (Python):
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
dp = [0 for i in range(W+1)]
for i in range(N):
    for j in range(goods[i][1], W+1):
        dp[j] = max(dp[j-goods[i][1]] + goods[i][0], dp[j])
print(dp[W])

Solution (Python):
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


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

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

for loop in range(N):
    value,weight = map(int,input().split())
    for i in range(weight,W+1):
        if dp[i-weight] == -1:
            pass
        else:
            dp[i] = max(dp[i],dp[i-weight]+value)

ans = 0
for i in range(W+1):
    ans = max(ans,dp[i])

print("%d"%(ans))

Solution (Python):
N,W = map(int, input().split())
val_i = [0]*(W+1)
for i in range(1,N+1):
    v,w = map(int, input().split())
    copy = val_i[:] 
    for j in range(1,W+1):
        if (w <= j):
            val_i[j] = max(copy[j], (val_i[j-w] + v)) 
                                               
            
            
            
            
print(val_i[-1])

Solution (Python):
n, w = [int(i) for i in input().split()]
V, W = zip(*[[int(i) for i in input().split()] for j in range(n)])

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

for i in range(n):
    for j in range(w+1):
        if W[i] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-W[i]]+V[i], dp[i+1][j-W[i]]+V[i])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])

Solution (Python):
n,wmax=map(int,input().split(" "))
v=[]
w=[]
ans=[0]*(wmax+1)
for i in range(n):
    vv,ww=map(int,input().split(" "))
    v.append(vv)
    w.append(ww)
for i in range(n):
    for j in range(w[i],wmax+1):
        ans[j]=max([ans[j],ans[j-w[i]]+v[i]])
print(ans[-1])

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

dp = [[0 for w in range(W+1)] for i in range(N+1)]
for w in range(W+1):
    dp[0][w] = 0
for i in range(N):
    for w in range(W+1):
        if items[i][1] <= w:
            dp[i+1][w] = max(dp[i+1][w-items[i][1]] + items[i][0], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])