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):
n,W=map(int,input().split())
L=[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):
        
        if L[i][1] <=  w:
            dp[i+1][w] = max(dp[i][w - L[i][1]]+L[i][0], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[n]))

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

n, w = map(int, input().split())
items = {i: Item(*map(int, input().split())) for i in range(1, n+1)}
dp = [[i for i in range(w+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(w+1):
    dp[0][i] = 0
for j in range(1, n+1):
    for k in range(1, w+1):
        if 0 <= k - items[j].w:
            dp[j][k] = max(dp[j-1][k], dp[j-1][k-items[j].w] + items[j].v)
        else:
            dp[j][k] = dp[j-1][k]
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)]

values = []
weights = []

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


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

print(dp[N][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)[::-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()
    vw=[LI() for _ in range(n)]
    dp=[0]*(wn+1)
    for v,w in vw:
        for i in range(wn,w-1,-1):
            dp[i]=max(dp[i],dp[i-w]+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 - 1][j - w[i]] + v[i], dp[i - 1][j])
print(dp[N][W])

Solution (Python):
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C[item_w:], C)):
            v1, v2 = vals
            v1 += item_v
            if v1 > v2:
                C[i] = v1
    print(C[0])

solve()

Solution (Python):
from bisect import bisect_left as lower_bound
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N, W = MI()
    v = [0] * N
    w = [0] * N
    dp = [0] * (W + 1)

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

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

    print(dp[W])


if __name__ == '__main__':
    main()

Solution (Python):


import sys




def main():
    n, w = map(int, input().split())
    goods = [(0,0)]*n
    for i, inp in enumerate(sys.stdin):
        v, wtmp = map(int, inp.strip("\n").split())
        goods[i] = (v,wtmp)
    dp = [[0 for i in range(w+1)] for j in range(n)]
    for i in range(n):
        for c in range(w+1):
            if i < 0 or c <= 0: dp[0][0] = 0
            elif c - goods[i][1] < 0: dp[i][c] = dp[i-1][c]
            else: dp[i][c] = max(goods[i][0] + dp[i-1][c-goods[i][1]], dp[i-1][c])
    print(dp[n-1][w])



    
if __name__ == '__main__':
    main()

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

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

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

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

memo = [[-1] * (W + 1) for i in range(N + 1)]
w = 1
v = 0
l = []
for i in range(0, N):
    l.append(list(map(int, input().split())))

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

print(dp[N][W])

Solution (Python):


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

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

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

    for v, w in S:
        for i in range(W-w, -1, -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):
length, weight = (int(n) for n in input().split(" ") )
dp = [0 for n in range(weight + 1)]
for l in range(length):
    v, w = (int(n) for n in input().split(" ") )
    temp = dp[:]
    for i, d in enumerate(dp):
        if d and i + w <= weight:
            temp[i + w] = max(d + v, dp[i + w])
    dp = temp
    dp[w] = max(v, dp[w])
    
print(max(dp))

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

values = [0] * N
weights = [0] * N

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

for i in range(N):
    values[i], weights[i] = map(int, input().split())

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

print(dp[N][W])

Solution (Python):
import operator
import functools


@functools.lru_cache(10**9)
def dynamic_planning(item_taken, target_weight):
    if item_taken == 0 or target_weight == 0:
        return 0
    value, weight = items[item_taken-1]
    if weight <= target_weight:
        ret = max(dynamic_planning(item_taken-1, target_weight-weight) + value, dynamic_planning(item_taken-1, target_weight))
    else:
        ret = dynamic_planning(item_taken-1, target_weight)
    return ret


N, W = map(int, input().split(" "))
items = list()
for _ in range(N):
    items.append(list(map(int, input().split(" "))))
items = sorted(items, key=operator.itemgetter(0))
print(dynamic_planning(N, W))

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

Solution (Python):

 
def rec1 (n,w): 
    v = 0
 
    if dp[n][w] > 0:
        return dp[n][w]
 
    if n == N: 
        v = 0
    elif items[n][1] > w: 
        v = rec1(n + 1 ,w)
    else: 
        c1 = rec1(n + 1, w ) 
        c2 = rec1(n + 1, w - items[n][1]) + items[n][0]
        v = max( c1,c2)
    dp[n][w] = v
    return v
 
 
 
 

 
