Problem:
0-1 Knapsack Problem 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 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 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):


def solve():
    INF = 1e+9
    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-1][j-item[1]] + item[0])

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


if __name__ == "__main__":
    solve()

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

dp = [[-1]*(M+1) for _ in range(N+1)]
def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]

    if i == N:
        res = 0
    elif j < W[i]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1,j), rec(i+1,j-W[i]) + V[i])

    dp[i][j] = res
    return res

print rec(0, M)

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

Solution (Python):
n,w=map(int,input().split())
items=[[0,0]]
for i in range(n):
  items.append(list(map(int,input().split())))
c=[[0 for i in range(w+1)]for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,w+1):
    if items[i][1]<=j:
      if items[i][0]+c[i-1][j-items[i][1]]>c[i-1][j]: 
        c[i][j]=items[i][0]+c[i-1][j-items[i][1]]
      else:
        c[i][j]=c[i-1][j]
    else:
      c[i][j]=c[i-1][j]
print(c[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 sum_w in range(W+1):
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
        if sum_w + w[i] > W:
            continue
        dp[i+1][sum_w+w[i]] = max(dp[i+1][sum_w+w[i]], dp[i][sum_w] + v[i])

print(max(dp[N]))

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

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


for n in range(N): 
    for w in range(W+1):
        vn, wn = K[n]
        if wn > w: 
            dp[w][n] = dp[w][n-1]
        else: 
            dp[w][n] = max(dp[w][n-1], vn+dp[w-wn][n-1]) 

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

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

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

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

    products = []
    for i in range(N):
        products.append([int(num) for num in input().split()])

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

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

    print(dp[N][W])

if __name__ == '__main__':
    main()

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] = max(dp[i + 1][j], dp[i][j])

    print(dp[N][W])


if __name__ == "__main__":
    main()

Solution (Python):
w = []
v = []
n, W = map(int, input().split())

dp = [[None for i in range(W+1)] for j in range(n+1)]

for i in range(n):

    v2, v1 = map(int, input().split())
    w.append(v1)
    v.append(v2)




def knap(i, j):
    
    
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:

        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        
        
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]


print(knap(0, W))

Solution (Python):
dp = {}

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

value = []
weight = []

for w in range(0, W+1):
    dp[(0, w)] = 0

for i in range(n):
    s = list(map(int, input().split()))

    value.append(s[0])
    weight.append(s[1])

for i in range(n):
    for w in range(0, W+1):

        if w >= weight[i]:
            dp[(i+1, w)] = max(dp[(i, w - weight[i])] + value[i], dp[(i, w)])
        else:
            dp[(i+1, w)] = dp[(i, w)]

print(dp[(n, W)])

Solution (Python):



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

v = []
w = []
for _ in range(N):
    a, b = map(int, input().split())
    v.append(a)
    w.append(b)

memo = [[-1] * (W + 1) for _ in range(N+1)]


def rec(i, j):

    if memo[i][j] >= 0:
        return memo[i][j]

    
    if (i == N):
        res = 0
    
    elif (j < w[i]):
        res = rec(i + 1, j)
    else:
        
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    
    memo[i][j] = res
    return res

print(rec(0, W))

Solution (Python):


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

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

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

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(N):
    v, w = map(int, input().split())
    for j in range(W):
        if j+1 >= w:
            dp[i+1][j+1] = max(dp[i][j+1-w]+v, dp[i][j+1])
        else:
            dp[i+1][j+1] = dp[i][j+1]

print(dp[N][W])

Solution (Python):
def larger(x, y):
	if x > y: return x
	return y

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

Solution (Python):

import functools


def memorized(f):
    table = {}
    @functools.wraps(f)
    def wrapper(*args):
        if args in table:
            return table[args]
        rvalue = f(*args)
        table[args] = rvalue
        return rvalue
    return wrapper


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

@memorized
def knapsack(i, r):
    if i == N:
        return 0
    if r < w[i]:
        return knapsack(i + 1, r)
    return max(knapsack(i + 1, r), v[i] + knapsack(i + 1, r - w[i]))

