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


def main():
    input = sys.stdin.buffer.readline
    n, W = map(int, input().split())
    v = [0] * (n + 1)
    w = [0] * (n + 1)
    for i in range(1, n + 1):
        v_i, w_i = map(int, input().split())
        v[i], w[i] = v_i, w_i
    
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[n][W])


if __name__ == "__main__":
    main()

Solution (Python):
n,w=map(int,input().split())
vlst=[0 for _ in range(n+1)]
wlst=[0 for _ in range(n+1)]

for i in range(1,n+1):
    x,y=map(int,input().split())
    vlst[i],wlst[i]=x,y

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

print(dp[n][w])

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

for _ in range(n):
    v, w = map(int, input().split())
    for i in range(w, cap + 1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(max(dp))

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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





def main():
    n, w = ns()
    d = []
    for _ in range(n):
        tmp = na()
        d.append(tmp)

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

    for vi, wi in d:
        for i in range(w+1):
            if dp[i] > -1 and i + wi < w + 1:
                dp[i + wi] = max(dp[i + wi], dp[i] + vi)

    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N, W = map(int, input().split())

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


if __name__ == '__main__':
    resolve()

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

dp = [ [0]*(W+1) for _ in range(N+1) ]
for i in range(1, N+1):
  val,wei = items[i-1]
  for w in range(W+1):
    if w >= wei:
      dp[i][w] = max(dp[i-1][w], dp[i][w-wei]+val)
    else:
      dp[i][w] = max(dp[i-1][w], dp[i][w-1])

print(dp[N][W])

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7


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

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

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

print(dp[W])

Solution (Python):
N,W=map(int,input().split())
vw=[list(map(int,input().split())) for _ in range(N)]
DP=[[0 for i in range(10001)] for j in range(100)]
for idx in range(N):
    for weight in range(10001):
        if weight<vw[idx][1]:
            DP[idx][weight]=DP[idx-1][weight]
        else:
            DP[idx][weight]=max(DP[idx][weight-vw[idx][1]]+vw[idx][0],DP[idx-1][weight])

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

Solution (Python):

import sys
input = sys.stdin.readline



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

price_list = [0]
weight_list = [0]
for _ in range(M):
    price, weight = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)




dp_min = 0                                                      


dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                 

for item in range(M+1):                                         
    dp[item][0] = 0                                             





for item in range(1,M+1):                                       
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          
            dp[item][weight] = dp[item - 1][weight]
        else:
            temp = dp[item - single][weight - weight_list[item]] + price_list[item]  
            if temp > dp[item-1][weight]:
                dp[item][weight] = temp
            else:
                dp[item][weight] = dp[item-1][weight]

print(dp[M][W])

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

Solution (Python):



n, w = map(int, input().split())
vw_l = [[int(x) for x in input().split()] for y in range(n)]

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

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

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

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

print(dp[W])

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

dp = [0] * (W+1)

value = []
weight = []

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

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

print(dp[W])

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

print(max(dp[n]))

Solution (Python):
def solve():
    N, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*(W+1)
    for w in range(1,W+1):
        for i in range(N):
            if A[i][1]<=w:
                dp[w] = max(dp[w],dp[w-A[i][1]]+A[i][0])
    ans = dp[-1]
    return ans
print(solve())

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


dp=[[-float('inf')]*(W+1) for i in range(N+1)]
for i in range(W+1):
    dp[0][i]=0
for i in range(1,N+1):
    dp[i][0]=0

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

print(dp[N][W])

Solution (Python):
def main():
    _, W, *C = map(int, open(0).read().split())
    dp = [0]*(W+1)
    for v, w in zip(*[iter(C)]*2):
        for i in range(w, W+1):
            d_new = dp[i-w]+v
            if dp[i] < d_new:
                dp[i] = d_new
    print(max(dp))

if __name__ == '__main__':
    main()

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


def main():
    N, W = map(int, readline().rstrip().split())
    dp = [0] * (W + 1)

    for _ in range(N):
        v, w = map(int, readline().rstrip().split())
        for j in range(W-w+1):
            dp[j+w] = max(dp[j+w], dp[j] + v)

    print(dp[-1])


if __name__ == '__main__':
    main()

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

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

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, WM = 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] * (WM + 1)

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

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


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

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

Solution (Python):


from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


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




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

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


print(dp[W])

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

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

value = []
weight = []

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

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

print(dp[N][W])

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

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



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