N, W = map(int, input().split())
items = [ tuple(map(int, input().split()) )for _ in range(N)]
maxW = maxV = -1
for item in items:
    v,w = item
    maxW = max(maxW,w)
    maxV = max(maxV,v)


 
 
if maxW <= 1000:
    dp = [[-1] * 200001 for _ in range(N + 1)]
    rec1(0, W)
    print(dp[0][W])
elif maxV <= 1000:
    INF = 10 ** 18
    dp = [INF] * 200001
    dp[0] = 0
    for item in items:
        v, w = item
        for j in range(200000,v-1,-1):
            dp[j] = min( dp[j - v] + w ,dp[j])
    for j in range(200000, - 1, -1):
        if dp[j] <= W:
            print(j)
            break

Solution (Python):



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

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


solve()

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

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

print(dp[N][W])

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

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

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

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


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

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

for _ in range(num_item):
    value,weight = map(int,input().split())
    for i in range(W,weight-1,-1):
        if dp[i-weight] == -BIG_NUM:
            continue
        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):
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]

if __name__ == '__main__':
    N,W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        va,we = map(int, input().split())
        weight.append(we)
        value.append(va)
    print(knapsack(N,W,weight,value))

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

print(dp[N][W])

Solution (Python):


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

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

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

Solution (Python):









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




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




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






from itertools import product
for i, w in product(range(N), range(W + 1)):
    dp[i + 1][w] = dp[i][w]
    value, weight = items[i]
    if w - weight >= 0:
        dp[i + 1][w] = max(dp[i][w], dp[i][w - weight] + value)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='darwin':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

N, W = MAP()
v = [0] * N
w = [0] * N
for i in range(N):
	v[i], w[i] = MAP()

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

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


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
        dp_prev = dp[:]
        while ww <= weight:
            dp[ww] = max(dp_prev[ww], dp_prev[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):




def knaspsack(V,W,n,w):
    V = [0] + V ; W = [0] + W
    dp = [[0]*(w+1) for i in range(n+1)]
    for i in range(1, n+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])
    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(knaspsack(V,W,n,w))

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-1][w-tw]+tv)
        DP[n][w] = max(DP[n][w],DP[n-1][w])
print(DP[N][W])

Solution (Python):
from collections import defaultdict
N, W = list(map(int, input().split()))

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

dp = dict()

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

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

Solution (Python):
N, totalWt = list(map(int, input().split()))
itemsVal = [0]
itemsWt = [0]
for i in range(0, N):
    val, weight = list(map(int, input().split()))
    itemsVal.append(val)
    itemsWt.append(weight)

mylist = [[0 for _ in range(totalWt+1)] for _ in range(N + 1)]


for i in range(1, N + 1):
    for j in range(1, totalWt+1):
        if j >= itemsWt[i]:
            mylist[i][j] = max(mylist[i-1][j], mylist[i-1][j-itemsWt[i]] + itemsVal[i])
        else:
            mylist[i][j] = mylist[i-1][j]

print(mylist[len(itemsWt)-1][totalWt])

Solution (Python):
def main():
    n_max, w_max = map(int, input().split())

    v_list = []
    w_list = []
    for i in range(n_max):
        v, w = map(int, input().split())
        v_list.append(v)
        w_list.append(w)

    dp = [[0] * (w_max + 1) for _ in range(n_max + 1)]
    
    for i in range(n_max-1, -1, -1):
        
        for j in range(w_max + 1):
            if j < w_list[i]:
                dp[i][j] = dp[i+1][j]
            else:
                temp0 = dp[i+1][j]
                temp1 = dp[i+1][j - w_list[i]] + v_list[i]
                dp[i][j] = max(temp0, temp1)

    print(dp[0][w_max])


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][1] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][1]]+li[i][0])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))

Solution (Python):
def knapsack(N, W, l):    
    dp = [[0]*(W+1) for _ in range(N+1)]
    for j in range(1, W+1):
        for i in range(1, N+1):
            v = l[i-1][0]
            w = l[i-1][1]
            if j-w < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
    return dp[N][W]