print(knapsack(0, W))

Solution (Python):

N,W = list(map(int,input().split()))
vw = [list(map(int,input().split())) for i in range(N)]
value = [i[0] for i in vw]
weight = [i[1] for i in vw]

inf=float("inf")
dp = [[-inf for _ in range(W+1)] for _ in range(N+1)]

dp[0] = [0]*(W+1)
def main():
    for i in range(N):
        w = 0
        while w <= W:
            if weight[i] <= w:
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
            w+=1
main()
print(dp[N][W])

Solution (Python):
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+1)]

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

Solution (Python):
def knapsack_weight(W, items):
    '''
        W (int): the capacity of a knapsack
        items (list of tuples): i-th element is a tuple (weight, value)
    '''
    N = len(items)
    
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i in range(1, N+1):
        w, v = items[i-1]
        for j in range(W+1):
            if j - w >= 0:
                dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[N][W]

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

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 - 1][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):
items = []
dp = []

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

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) for _ in range(0, E + 1)]
knapsack(W, E)
print(dp[E][W])

Solution (Python):
N,W=(int(x) for x in input().split())
value=[]
weight=[]
for n in range(N):
    a,b=(int(x) for x in input().split())
    value.append(a)
    weight.append(b)
def knap(N,W,value,weight):
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N+1):
        for w in range(W+1):
            if i>0:
                if weight[i-1]<=w:
                    dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight[i-1]]+value[i-1])
                else:
                    dp[i][w]=dp[i-1][w]
    return dp[N][W]
print(knap(N,W,value,weight))

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

dp=[[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
    for m in range(1,W+1):
        if VW[n-1][1]>m:
            dp[n][m]=dp[n-1][m]
        else:
            dp[n][m]=max(dp[n-1][m],dp[n-1][m-VW[n-1][1]]+VW[n-1][0])
print(dp[-1][-1])

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 reversed(range(w,W+1)):
        dp[j] = max(dp[j],dp[j-w]+v)

print(dp[-1])

Solution (Python):

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

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

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

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

Solution (Python):
n,w = map(int,input().split())
L = []
for i in range(n):
  L.append(list(map(int,input().split())))
dp = []
for i in range(n+1):
    T = [0]*(w+1)
    dp.append(T)
for i in range(n-1,-1,-1):
    for j in range(w+1):
        if j < L[i][1]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-L[i][1]]+L[i][0])
print(dp[0][w])

Solution (Python):
n,w = map(int,input().split())
s = []
check = [[0 for b in range(w+1)] for a in range(n)]
for i in range(n):
  s.append(list(map(int,input().split())))

for j in range(n): 
  for k in range(1,w+1):
    if k < s[j][1]: 
      check[j][k] = check[j-1][k] 
    else:
      check[j][k] = max(check[j-1][k],check[j-1][k-s[j][1]]+s[j][0])   
print(max(check[n-1]))

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

lst = []
for i in range(N):
    a = list(map(int, input().split()))
    lst += [a]

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

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



print (dp[0][W])

Solution (Python):
def larger(x, y):
	if x > y: return x
	else: return y

N, W = map(int, raw_input().split())
dp = []
for i in range(0, N+1):
	lst = []
	for j in range(0, W+1):
		lst.append(0)
	dp.append(lst)
items = []
for i in range(0, N):
	items.append(map(int, raw_input().split()))
weight = W
for i in range(0, N):
	for w in range(0, W+1):
		if items[i][1] <= w:
			dp[i+1][w] = larger(dp[i][w-items[i][1]]+items[i][0], dp[i][w])
		else: dp[i+1][w] = dp[i][w]

print dp[N][W]

Solution (Python):
from collections import*
N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    v,w=map(int,input().split())
    for p,q in d.copy().items():
        if p+w<=W:
            d[p+w]=max(d[p+w],v+q)

print(max(d.values()))

Solution (Python):
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(N):
    for w in range(W+1):
        dp[i+1][w] = max(dp[i][w-items[i][1]] + items[i][0], dp[i][w]) if w >= items[i][1] else dp[i][w]
