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

N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

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

N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

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 - 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):
INF = float('inf')
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

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

Solution (Python):

import sys
from collections import defaultdict


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

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



ans = [[0]*(w+1) for i in range(n)]


for i in range(n):
  for j in range(0,w+1):
    if i == 0 and j >= l[0][0]:
      ans[0][j] = l[0][1]
    elif i > 0:
      new_w = j + l[i][0]
      if new_w <= w:
        ans[i][new_w] = max(ans[i-1][new_w], ans[i-1][j] + l[i][1])
    if ans[i][j] < ans[i-1][j]:
      ans[i][j] = ans[i-1][j]
        

print(ans[n-1][w])

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 (j-wv[i][0]) >= 0:
            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 sys

n, w = [int(x) for x in input().split(" ")]

wv_list = []

for i in range(n):
  wv_list.append([int(x) for x in input().split(" ")])

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

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

Solution (Python):
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
print(int(dp[W]))

Solution (Python):
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

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

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

for i,(w,v) in enumerate(LIS, 1):
    for wb in range(0, W+1):
        DP[i][wb] = DP[i-1][wb]
        if wb >= w :
            DP[i][wb] = max(DP[i][wb], DP[i-1][wb-w]+v)

print(DP[N][W])

Solution (Python):
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

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

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

for i,(w,v) in enumerate(LIS, 1):
    for wb in range(0, W+1):
        DP[i][wb] = DP[i-1][wb]
        if wb >= w :
            DP[i][wb] = max(DP[i][wb], DP[i-1][wb-w]+v)



print(DP[N][W])

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

for i, wv in enumerate(wvs):
    for j in range(W+1):
        if i == 0:
            if wv[0] < j+1:
                dp[0][j] = wv[1]
        elif wv[0] < j+1:
            dp[i][j] = max(dp[i-1][j-wv[0]] + wv[1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

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

Solution (Python):
n,W=map(int,input().split())
w,v=[],[]
dp=[[0]*(W+1) for i in range(n+1)]
for i in range(n):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)
for i in range(n):
    for w_sum in range(1,W+1):
        if w_sum - w[i]>=0:
            dp[i+1][w_sum]=max(dp[i][w_sum],dp[i][w_sum - w[i]]+v[i])
        else:
            dp[i+1][w_sum]=dp[i][w_sum]
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 w, v in WV:
	for tw in range(W, w - 1, -1):
		dp[tw] = max(dp[tw], dp[tw - w] + v)
	
print(max(dp))

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

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

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

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
dp=[[0]*-~W for _ in range(n+1)]
for i in range(1,n+1):
    t=g[i]
    for j in range(W+1):
        if j-t[0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[0]]+t[1])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))
"""))

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


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

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

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

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

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

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

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

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

Solution (Python):


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

for i in range(N):
    for sum_w in range(W+1):


        if sum_w-wv_l[i][0] >= 0:
            DP[i+1][sum_w] = max(DP[i+1][sum_w],DP[i][sum_w-wv_l[i][0]]+wv_l[i][1])
        DP[i+1][sum_w] = max(DP[i+1][sum_w],DP[i][sum_w])
        
print(DP[N][W])

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

dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

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

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

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

Solution (Python):
n, w = map(int, input().split())
goods = [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 0 <= j - goods[i][0]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - goods[i][0]] + goods[i][1])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[n][w])

Solution (Python):

import sys
input = sys.stdin.readline

n, w = list(map(int, input().rstrip().split()))
arr = [tuple(map(int, input().rstrip().split())) for _ in range(n)]
dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, arr[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][1])
print(max(dp))

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

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

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

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

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

print(max(dp[N]))

Solution (Python):
n, w = map(int, input().split())
goods = [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 0 <= j - goods[i][0]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - goods[i][0]] + goods[i][1])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[n][w])

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

Solution (Python):


N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

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

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

print(dp[N][W])

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

import numpy as np
ndp = np.zeros(W+1,dtype= np.int64)

for w,v in zip(w,v):
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])

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

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

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

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

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

print(max(dp[n]))

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


main()

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


main()

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

Solution (Python):
import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = np.array([[0 for j in range(W+1)] for _ in range(N+1)])
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.maximum(dp[i-1, :-w] + v, dp[i-1, w:])
print(dp[N, W])

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(W + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= j - cw :
                dp[i+1][j] = max(dp[i+1][j], dp[i][j - cw] + cv)
    return max(dp[-1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    print(result)

if __name__ == '__main__':
    main()

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

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

print(dp[N][W])

Solution (Python):
import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1)
for _ in range(N):
  w,v = map(int,input().split())
  dp[w:]=np.maximum(dp[w:], dp[:-w]+v)
print(int(max(dp)))

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

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

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

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

Solution (Python):

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

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

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

print(max(dp))

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

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

Solution (Python):
from itertools import accumulate

N,W = [int(i) for i in input().split()]
H = [[int(i) for i in input().split()] for _ in range(N)]

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

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

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

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

wv.sort()
wv.reverse()

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

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

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

dp = Counter()
dp[0] = 0

for _ in range(N):
    w, v = map(int, sys.stdin.readline().split())
    for k, x in dp.copy().items():
        if k + w <= W:
            dp[k + w] = max(dp[k + w], x + v)

print(max(dp.values()))

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

Solution (Python):
import fileinput


def knapsack(capacity, item_weights, item_values):
    no_current_item_values = [0] * (capacity + 1)
    for i, val in enumerate(item_values):
        with_current_item_values = [0] * (capacity + 1)
        for current_capacity in range(1, capacity + 1):
            if current_capacity < item_weights[i]:
                with_current_item_values[current_capacity] = no_current_item_values[current_capacity]
            else:
                with_current_item_values[current_capacity] = max(
                    no_current_item_values[current_capacity],
                    no_current_item_values[current_capacity - item_weights[i]] + val
                )
        no_current_item_values = with_current_item_values

    return no_current_item_values[-1]


inp = fileinput.input()

first_line_split = inp.readline().split(" ")

item_count = int(first_line_split[0])
capacity = int(first_line_split[1])

item_weights = []
item_values = []
for _ in range(item_count):
    split = inp.readline().split(" ")
    item_weights.append(int(split[0]))
    item_values.append(int(split[1]))

print(knapsack(capacity, item_weights, item_values))

Solution (Python):
n,W = map(int, input().split())
l = [dict() for i in range(n+1)]
l[0][0] = 0
for i in range(1,n+1):
  w,v = map(int, input().split())
  l[i] = l[i-1].copy()
  l[i][w] = max(l[i].get(w,0),v)
  for x in l[i-1]:
    if x+w <= W:
      l[i][x+w] = max(l[i].get(x+w,0),l[i-1][x] + v)
print(max(l[n].values()))

Solution (Python):
def dpcalc():
    global n, w
    dp = [0] * (w + 1)      

    for i in range(n):      
        wt, vl = map(int, input().split())
        for j in range(w, wt - 1, -1):
            tmp = dp[j - wt] + vl
            if tmp > dp[j]:
                dp[j] = tmp
    return dp[w]


if __name__ == "__main__":
    
    n, w = map(int, input().split())
    print(dpcalc())

Solution (Python):
def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]
 
num, capacity = map(int, input().split())
print(calc(num,capacity))

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

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

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

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

print(dp[N][W])

Solution (Python):


n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] 

dp = [0]*(W+1)
dp[0]=0
newdp = [0]*(W+1)
for i in range(n):
    w, v = wv[i]
    for j in range(W+1):
        newdp[j] = dp[j]
    for j in range(W+1):
        if j+w <= W:
            if newdp[j+w] < dp[j] + v:
                newdp[j+w] = dp[j] + v
    newdp, dp = dp, newdp


print(max(dp))

Solution (Python):


n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] 

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


print(max(dp))

Solution (Python):

"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d

"""
import sys


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