N, W = [int(_) for _ in input().split()]
l = [[0]* 2 for _ in range(N)]
for i in range(N):
    l[i][0],l[i][1] = [int(_) for _ in input().split()]
ans = knapsack(N, W, l)
print(ans)

Solution (Python):
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    v.append(x)
    w.append(y)
dp = [[0 for i in range(W+1)] for j in range(n+1)]

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

Solution (Python):
def main():
    N, W = (int(i) for i in input().split())
    v = []
    w = []
    for i in range(N):
        a, b = (int(i) for i in input().split())
        v.append(a)
        w.append(b)
    done = [[False for i in range(W+1)] for j in range(N+1)]
    memo = [[0 for i in range(W+1)] for j in range(N+1)]

    def dp(i,u):
        if done[i][u]: 
            return memo[i][u]
        if i == N:
            return 0
        elif u < w[i]:
            return dp(i + 1, u)
        else:
            res1 = dp(i + 1, u)
            res2 = dp(i + 1, u - w[i]) + v[i]
            res = max(res1,res2)
            done[i][u] = True
            memo[i][u] = res
            return res

    print(dp(0,W))

if __name__ == '__main__':
    main()

Solution (Python):
"""
item: ２次元配列 item[i] = [weight, value]
bounds: size of knapsack
"""
def knapsack(item, bounds):
    n = len(item)
    dp_table = [[0] * (bounds+1) for i in range(n)]
    for w in range(1,bounds+1):
        if item[0][0] > w:
            continue
        dp_table[0][w] = item[0][1]

    for i in range(1,n):
        for w in range(W+1):
            if item[i][0] > w:
                dp_table[i][w] = dp_table[i-1][w]
            else:
                dp_table[i][w] = max(dp_table[i-1][w], dp_table[i-1][w-item[i][0]] + item[i][1])
    return dp_table[n-1][bounds]


N, W = map(int, input().strip().split())
item = []
for i in range(N):
    value, weight = map(int, input().strip().split())
    item.append([weight, value])

print(knapsack(item, 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(n):
    vi,wi=map(int,input().split())
    for j in range(w+1):
        if(j >= wi):
            dp[i+1][j] =max(dp[i][j-wi]+vi,dp[i][j])
        else:
            dp[i+1][j] =dp[i][j]

print(dp[n][w])

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

v = []
w = []

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

"""
つまり、
dp[i][vv][ww] = {max(dp[i+1][vv+v[i]][ww-w[i]] | dp[i+1][vv][ww]}
となる？
価値を保存するから vv が消えると
dp[i][ww] = {max(dp[i+1][ww-w[i]]+v[i] | dp[i+1][ww]}
となる。
これは、実質、価値であるから
"""

def rec(i, vv, ww):
    if i == N:
        return vv
    ans = 0
    
    if ww >= w[i]:
        ans = rec(i+1, vv+v[i], ww-w[i])
    
    ans = max(ans, rec(i+1, vv, ww))
    return ans

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

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 = [['.' for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):  
    dp[N][i] = 0

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

print(dp[0][W])

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

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

Solution (Python):
num ,endu = map(int,input().split())

arr = [[0]*(endu+1) for i in range(num+1)]

value = [0]
weight = [0]
for i in range(num):
    val, wei = map(int,input().split())
    value.append(val)
    weight.append(wei)

for i in range(1,num+1):
    
    for j in range(1,endu+1):
        if j >= weight[i]:
            arr[i][j] = max(arr[i-1][j-weight[i]]+value[i],arr[i-1][j])
        else:
            arr[i][j] = arr[i-1][j]

print(arr[num][endu])

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,-1):
		x=l[i-w]+v
		if x>l[i]:l[i]=x
print(l[W])

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

N, W = map(int, input().split())
A = [Item(*list(map(int, input().split()))) for i in range(N)]
A = [Item(0, 0)] + A
dp = [[0 for i in range(W+1)] for j in range(N+1)]

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

print(maximum)

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

def knapsack(i , j):
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i , j):
        if dp[i][j] != -1:
            return dp[i][j]
        if i == N:
            retval = 0
        elif j < weight[i]:
            retval = solve(i + 1 , j)
        else:
            retval = max(solve(i + 1 , j) , solve(i + 1 , j - weight[i]) + value[i])
        dp[i][j] = retval
        return retval
    ans = solve(0,W)
    return ans

if __name__ == "__main__":
    print(knapsack(0 , W))

Solution (Python):
n,W=map(int,input().split())
vw=[list(map(int,input().split())) for _ in [0]*n]
memo=[0]*(W+1)
for i in range(n):
    v,w=vw[i]
    for j,k in enumerate(memo[W-w::-1]):
        memo[W-j]=max(v+k,memo[W-j])
print(max(memo))

Solution (Python):
s = list(map(int,input().split()))
N = s[0]
W = s[1]

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

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

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



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


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

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-1][j-w]+v)
print(dp[N][W])

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