print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
vw = [[0, 0]]+[list(map(int, input().split())) for _ in range(N)]
'''
ナップザック問題
i番目までの品物で作れる価値の最大値を求めていく
'''
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):
        v = dp[i-1][j]
        if j >= vw[i][1]:
            t = dp[i-1][j-vw[i][1]] + vw[i][0]
            if t > v:
                v = t
        dp[i][j] = v
print(dp[N][W])

Solution (Python):
def main():
    n, w = map(int, input().split(" "))
    items = []
    for _ in range(n):
        items.append(list(map(int, input().split(" "))))

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

    for i in range(n):
        val = items[i][0]
        wei = items[i][1]
        for j in range(w + 1):
            if i == 0:
                if j >= wei:
                    memo[i][j] = val
            else:
                if j >= wei:
                    memo[i][j] = max(
                        memo[i - 1][j],
                        memo[i - 1][j - wei] + val,
                    )
                else:
                    memo[i][j] = memo[i - 1][j]
    return memo[n - 1][w]


if __name__ == '__main__':
    print(main())

Solution (Python):
def knapsack(N,W,weight,value):
  
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
  
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: 
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: 
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

n,q = map(int,input().split()) 
li = [input().split() for i in range(n)]
w=[0]*n
v=[0]*n
for i in range(n):
  v[i]=int(li[i][0])
  w[i]=int(li[i][1])
print(knapsack(n,q,w,v))

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 _ in range(N+1)]  

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

        dp[i+1][w] = max(dp[i+1][w] , dp[i][w])



print( max(dp[N]) )

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

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


for i in reversed(range(n)):

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

print(dp[0][W])

Solution (Python):
N , W = map(int , input().split())
lst = [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):
    for j in range(W + 1):
        if lst[i][1] <= j :
            dp[i+1][j] = max(dp[i][j], dp[i][j-lst[i][1]]+lst[i][0])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

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

t = [tuple(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 >= t[i][1]:
            dp[i+1][j] = max(dp[i][j-t[i][1]]+t[i][0], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
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())))
search_m=[[0 for i in range(N+1)] for j in range(W+1)]
for i in range(N)[::-1]:
    for j in range(W+1):
        search_m[j][i]=search_m[j][i+1]
        if j+nap[i][1]>W:
            continue
        else:
            search_m[j][i]=max(search_m[j][i],search_m[j+nap[i][1]][i+1]+nap[i][0])
print(max(search_m[0]))

Solution (Python):
N,W=list(map(int, input().split()))
v=[list(map(int, input().split())) for i in range(N)]
v.sort(key=lambda x: x[1])
q=[[0 for i in range(W+1)] for j in range(N+1)]


for i,x in  enumerate(v):
    for j in range(1,W+1):
        
        if x[1]<=j:
            q[i+1][j]=max([q[i][j],x[0]+q[i][j-x[1]]])
            
        else:
            q[i+1][j]=q[i][j]
        
print(q[N][W])

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

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

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

res = -1
for i in range(W+1):
    for j in range(N+1):
        res = max(res, dp[j][i])

print(res)

Solution (Python):
def dump(dp, max_n, max_w):
    for n in range(max_n + 1):
        for i in range(max_w + 1):
            print('%3d' % dp[n][i], end='')
        print()
    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 _ in range(max_n + 1)]

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

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

print(dp[max_n][max_w])

Solution (Python):
from typing import Callable


class DynamicProgramming(object):

    table: list
    obj_coef: list
    sbj_coef: list

    def __init__(self, item_n: int, border: int):
        self.item_n = item_n
        self.border = border

    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, obj_coef: list, sbj_coef: list, expr: Callable[[int, int], int], initializer=0) -> list:
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

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

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

        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 - 1] + self.obj_coef[item_idx])
        return res


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

    dp = DynamicProgramming(N, W)
    print(dp.solve(v, w, dp.knapsack_expr)[W][N])

Solution (Python):
class Item(object):
    def __init__(self, value, weight):
        self.v = value
        self.w = weight


