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


import sys
from collections import namedtuple

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

Item = namedtuple("Item", ("value", "weight"))

def main():
    n, max_w = read_list(int)
    items = []

    for _ in range(n):
        v, w = read_list(int)
        items.append(Item(v, w))
    
    dp = [0] * (max_w + 1)
    for w_i in range(max_w + 1):
        for i in range(len(items)):
            if w_i >= items[i].weight:
                dp[w_i] = max(dp[w_i], dp[w_i - items[i].weight] + items[i].value)
    print(dp[max_w])

if __name__ == "__main__":
    main()

Solution (Python):
n,m=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]*(m+1)
for i in range(n):
    for j in range(1,m+1):
        if j>=w[i]:
            dp[j]=max(dp[j],dp[j-w[i]]+v[i])
print(dp[m])

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

def resolve():
    N, W = map(int, input().split())
    vw = [list(map(int, input().split())) for _ in range(N)]

    
    dp = [0]*(W+1)

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

    print(dp[W])

if __name__ == '__main__':
    resolve()

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

for j in range(N):
  v, w = map(int, input().split())
  value.append(v)
  weight.append(w)

dp = [0] * (W+1)

for k in range(1,W+1):
  dpk = 0
  for m in range(N):
    if(k-weight[m] >= 0):
      tmp = dp[k-weight[m]] + value[m]
      if(tmp > dpk):
        dpk = tmp
  dp[k] = dpk

print(dp[W])

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

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

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 = [0]*(M+1)

for w in range(1, M+1):
    for i in range(N):
        if W[i] <= w:
            DP[w] = max(DP[w], DP[w-W[i]] + V[i])

print DP[M]

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


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

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]




DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(m+1):
        if j < W[i]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = max(DP[i][j], DP[i+1][j-W[i]]+V[i])
print(DP[n][m])

Solution (Python):
import sys,bisect
sys.setrecursionlimit(15000)

n,w = map(int,sys.stdin.readline().split())
a = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dp = [0]*(w+1)

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

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

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

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

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


for i in range(1, N + 1):
    for j in range(1, W + 1):
        if i == 1:
            if j >= weights[i]:
                dps[i][j] = values[i] * (j // weights[i])
        else:
            if j >= weights[i]:
                dps[i][j] = max(dps[i][j - (weights[i])] +
                                values[i], dps[i - 1][j])
                
                
                
                dps[i][j] = max(dps[i][j], dps[i][j - 1])
            else:
                dps[i][j] = max(dps[i][j - 1], dps[i - 1][j])
print(dps[N][W])

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


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

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

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

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

Solution (Python):
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 S(): return input()


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


def MS(): return map(str, 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 make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
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 = False



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

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

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

if __name__ == '__main__':
    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(1,W+1):
        if j - w >= 0:
            dp[j] = max(dp[j],dp[j-w]+v)

print(dp[-1])

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

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

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 for _ in range(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] = max(dp[i][j - w[i]] + v[i], 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):
from collections import defaultdict
N, W = list(map(int, input().split()))

values = []
weights = []

max_w = 0
weight_value_dict = defaultdict(int)
for i in range(N):
    v, w = list(map(int, input().split()))
    weight_value_dict[w] = max(v, weight_value_dict[w])
    values.append(v)
    weights.append(w)


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

for j in range(1, W+1):
    for weight, val in weight_value_dict.items():
        if j < weight:
            continue
        else:
            dp[j] = max(dp[j], dp[j-weight] + val)
print(dp[W])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N,W=map(int,input().split())
    v,w=[0]*N,[0]*N
    for i in range(N):
        v[i],w[i]=map(int,input().split())
    dp=[[0]*2*10**5 for _ in range(N+1)]
    for i in range(N):
        for weight in range(W+1):
            dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight])
            if weight-w[i]>=0:
                dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight-w[i]]+v[i])
                dp[i+1][weight]=max(dp[i+1][weight],dp[i+1][weight-w[i]]+v[i])
    print(dp[N][W])

if __name__ == '__main__':
    main()

Solution (Python):
N,W=map(int,input().split())
v,w=[],[]
for i in range(N):
    t,m=map(int,input().split())
    v.append(t);w.append(m)
dp=[0]*(W+1)
for i in range(1,W+1):
    for k in range(N):
        if(i-w[k]>=0):
            dp[i]=max(dp[i],dp[i-w[k]]+v[k])
print(dp[W])

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    N, W = iip()
    dp = [0] * (W+1)

    for i in range(N):
        v, w = iip()
        for j in range(W+1):
            id = j+w
            if id >= W+1:
                continue
            dp[id] = max(dp[id], dp[j]+v)

    print(dp[-1])











def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    if isinstance(l, list):
        l = l[0] 
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

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

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

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

print(dp[N][W])

Solution (Python):

def main():

    inf = 1<<29
    n,w = map(int,input().split())
    A = []
    for _ in range(n):
        a,b = map(int,input().split())
        A.append([a,b])
    dp = [0]*(w+1)
    for i in range(1,w+1):
        for j in range(n):
            if i-A[j][1]<0:continue
            dp[i] = max(dp[i],dp[i-A[j][1]]+A[j][0])
    res = 0
    for i in range(w+1):res = max(res,dp[i])
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
if __name__ == "__main__":
    N, W = map(int, input().split())
    bag = []
    for _ in range(N):
        v, w = list(map(int, input().split()))
        bag.append((v, w))

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

    for i in range(N):
        iv, iw = bag[i]
        for w in range(iw, W+1):
            if dp[w-iw] == -1:
                continue
            else:
                dp[w] = max(dp[w-iw] + iv, dp[w])

    result = max(dp)

    print(result)

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

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

V=[]
W=[]

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

