Problem:
 Score : 100 points    Problem Statement There are N items, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq N ), Item i has a weight of w_i and a value of v_i .  Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W , which means that the sum of the weights of items taken must be at most W .  Find the maximum possible sum of the values of items that Taro takes home.      Constraints  All values in input are integers.  1 \leq N \leq 100  1 \leq W \leq 10^5  1 \leq w_i \leq W  1 \leq v_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  W  w_1  v_1  w_2  v_2  :  w_N  v_N       Output Print the maximum possible sum of the values of items that Taro takes home.        Sample Input 1 3 8
3 30
4 50
5 60      Sample Output 1 90  Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8 , and the sum of the values is 30 + 60 = 90 .       Sample Input 2 5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000      Sample Output 2 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 3 6 15
6 5
5 6
6 4
6 6
3 5
7 2      Sample Output 3 17  Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14 , and the sum of the values is 6 + 6 + 5 = 17 .

Solution (Python):
import sys

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

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


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

Solution (Python):

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for n in range(N):
    for w in range(W + 1):
        if wv[n][0] <= w:
            dp[n+1][w] = max(dp[n][w], dp[n][w - wv[n][0]] + wv[n][1])
        else:
            dp[n+1][w] = dp[n][w]
print(dp[N][W])

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

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

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

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

dp = [[0]*100100 for i in range(110)]

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

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])    
        
print(dp[N][W])

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


def solve(N, W, WV):
    "void()"
    values = [0] * (W + 1)
    for i in range(N):
        next_values = values[:]
        weight, value = WV[i]
        for j in range(W - weight + 1):
            next_values[j + weight] = max(
                values[j + weight],
                values[j] + value)
        values = next_values
    return max(values)


T1 = """
3 8
3 30
4 50
5 60
"""


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