n, W = map(int, input().split())
dp = [[-1] * (W + 1) for i in range(n + 1)]
items = [[int(x) for x in input().split()] for j in range(n)]


def rec_dp(i: int, w: int) -> int:
    if dp[i][w] != -1:
        return dp[i][w]

    result = 0
    if i < 0:
        pass
    else:
        item = Item(items[i][0], items[i][1])
        if w - item.w < 0:
            result = rec_dp(i - 1, w)
        else:
            result = max(
                rec_dp(i - 1, w),
                rec_dp(i - 1, w - item.w) + item.v
            )

    dp[i][w] = result
    return result


def main() -> None:
    print(rec_dp(n - 1, W))


if __name__ == "__main__":
    main()

Solution (Python):
import math
import sys
from operator import itemgetter








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


dp = [[0 for j in range(10001)] for i in range(101)]

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

print(dp[N][W])

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

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

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

print(dp[N][W])

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

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

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 reversed(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 = map(int, input().split())
items = []

for i in range(n):
    items.append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0 for i in range(w + 1)] for j in range(n + 1)]
    g = [["TOP" for i in range(w + 1)] for j in range(n + 1)]

    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = "DIAGONAL"

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

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = "TOP"
            item = items[i - 1]
            if item[1] > j:
                continue
            if item[0] + c[i - 1][j - item[1]] > c[i - 1][j]:
                c[i][j] = item[0] + c[i - 1][j - item[1]]
                g[i][j] = "DIAGONAL"

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == "DIAGONAL":
            routes.append(i)
            w -= items[i - 1][1]

    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)

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 = {u: 0 for u in range(W + 1)}


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

print(value[W])

Solution (Python):
n, w = map(int, input().split(" "))
value, weight = zip(*[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):
	for j in range(1, 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]


print(dp[n][w])

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

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

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

print(dp[(0, 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(W, goods[i][1]-1, -1):
        dp[j] = max(dp[j-goods[i][1]] + goods[i][0], dp[j])
print(dp[W])

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

value = []
weight = []

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

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

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

print(dp[w])

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((v + copy[j-w]), copy[j])
print(val_i[-1])

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

dp = [[0 for j in range(W+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())

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

    print(dp[0][W])


if __name__ == '__main__':
    main()

Solution (Python):
class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight


def conpute(N, W, items):
    c = [[None] * (W + 1) for i in range(N + 1)]
    c[0] = [0] * (W + 1)
    for i in range(1, N + 1):
        c[i][0] = 0
    
    for i in range(1, N + 1):
        for w in range(1, W + 1):
            c[i][w] = c[i - 1][w]
            if items[i].weight > w:
                continue
            if items[i].value + c[i - 1][w - items[i].weight] > c[i - 1][w]:
                c[i][w] = items[i].value + c[i - 1][w - items[i].weight]

    maxValue = c[N][W]

    return maxValue

if __name__ == '__main__':
    N, W = [int(v) for v in input().split()]
    items = [Item(0, 1 << 30)]
    for i in range(N):
        v, w = [int(v) for v in input().split()]
        items.append(Item(v, w))
    print(conpute(N, W, items))

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])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])

Solution (Python):
N, W = map( int, input().split())
VS, WS = [], []
for _ in range(N):
    a, b = map( int, input().split())
    VS.append(a)
    WS.append(b)
dp = [ [ 0 for _ in range(10**5+1)] for _ in range(N+1) ]
for i in range(N):
    w = WS[i]
    v = VS[i]
    for j in range(W+1):
        if w <= j:
            dp[i+1][j] = max( dp[i][j-w] + v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

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

print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
values = []
weights = []
for _ in range(N):
    vi, wi = map(int, input().split())
    values.append(vi)
    weights.append(wi)

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

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-1, -1, -1):
  for j in range(w+1):
    if j<vw[i][1]:
      dp[i][j] = dp[i+1][j]
    else:
      dp[i][j] = max(dp[i+1][j], dp[i+1][j-vw[i][1]]+vw[i][0])

print(dp[0][w])