for i in range(N+1):
    for w in range(W+1):
        if i == 0:
            dp[i][w] = 0
            continue
        if w == 0:
            dp[i][w] = 0
            continue
        if product[i][0] > w:
            dp[i][w] = dp[i-1][w]
        else:
            not_choice = dp[i-1][w]
            choice = dp[i-1][w-product[i][0]] + product[i][1]
            same_choice = dp[i][w-product[i][0]] + product[i][1]
            dp[i][w] = max(not_choice, choice, same_choice)
print(max(dp[N]))

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

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

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

for i in range(N):
    for j in range(W + 1):
        v, w = vw[i]

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

        if j >= w:
            dp[i + 1][j] = max(dp[i + 1][j - w] + v, dp[i][j])


print(dp[N][W])

Solution (Python):
"""何回でも同じ荷物を選べるナップザック問題"""
def main():
    N,W = map(int, input().split())
    v,w = [],[]
    for i in range(N):
        a,b = map(int, input().split())
        v.append(a)
        w.append(b)
    
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(W+1):
            if j-w[i-1]>=0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1])
                dp[i][j] = max(dp[i][j], dp[i][j-w[i-1]]+v[i-1])
            dp[i][j] = max(dp[i][j], dp[i-1][j])
    print(dp[N][W])

main()

Solution (Python):
def solve(N,W,knap):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(0,N):
        v,w=knap[i]
        for j in range(w,W+1):
            if dp[j-w]!=-1:
                dp[j]=max(dp[j],dp[j-w]+v)
    return max(dp)

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