def _test():
    """
    >>> as_input(T1)
    >>> main()
    90
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = [0]
v = [0]

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

if sum(w) < tw:
    tw = sum(w)

dp = [[0 for i in range(tw+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(1,tw+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-1][j-w[i]])

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

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

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

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

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

Solution (Python):
def knapsack(W,weight,value):
    n = len(weight)
    dp = [[0]*(W+1) for _ in range(n+1)]
    
    for j in range(W):
        dp[0][j] = 0
    for i in range(n):
        for j in range(W+1):
            if weight[i] <= j:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]
    return dp

N,W = map(int,input().split())
values, weights = [],[]
for _ in range(N):
    ｗ,ｖ = map(int,input().split())
    values.append(v)
    weights.append(w)
    
dp = knapsack(W,weights,values)
print(dp[-1][-1])

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

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

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

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

Solution (Python):

n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,capacity+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

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

    for i in range(n):
        for sum_w in range(w+1):
            
            if sum_w - wei[i] >= 0:
                dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - wei[i]] + val[i])

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

    print(dp[n][w])


if __name__ == '__main__':
    main()

Solution (Python):
inf = 2**60
'''
def table(size, init): 
  x = len(size)
  l = [init for i in range(size[x-1])]
  for i in range(x-1):
    l = [l for k in range(size[x-2-i])]
  return l
'''

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

print(max(dp[n]))

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

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

import numpy as np

dp = np.zeros(W + 1, dtype = int)

for i in range(N):
  w,v = map(int,readline().split())
  np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])
  
print(dp.max())

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

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

import numpy as np
dp = np.zeros(W + 1, dtype = int)

for i in range(N):
  w,v = map(int,readline().split())
  np.maximum(dp[:-w] + v,dp[w:],out = dp[w:])

print(dp.max())

Solution (Python):





import sys
input = sys.stdin.readline

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

dp_min = 0                                                      


price_list = [0]
weight_list = [0]

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





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:
            dp[item][weight] = max(dp[item-1][weight], dp[item-1][weight - weight_list[item]] + price_list[item])        

print(dp[M][W])

Solution (Python):
import sys


import math


input = sys.stdin.readline




def main():

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

    dp = [0] * (W+2)

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

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

    print(dp[W])





if __name__ == "__main__":
    main()

Solution (Python):



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

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

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

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def knapsack(sm,W,n,V):
    K = [[0]*(sm+1) for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,sm+1):
            K[i][j] = K[i-1][j]
            if W[i-1] <= j:
                K[i][j] = max(V[i-1]+K[i-1][j-W[i-1]], K[i-1][j])
    return K[n][sm]

n,wt = ip()
V,W = [0]*n,[0]*n
for i in range(n):
    w,v = ip()
    V[i] = v
    W[i] = w
ans = knapsack(wt,W,n,V)
print(ans)

Solution (Python):
II = lambda: int(input())
SI = lambda: input()
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
n,m = MI()
dp = [0]*(m+1)
for i in range(n):
	w,v = MI()
	for j in range(m,w-1,-1):
		dp[j] = max(dp[j-w]+v,dp[j])
print(dp[m])

Solution (Python):
import copy

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

max_v_per_w = [0] * (W+1)
for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(max_v_per_w)
    for j in range(w, W+1):
        max_v_per_w[j] = max(tmp[j], tmp[j-w]+v)
        
print(max(max_v_per_w))

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

w = []
v = []

for x in range(n):
    peso,valor = map(int,input().split())
    w.append(peso)
    v.append(valor)

dp = [0] * (W+1)

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


resposta = 0

for x in dp:
    resposta = max(x,resposta)

print(resposta)

Solution (Python):
import numpy as np

def main_():
    N,W=map(int,input().strip().split())
    l=[]
    for n in range(N):
        l.append(list(map(int,input().strip().split())))
    
    dp=np.zeros(W+1,np.int64)

    for n in range(N):
        w=l[n][0]
        v=l[n][1]
        dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
    return dp.max()

if __name__=="__main__":
    print(main_())

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

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

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

print(table[N][W])

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

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

Solution (Python):

N,W=map(int,input().split())
w_list=[]
v_list=[]

for i in range(N):
    w1,v1=map(int,input().split())
    w_list.append(w1)
    v_list.append(v1)
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_list[i]<=w:
            dp[i+1][w]=max(dp[i][w-w_list[i]]+v_list[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(N)]
x.insert(0, [0, 0])
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for sum_m in range(1, W+1):
        
        if sum_m >= x[i][0]:
            dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m-x[i][0]] + x[i][1])
        
        dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m])
print(dp[N][W])

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

val, wt = [], []
for _ in range(N):
    res = list(map(int, input().split()))
    val.append(res[1])
    wt.append(res[0])

dp = [[0 for _ in range(W + 1)] for _ in range(N+1)]
for n in range(N + 1):
    for w in range(W + 1):
        if n == 0 or w == 0:
            dp[n][w] = 0
        elif wt[n-1] > w:
            
            dp[n][w] = dp[n - 1][w]
        else:
            
            dp[n][w] = max(val[n-1] + dp[n-1][w - wt[n-1]], dp[n-1][w])  
            
            
print(dp[N][W])

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

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

Solution (Python):

import numpy as np
n, W = map(int,input().split())
w = []
v = []
for i in range(n):
    w_,v_= map(int,input().split())
    w.append(w_)
    v.append(v_)
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
	dp[w[i]:] = np.maximum(dp[:-w[i]] + v[i], dp[w[i]:])
print(dp[W])

Solution (Python):
def main():
    n, maxW, weight, value = getInputs()

    accumulatedValue = [0] * (maxW + 1)

    possible = [False] * (maxW + 1)
    possible[0] = True

    used = []
    for i in range(maxW + 1):
        used.append([0] * n)

    for x in range(min(weight), maxW + 1):
        for w in range(n):
            weightW = weight[w]

            if (x - weightW >= 0) and possible[x - weightW] and used[x - weightW][w] == 0:
                newValue = accumulatedValue[x - weightW] + value[w]

                if newValue > accumulatedValue[x]:
                    accumulatedValue[x] = newValue
                    used[x] = used[x - weightW].copy()
                    used[x][w] = 1
                    possible[x] = True

    print(max(accumulatedValue))

def getInputs():
    n, maxW = map(lambda x: int(x), input().split())

    weight, value = [], []
    for i in range(n):
        w, v = map(lambda x: int(x), input().split())
        weight.append(w)
        value.append(v)

    return n, maxW, weight, value

main()

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


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

Solution (Python):
import numpy as np

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

dp = np.zeros(W + 1, np.int64)

for w, v in wv:
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

ans = dp.max()
print(ans)

Solution (Python):
import sys
def main():
    N,W=tuple(map(int,sys.stdin.readline().split()))
    w,v=[0],[0]
    for _ in [0]*N:
        wi,vi=tuple(map(int,sys.stdin.readline().split()))
        w.append(wi)
        v.append(vi)
    dp=[[0 for _ in [0]*(W+1)] for _ in [0]*(N+1)]
    for i in range(1,N+1):
        for j in range(1,W+1):
            dp[i][j]=max(dp[i-1][j], dp[i][j-1])
            if w[i]<=j:dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])
    print(dp[N][W])
if __name__=='__main__':main()

Solution (Python):
def main():
    n, maxW, weight, value = getInputs()

    accumulatedValue = [0] * (maxW + 1)

    possible = [False] * (maxW + 1)
    possible[0] = True

    used = []
    for i in range(maxW + 1):
        used.append([0] * n)

    for x in range(min(weight), maxW + 1):
        for w in range(n):
            weightW = weight[w]

            if (x - weightW >= 0) and possible[x - weightW] and used[x - weightW][w] == 0:
                newValue = accumulatedValue[x - weightW] + value[w]

                if newValue > accumulatedValue[x]:
                    accumulatedValue[x] = newValue
                    used[x] = used[x - weightW].copy()
                    used[x][w] = 1
                    possible[x] = True

    print(max(accumulatedValue))

def getInputs():
    n, maxW = map(lambda x: int(x), input().split())

    weight, value = [], []
    for i in range(n):
        w, v = map(lambda x: int(x), input().split())
        weight.append(w)
        value.append(v)

    return n, maxW, weight, value

main()

Solution (Python):

import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    
    
    

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

    dp = [defaultdict(int)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = sorted(list(dp[i].keys()))
        new_dp = defaultdict(int)
        for key in keys:
            new_dp[key] = max([new_dp[key], dp[i][key]])
            new_w = key + w
            if new_w <= W:
                new_dp[new_w] = max([new_dp[new_w], dp[i][key] + v])

        max_value = 0
        for key in sorted(new_dp.keys()):
            if max_value > new_dp[key]:
                del new_dp[key]
            else:
                max_value = new_dp[key]

        dp.append(new_dp)
    print(max(dp[N].values()))


if __name__ == '__main__':
    main()

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

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
    for sum_w in range(W+1):
        weight = sum_w - wv[i-1][0]
        if weight < 0:
            dp[i][sum_w] = max([dp[i][sum_w], dp[i-1][sum_w]])
        else:
            dp[i][sum_w] = max([dp[i][sum_w], dp[i-1][sum_w], dp[i-1][weight]+wv[i-1][1]])
print(max(dp[N]))

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

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def sub(w, v, b):
    """重みリストw, 価値リストv, 重さ上限bのナップサックを解く
    """
    dp = [0] * (b+1)
    for i in range(len(w)):
        for j in range(b, -1, -1):
            if w[i]<=j:
                dp[j] = max(dp[j], dp[j-w[i]]+v[i])
    return dp
n,w = map(int, input().split())
ws = [None]*n
vs = [None]*n
for i in range(n):
    ws[i], vs[i] = map(int, input().split())
dp = sub(ws, vs, w)
print(dp[w])

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

dp = [0] * (w+1)

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

print(max(dp))

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

w = [0 for i in range(n)]
v = [0 for i in range(n)]

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


dp = []

for i in range(n+1):
    temp = []
    for j in range(k+1):
        temp.append(0)
    dp.append(temp)


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

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

import numpy as np

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

dp = np.zeros(W + 1, dtype = int)
for i in range(N):
  w,v = map(int,readline().split())
  np.maximum(dp[:-w] + v,dp[w:],out = dp[w:])
  
print(max(dp))

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

print(dp[W])

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

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

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

print(dp[n][w])

Solution (Python):
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
dp=[0]*(b+1)
for i in range(a):
  x,y=mi()
  for i in range(b-x,-1,-1):
      dp[i+x]=max(dp[i]+y,dp[i+x])
print(max(dp))

Solution (Python):



n,w=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    f,s=map(int,input().split())
    weight.append(f)
    value.append(s)
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(w+1):
        dp[i][j]=dp[i-1][j]
        if j-weight[i]<0:
            continue
        else:
            dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i])
print(max(dp[n]))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

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

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


for weight in range(W+1):
    if w[0] <= weight:
        dp[0][weight] = v[0]
    else:
        dp[0][weight] = 0



for idx in range(1, N):
    for weight in range(1, W+1):
        
        if weight - w[idx] < 0:
        
            dp[idx][weight] = dp[idx - 1][weight]
            continue

        
        v1 = dp[idx - 1][weight - w[idx]] + v[idx]
        

        
        v2 = dp[idx - 1][weight]

        dp[idx][weight] = max(v1, v2)





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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

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

for idx in range(1, N+1):
    for weight in range(W+1):
        if weight - w[idx - 1] < 0:
            dp[idx][weight] = dp[idx - 1][weight]
            continue

        
        
        v1 = dp[idx - 1][weight - w[idx - 1]] + v[idx - 1]

        
        v2 = dp[idx - 1][weight]

        dp[idx][weight] = max(v1, v2)



print(dp[N][W])

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

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

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

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

Solution (Python):
from sys import stdin, gettrace
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 


def main():
    n,w=map(int,input().split())
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    for i in range(n,-1,-1):
        for j in range(0,w+1,1):
            if i==n or j==0:
                dp[i][j]=0        
            elif li[i][0]>j:
                dp[i][j]=dp[i+1][j]
            else:
                dp[i][j]=max(dp[i+1][j-li[i][0]]+li[i][1],dp[i+1][j])
    print(dp[i][w])
 
 
if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin, gettrace
import sys
sys.setrecursionlimit(1000000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 



def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

def main():
    n,w=[int(x) for x in input().split()]
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    print(recursion(li,0,n,w,dp))
 
 
if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

N, W = map(int, input().split(' '))
items = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = np.zeros(shape=W + 1, dtype=np.int64)

for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value)

print(dp[-1])

Solution (Python):
def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]
    ws, vs = zip(*wv)

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

    for i in range(n):
        for sum_w in range(w + 1):
            if sum_w - ws[i] >= 0:
                dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - ws[i]] + vs[i])
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

    res = max(dp[-1])
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):


LI = lambda: list(map(int, input().split()))


N, W = LI()
WV = [LI() for _ in range(N)]


def main():
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = WV[i - 1]
        for j in range(W + 1):
            if j < w:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
    ans = max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

N,W = get_ints();
arr = [];
for i in range(N):
    tarr = get_array();
    arr.append(tarr);
dp = [[0 for i 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-arr[i-1][0])>=0:
            dp[i][j]=max(dp[i-1][j],arr[i-1][1]+dp[i-1][j-arr[i-1][0]]);
        else:
            dp[i][j]=dp[i-1][j]


print(dp[N][W]);

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

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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

print(int(dp.max()))

Solution (Python):

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: 
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: 
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]






dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)

print(res)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, lim = map(int, readline().split())
WV = np.array(read().split(), np.int64)

W = WV[::2]
V = WV[1::2]


dp = np.zeros(lim + 1, np.int64)
for w, v in zip(W, V):
    np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])
print(dp.max())

Solution (Python):
import numpy as np
n, targw = map(int,input().split())
w = [0 for _ in range(n)]
v = [0 for _ in range(n)]
for i in range(n):
	w[i], v[i] = map(int,input().split())
dp = np.zeros(targw+1, dtype=np.int64)
for i in range(n):
	dp[w[i]:] = np.maximum(dp[:-w[i]] + v[i], dp[w[i]:])
print(dp[targw])

Solution (Python):
"""配列の再利用,numpyの利用の練習"""

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))
import numpy as np

N,W= inpl()
WV = []
for _ in range(N):
    w_v = inpl()
    WV.append(w_v)

dp = np.full(W+1,0,dtype=np.int64)
for i in range(N):
    w = WV[i][0]
    v = WV[i][1]
    np.maximum(dp[w:],dp[:W+1-w]+v,out=dp[w:])

print(np.max(dp))