def main(args):
    N, W = map(int, input().split())
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d

"""
import sys


def solve(N, W, items):
    ans = {0: 0}
    for w, v in items:
        u = dict()
        for x, y in ans.items():
            if x+w <= W and ans.get(x+w, 0) < y+v:
                u[x+w] = y+v
        ans.update(u)
    return max([v for v in ans.values()])


def main(args):
    N, W = map(int, input().split())
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
import numpy as np
N, W = map(int, input().split())

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

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

Solution (Python):
n,w=map(int,input().split())
wlis=[]
vlis=[]
for i in range(n):
    a,b=map(int,input().split())
    wlis.append(a)
    vlis.append(b)

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

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

print(dp[n][w])

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


dp = []
dp.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	
	
	
	
	dpi = []
	for j in range(Wmax+1):
		if j<W[i]:
			dpi.append(dp[i-1][j])
		else:
			dpi.append(max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]))
	dp.append(dpi)
print(dp[N-1][Wmax])

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

	dp = [0] * (W + 1)
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			t = dp[sumw - w] + v
			if dp[sumw] < t:
				dp[sumw] = t
		
		
		
	return max(dp)

print(main())

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

	dp = [0] * (W + 1)
	
	
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			
			t = dp[sumw - w] + v
			if dp[sumw] < t:
				dp[sumw] = t
		
		
		
	return max(dp)

print(main())

Solution (Python):
def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())

Solution (Python):
def d():
    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(N):
        for j in range(W + 1):
            if j - wv[i][0] >= 0:
                dp[i + 1][j] = max(dp[i + 1][j],
                                   dp[i][j - wv[i][0]] + wv[i][1])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    return dp[-1][-1]


if __name__ == '__main__':
    ans = d()
    print(ans)

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

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

print(dp[N][W])

Solution (Python):
def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    
    dp_table = [[0 for _ in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for j in range(W):
            w_next = j+ww[i]
            v_next = vv[i]
            if w_next <= W:
                dp_table[i+1][w_next] = max(dp_table[i+1][w_next], dp_table[i][j] + v_next)
            dp_table[i+1][j] = max(dp_table[i+1][j], dp_table[i][j])


    print(max(dp_table[-1]))
    

sub()

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

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

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

Solution (Python):


def main():

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

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


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



    wvn.sort(key = lambda x : x[1], reverse = True )
    wvn.sort(key = lambda x : x[0] )


    
    for i in range(1, N + 1 ):

        
        for wi in range(1, W+1 ):

            wv = wvn[i-1]


            a = tab[i-1][wi]
            b = tab[i][wi-1]
            
            c = 0
            if wi>=wv[0] :
                t = tab[i-1][wi-wv[0]] + wv[1]
                c = max(c,t)
            


            tab[i][wi] = sorted([a,b,c])[-1]


    print(tab[-1][-1])






main()

Solution (Python):
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


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


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def i(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
n,w=list(map(int, sys.stdin.readline().split()))
arr=[list(map(int, sys.stdin.readline().split())) for i in range(n)]

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

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


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

Solution (Python):
N, W = list(map(int, input().split()))
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    w, v = list(map(int, input().split()))
    for lim_w in range(W+1):
        if lim_w - w < 0:
            dp[i][lim_w] = dp[i-1][lim_w]
            continue
        dp[i][lim_w] = max(dp[i-1][lim_w-w] + v, dp[i-1][lim_w])

print(max(dp[N]))

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

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]

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


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