Solution (Python):
import time,sys
sys.setrecursionlimit(1000000000)


def search(i,j):

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

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

N,W = map(int,input().split())
res=0
items=[]
for i in range(N) :
    array =list(map(int,input().split()))
    items.append(array)

memo=[[-1 for i in range(W+1)] for j in range(N+1)]


knapsack=0
print(search(0,W))

Solution (Python):

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

weight_value = []

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

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



for i in range(N):
    value = weight_value[i][0]
    weight = weight_value[i][1]
    
    
    for j in range(W + 1):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        
        next_weight = j + weight
        next_value = dp[i][j] + value
        
        if (next_weight <= W and next_value > dp[i+1][next_weight]):
            dp[i+1][next_weight] = next_value

            

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

print(dp[N][W])

Solution (Python):

n, w = map(int, input().split())
zaq = [tuple(map(int, input().split())) for _ in range(n)]
memo = [[-1] * n for _ in range(w+1)]

def dfs(i, w):
    if i == n:
        return 0
    elif memo[w][i] >= 0:
        return memo[w][i]
    elif w < zaq[i][1]:
        return dfs(i+1, w)
    else:
        res1 = dfs(i+1, w)
        res2 = dfs(i+1, w - zaq[i][1]) + zaq[i][0]
        res = max(res1, res2)
        memo[w][i] = res
        return res
print(dfs(i=0, w=w))

Solution (Python):
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)
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

    for i in range(N):
        value, weight = items[i]
        for j in range(W + 1):
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
            next_weight = j + weight
            next_value = dp[i][j] + value
            if (next_weight <= W and next_value > dp[i + 1][next_weight]):
                dp[i + 1][next_weight] = next_value

    print(max(dp[N]))

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(W, a[1] - 1, -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):
    v,t = map(int, input().split( ))
    V.append(v)
    W.append(t)



Pos = [[0 for w2 in range(w+1)] for j in range(n)]
Able = []

for i in range(n):
     for w1 in range(w+1):
         if w1 >= W[i]:
             Pos[i][w1] = max(Pos[i-1][w1-W[i]] + V[i], Pos[i-1][w1])
             
         else:
             Pos[i][w1] = Pos[i-1][w1]
         if Pos[i][w1] > 0:
            Able.append(Pos[i][w1])



print(Able[-1])

Solution (Python):
from typing import List, NamedTuple
import pprint

pp = pprint.PrettyPrinter()


class Baggage(NamedTuple):
    value: int
    weight: int


def knapsack(
    total_weight: int, n_baggages: int, baggages: List[Baggage]
) -> int:

    T: List[List[int]] = [
        [0] * (n_baggages + 1) for _ in range(total_weight + 1)
    ]

    for n in range(1, n_baggages + 1):
        for t in range(1, total_weight + 1):
            v = T[t][n - 1]
            b = baggages[n - 1]
            if t >= b.weight:
                v_use = T[t - b.weight][n - 1] + b.value
                v = max(v, v_use)
            T[t][n] = v
        

    return T[total_weight][n_baggages]


def main() -> None:
    N, W = [int(x) for x in input().split()]

    B: List[Baggage] = []
    for _ in range(N):
        v, w = (int(x) for x in input().split())
        B.append(Baggage(v, w))

    print(knapsack(W, N, B))


main()

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