DP=[[0]*(gw+1) for i in range(n+1)]

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

print(DP[n][gw])

Solution (Python):
n,w = map(int,input().split())
dp = [0]*(w+1)

for i in range(n):
    a,b = map(int,input().split())
    for j in range(w+1):
        if b > j:
            continue
        else:
            dp[j] = max(dp[j] , dp[j-b] + a)
            
print(dp[w])

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


def inpl():
    return list(map(int, input().split()))


N, W = inpl()
VW = [inpl() for _ in range(N)]

dp = [0] * (W + 1)

for w in range(W + 1):
    for i in range(N):
        if w < VW[i][1]:
            continue

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


print(dp[W])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

N, W = na()
weight = [0] * 110
value = [0] * 110
for i in range(N):
    v, w = na()
    weight[i], value[i] = w, v
dp = [[0] * 10010 for _ in range(110)]
for i in range(N):
    for w in range(W+1):
        if w >= weight[i]:
            dp[i+1][w] = max(dp[i+1][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())
vw=[list(map(int,input().split())) for i in range(n)]

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

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,W = mi()
vl=[-1]*(W+1)
w_list=[]
for i in range(n):
    vt,wt =mi()
    if wt>W: continue
    vl[wt] = max(vl[wt], vt)
for k,i in enumerate(vl):
    if i!= -1:
        w_list.append(k)
dp = [0]*(W+1)
for i in w_list:
    w = i
    v = vl[w]
    for i in range(w,W+1):
        dp[i] = max(dp[i],dp[i-w]+v)
print(dp[W])

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

print(dp[W])

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]

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

for i in range(n):
    for j in range(w):
        if j + vw[i][1] < w + 1:
            dp[j + vw[i][1]] = max(dp[j + vw[i][1]], dp[j] + vw[i][0])
print(max(dp))

Solution (Python):








import sys
sys.setrecursionlimit(10 ** 5 + 10)


def resolve():
    N, W = map(int, input().split())
    value, weight = [0] * N, [0] * N
    for i in range(N):
        value[i], weight[i] = map(int, input().split())


    
    
    def knapsack(N, W, weight, value):
        dp = [[0] * (W + 1) for _ in range(N + 1)]

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

        return dp[N][W]

    print(knapsack(N, W, weight, value))




resolve()

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

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

ans = 0

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

print(ans)

Solution (Python):
n, w = map(int, input().split())
V = [0] * n
W = [0] * n
for i in range(n):
    vi, wi = map(int, input().split())
    V[i] = vi
    W[i] = wi
    


dp = [-999999]*(w+1)
dp[0] = 0

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

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

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

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

v=[0]*N
w=[0]*N

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

dp=[0]*(W+1)

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

print(dp[W])

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

value, weight = [], []
for i in range(n):
    a, b = map(int,input().split())
    value.append(a)
    weight.append(b)

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

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

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

print(dp[n][w])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,W = LI()
    g = LIR(n)
    dp = [0]*(W+1)
    for i in range(n):
        v,w = g[i]
        for j in range(W):
            nj = j+w
            if nj <= W:
                nd = dp[j]+v
                if dp[nj] < nd:
                    dp[nj] = nd
    print(dp[W])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def main():

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

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

    print(max(dp[N]))


if __name__ == '__main__':
    main()

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


dp = [0] * (W + 1)

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

    dp[i] = tmp

print(dp[W])

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

Solution (Python):
def main():
    N,W = map(int,input().split(" "))
    dp = [0 for _ in range(W+1)]
    V = [tuple(map(int,input().split(" "))) for _ in range(N)]
    for i in range(W+1):
        for j in range(N):
            v,w = V[j]
            if i-w < 0:continue
            else:
                dp[i] = max(dp[i],dp[i-w]+v)
    print(max(dp))

if __name__ == "__main__":
    main()

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

def main():
    N, W = map(int, input().split())
    vw = [list(map(int, input().split())) for i in range(N)]

    dp = [0] * (W+1)

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

    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):
N,W = map(int,input().split())
VW = [list(map(int,input().split())) for i in range(N)]
Val = [VW[i][0] for i in range(N)]
Wei = [VW[i][1] for i in range(N)]

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(1,W+1):
        if j - Wei[i-1] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i][j-Wei[i-1]]+Val[i-1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

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

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

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

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

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

ans = dp[N][W]
print(ans)

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

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

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

print(dp[N][W])

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

vw = []
for i in range(N):
    vw.append([int(i) for i in input().split(" ")])
value = [i[0] for i in vw]
weight = [i[1] for i in vw]

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

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

print(dp[N][W])

Solution (Python):
def solve():
    n, w = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]
    
    dp = [[float("inf") if i != 0 else 0 for i in range(w+1)] for j in range(n+1)]
    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 k - items[j-1][1] >= 0:
                dp[j][k] = max(dp[j-1][k], dp[j-1][k-items[j-1][1]] + items[j-1][0], dp[j][k-items[j-1][1]] + items[j-1][0])
            else:
                dp[j][k] = dp[j-1][k]

    return dp[-1][-1]

print(solve())

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

DP = [0] * (WE+1)



DP[0] = 0

for i in range(N):
    for j in range(WE+1):
        if j + W[i] <= WE:
            DP[j+W[i]] = max(DP[j+W[i]], DP[j]+V[i])
    

print(DP[WE])

Solution (Python):
def run():
  N, W = map(int, input().split())
  vw = [list(map(int, input().split())) for n in range(N)]
  dp = [0]*(W+1)
  for w in range(W+1):
    for n in range(N):
      if w < vw[n][1]:
        continue
      else:
        dp[w] = max(dp[w], dp[w-vw[n][1]]+vw[n][0])
  print(dp[-1])
    
if __name__ == '__main__':
    run()