Solution (Python):
def main():
    N, W = map(int, input().split())
    
    items = [tuple(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 items[i][1] > w:
                dp[i+1][w] = dp[i][w]
            else:
                dp[i+1][w] = max(dp[i][w], dp[i+1][w-items[i][1]]+items[i][0])
    print(max(dp[N]))
    """
    """ 使い回す方 """
    dp = [0]*(W+1)
    for i in range(N):
        for w in range(W+1):
            if items[i][1] <= w:
                dp[w] = max(dp[w], dp[w-items[i][1]]+items[i][0])
    print(max(dp))


if __name__ == "__main__":
    main()

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

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

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

Solution (Python):
def solve(N, W, vals, weights):
    dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if weights[i] <= w:
                dp[i + 1][w] = max(dp[i + 1][w - weights[i]] + vals[i], dp[i][w])
            else:
                dp[i + 1][w] = dp[i][w]
    print(dp[N][W])

if __name__ == "__main__":
    N, W = map(int, input().split())
    vals = []
    weights = []
    for _ in range(N):
        v, w = map(int, input().split())
        vals.append(v)
        weights.append(w)
    solve(N, W, vals, weights)

Solution (Python):



import sys
import math

N, W = map(int, sys.stdin.readline().strip().split())

item = []
for n in range(N):
    v, w = map(int, sys.stdin.readline().strip().split())
    item.append((v, w))



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


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





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

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

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

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

print(dp[N % 2][W])

Solution (Python):
n, w = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]



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


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

print(dp[n][w])

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

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


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

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

print(dp[N][W])

Solution (Python):
nn,ww=map(int,input().split())
value=[0]*nn
weight=[0]*nn
for i in range(nn):
    value[i],weight[i]=map(int,input().split())    

dp=[[0]*(ww+1) for i in range(nn+1)]
for w in range(ww+1):
    dp[0][w]=0
    
for i in range(nn):
    for w in range(ww+1):
        if w-weight[i]>=0:
            dp[i+1][w]=max(dp[i][w],dp[i][w-weight[i]]+value[i],dp[i+1][w-weight[i]]+value[i])
        else:
            dp[i+1][w]=dp[i][w]

print(dp[nn][ww])

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

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

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

print(dp[W])

Solution (Python):
n, w_max = map(int, input().split())
X = []
for _ in range(n):
    X.append(list(map(int, input().split())))

W = [0] * (w_max + 1)

for i in range(len(W)):
    for x in X:
        xv, xw = x[0], x[1]
        if i - xw >= 0:
            W[i] = max(W[i], W[i - xw] + xv)

print(max(W))

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

dp = [0] * (W + 1)

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

print(dp[W])

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

for _ in range(N):
    vi, wi = map(int, input().split())
    ndp = [0] * (W+1)
    for j in range(W+1):
        if j < wi:
            ndp[j] = dp[j]
        else:
            ndp[j] = max(dp[j], ndp[j-wi] + vi)
    dp = ndp 
print(dp[W])

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

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



dp = [[0]*(10**4+10) for _ in range(110)]
def rec(i,w):
    dp[i+1][w] = dp[i][w] 

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

for i in range(N):
    for j in range(W+1):
        rec(i,j)
print(dp[N][W])

Solution (Python):
if __name__ == "__main__":
    n, w_size = map(int, input().split())
    v = []
    w = []
    for _ in range(n):
        vi, wi = map(int, input().split())
        v.append(vi)
        w.append(wi)
    
    dp = [[0] * (w_size + 1)] * n

    for i in range(1, w_size + 1):
        dp[0][i] = v[0] * (i // w[0])
    
    for i in range(1, n):
        for j in range(1, w_size + 1):
            dp[i][j] = dp[i-1][j]
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i])
    print(dp[n-1][w_size])

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

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

Solution (Python):
n, w = map(int, input().split())
listV, listW = [], []
for i in range(n):
    vi, wi = map(int, input().split())
    listV.append(vi)
    listW.append(wi)

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

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

print(dp[n][w])

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

dp = [0] * (W + 1)

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

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

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

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

def main():
    N,W = map(int,input().split())
    item = [tuple(map(int,input().split())) for _ in range(N)]
    dp = [0]*(W + 1)
    for v,w in item:
        for j in range(w,W + 1):
            dp[j] = max(dp[j],dp[j - w] + v)
    print(dp[-1])
if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,W,*vw = map(int, read().split())

    VW = []
    for v, w in zip(*[iter(vw)]*2):
        VW.append((v, w))

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

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

    print(dp[N][W])    


if __name__ == "__main__":
    main()

Solution (Python):


def solve():
    import sys

    N, W = list(map(int, sys.stdin.readline().split()))

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

    for _ in range(N):
        v, w = list(map(int, sys.stdin.readline().split()))

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

    print(dp[W])


if __name__ == "__main__":
    solve()

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

dp = [0] * (w + 1)

weight = []
value = []
for _ in range(n):
    v, we = map(int, input().split())
    weight.append(we)
    value.append(v)







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



print(dp[w])

Solution (Python):
n, w = map(int, input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)

dp = [0] * (w+1)

for i in range(w+1):
    for value, weight in items:
        x = i + weight
        if x > w:
            continue
        dp[x] = max(dp[i] + value, dp[x])

print(dp[w])

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

dp = [0]*(W+1)
L = []
for i in range(N):
    ta,tb = map(int,input().split())
    L.append([ta,tb])

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

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

value,weight = [],[]
for i in range(N):
    v,w = map(int,input().split())
    value.append(v)
    weight.append(w)
    
dp = [[0 for i in range(W+10)] for j in range(N+10)]    





















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

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

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

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

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)

dp[0] = 0

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

print(dp[W])

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

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

for i in range(1,1+N):
    for j in range(10100):
        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][WI])

Solution (Python):
import sys

N, W = map(int, sys.stdin.readline().strip().split())
weights = []

for _ in range(N):
    v, w = map(int, sys.stdin.readline().strip().split())
    weights.append((v, w))

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

print(max(dp))

Solution (Python):

def main():
    N, W = map(int, input().split())
    DP = [-1]*(W+1)
    DP[0] = 0
    for i in range(N):
        v, w = map(int, input().split())
        for j in range(w, W+1):
            if DP[j-w] == -1:
                continue
            else:
                DP[j] = max(DP[j], DP[j-w] + v)
    
    ans = 0
    for k in range(W+1):
        ans = max(ans, DP[k])
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline
    
    
    N, W = map(int, input().split())
    item = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = float('inf')
    dp = [-INF] * (W + 1)
    dp[0] = 0
    for i in range(N):
        v, w = item[i]
        for j in range(W + 1 - w):
            dp[j + w] = max(dp[j] + v, dp[j + w])
    
    print(max(dp))


if __name__ == "__main__":
    main()

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


def knapsack_duplicate(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 w >= weight[i]:
                dp[i+1][w] = max(dp[i][w-weight[i]] + value[i],
                                 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_duplicate(N, W, ws, vs))

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 _ in range(N + 1)]
DP[0][W] = 0

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

Solution (Python):
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

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

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

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

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


"""
  dp[i + 1][j] i番目までの品物から，総和がj以下になるように選んだときの最大値
  - dp[0][j] = 0
  - dp[i+1][j] = max{ dp[i][j - k w[i]] + k v[i] | 0 <= k}
"""

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

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

Solution (Python):
n,w=map(int,input().split())
VW=[list(map(int,input().split())) for _ in range(n)]

DP=[0]*(w+1)
for i in range(w+1):
    for volume,weight in VW:
        if 0<=i+weight<=w:
            DP[i+weight]=max(DP[i+weight],DP[i]+volume)
print(max(DP))