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
sys.setrecursionlimit(10**8)
def knapsack(N,W,weight,value):
  
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: 
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: 
        dp[i+1][w]=dp[i][w]
  return dp[N][W]
n1,w1=map(int,input().split())
lw=[]
lv=[]
for i in range(n1):
  w,v=map(int,input().split())
  lw.append(w)
  lv.append(v)
print(knapsack(n1,w1,lw,lv))

Solution (Python):
N,W = map(int,input().split())
wv = [[int(i) for i in input().split()] for j 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 - 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])

print(dp[N][W])

Solution (Python):
def main():
    n,w=map(int,input().split())
    wv=[]
    for _ in range(n):
        wv.append(list(map(int,input().split())))
    dp=[]
    temp=[]
    for i in range(0,w+1):
        if i < wv[0][0]:
            temp.append(0)
        else:
            temp.append(wv[0][1])
    
    dp.append(temp)
    

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

if __name__=='__main__':
    main()

Solution (Python):
n, w = map(int, input().split())
wt, v = [], []
for i in range(n):
    a, b = map(int, input().split())
    wt.append(a)
    v.append(b)
dp = [0 for i in range(w + 1)]
for i in range(len(wt)):
    for j in range(w, wt[i]-1, -1):
        dp[j] = max(dp[j], v[i] + dp[j - wt[i]])
print(dp[-1])

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

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

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,int)
for i in range(N):
  w,v=WV[i]
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])

Solution (Python):
x,y=map(int,input().split())
yo=[]
yo0=[]
for __ in range(x):
    a,b=map(int,input().split())
    yo.append(a)
    yo0.append(b)
lol=[0]*(y+1)
lol0=[0]*(y+1)
k=[0]*(y+1)

for i in range(1,x+1):
    for j in range(1,y+1):
        if j<yo[i-1]:
            
            lol0[j]=lol[j]
        else:
            lol0[j]=max(lol[j],yo0[i-1]+lol[j-yo[i-1]])
    lol=lol0[:]
    lol0=k[:]
print(lol[y])

Solution (Python):
x,y=map(int,input().split())
yo=[]
yo0=[]
for __ in range(x):
    a,b=map(int,input().split())
    yo.append(a)
    yo0.append(b)
lol=[]
for i in range(x+1):
    lol.append([0]*(y+1))
for i in range(1,x+1):
    for j in range(1,y+1):
        if j<yo[i-1]:
            lol[i][j]=lol[i-1][j]
        else:
            lol[i][j]=max(lol[i-1][j],yo0[i-1]+lol[i-1][j-yo[i-1]])
print(lol[x][y])

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

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

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



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

Solution (Python):
import sys
input = sys.stdin.readline
def solve():
  n,W = (int(i) for i in input().split())
  query = []
  for i in range(n):
    w,v = (int(i) for i in input().split())
    query.append((w,v))
  dp = [[0]*(W+1) for _ in range(n+1)]
  for i in range(n):
    nw,nv = query[i]
    for weight in range(W):
      if weight+nw <= W:
        dp[i+1][weight+nw] = max(dp[i][weight+nw],dp[i][weight]+nv)
      dp[i+1][weight] = max(dp[i][weight],dp[i+1][weight])
  print(dp[n][W])
solve()

Solution (Python):
n, w = [int(i) for i in input().split()]
a = [0] * (w + 1)
for _ in range(n):
    b, c = [int(i) for i in input().split()]
    for i in reversed(range(w + 1)):
        if i + b >= w + 1:
            continue
        d = i + b
        a[d] = max(a[d], a[i] + c)
print(a[-1])

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

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

def chmax(a,b):
    if a < b:
        return b
    else:
        return a 
    
for i in range(N): 
    for w in range(W+1): 
        if wv[i][0] <= W - w:
            dp[i+1][w+wv[i][0]] = chmax(dp[i+1][w+wv[i][0]],dp[i][w]+wv[i][1])
        
        dp[i+1][w] = chmax(dp[i+1][w],dp[i][w])
        
print(dp[N][W])

Solution (Python):




"""
20191119
24分ギブアップ
質問

20191120
12分
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

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

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

    return max(dp[-1])


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

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

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

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

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

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

print(dp[n][w])

Solution (Python):
n, w = map(int, input().split(' '))
items = [[]] * n
for i in range(n):
  weight, val = map(int, input().split(' '))
  items[i] = [weight, val]




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



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

print(dp[W])

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

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

dp = [[0 for i in range(w+1)] for _ 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][sum_w-weight[i]]+value[i], dp[i][sum_w])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]

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

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

dp = [0] * (W + 1)

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

print(dp[W])

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

Solution (Python):
import numpy as np

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

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

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

print(dp[-1])

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

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


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

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

    
    
    knapsack = [list(map(int, readline().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):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

    print(dp[N][W])


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype = np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
print(dp.max())

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

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

for i in range(len(stones)):
  w=stones[i][0]
  v=stones[i][1]
  np.maximum(dp[:-w]+v,dp[w:],dp[w:])

print(dp.max())

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


for n in range(1,N+1):
    for w in range(1,W+1):
        wi,vi = Data[n]
        if w >= wi:
            DP[n][w] = max(DP[n][w],DP[n-1][w-wi]+vi)
        DP[n][w] = max(DP[n][w],DP[n-1][w])

print(DP[N][W])

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

print(dp[n][w])

Solution (Python):
import sys

import numpy as np

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


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])

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

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

    print(np.max(dp))


main()

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

table = {i: [0]*(W+1) for i in range(N+1)}
def dp(N, W):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
      if w <= j:
        table[i][j] = max(table[i-1][j-w]+v, table[i-1][j])
      else:
        table[i][j] = table[i-1][j]
  return table[N][W]

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,int)
for i in range(n):
	W,V = WV[i]
	
	dp[W:] = np.maximum(dp[W:],dp[:-W]+V)
	

print(dp[-1])

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, input().rstrip('\n').split()))
    dp = [0] * (w + 1)
    for _ in range(n):
        wv, vv = list(map(int, input().rstrip('\n').split()))
        for i in range(w - wv, -1, -1):
            dp[i+wv] = max(dp[i+wv], dp[i] + vv)
    print(dp[-1])


if __name__ == '__main__':
    solve()

Solution (Python):
def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()

Solution (Python):

import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())
dp = [defaultdict(int) for _ in range(n)]

w, v = map(int, sys.stdin.readline().split())
dp[0][w] = v


for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][w] = max(dp[i-1].get(w, 0), v)
    for w1, v1 in dp[i-1].items():
        dp[i][w1] = max(dp[i][w1], v1)
        if w+w1<=W:
            dp[i][w1+w] = max(dp[i][w1+w], v1+v)

print(max(dp[-1].values()))

Solution (Python):
from itertools import count

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

Solution (Python):
"""
【01ナップザック問題】
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000
"""



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

print(dp[W])

Solution (Python):
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
res=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,a[i][0]-1,-1):
        res[j]=max(res[j],res[j-a[i][0]]+a[i][1])
print(res[w])

Solution (Python):
n,W=map(int, input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y=map(int, input().split())
    w[i]=x
    v[i]=y
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]:
            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):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000
"""

n ,W = map(int, input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
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]:
            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):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [0] * (w + 1)
    for ww, vv in wv:
        for i in range(w-ww+1, -1, -1):
            if i + ww <= w:
                dp[i+ww] = max(dp[i+ww], dp[i] + vv)
    print(dp[-1])


if __name__ == '__main__':
    solve()

Solution (Python):
n,W=map(int, input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y=map(int, input().split())
    w[i]=x
    v[i]=y
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]:
            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):
import sys
n, W = map(int, sys.stdin.readline().split())
dp = [[0 for _ in range(W+1)] for _ in range(n)]
for i in range(n):
    w, v =map(int, sys.stdin.readline().split())
    for j in range(W+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j])
        if dp[i-1][j] !=0 and j+w<=W:
            dp[i][j+w] = max(dp[i-1][j+w], v+ dp[i-1][j])
            
        
    dp[i][w] = max(dp[i-1][w], v)
    

print(max(dp[-1]))

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

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

print(max(dp))

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

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

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


print(max(dp[n]))

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

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

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,int)
for i in range(n):
  w,v=WV[i]
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])

Solution (Python):
def Knapsack1(W,w,v): 
    n=len(w)
    
    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]=max( 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(max(dp[n]))

def main():
    n,W = 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())
    Knapsack1(W,w,v)
if __name__ == "__main__":
    main()

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

print(dp[W])

Solution (Python):
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000
"""

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

print(dp[n][W])

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

weights = [0]*(N+5)
values = [0]*(N+5)

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

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            if dp[i+1][sum_w] < dp[i][sum_w-weights[i]]+values[i]:
                dp[i+1][sum_w] = dp[i][sum_w-weights[i]]+values[i]
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]


print(max([max(row) for row in dp]))

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

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

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

Solution (Python):
import numpy as np
N, W = map(int, input().split())
l = sorted([tuple(map(int, input().split())) for i in range(N)], key=lambda x: x[0])
dp = np.zeros(W+1, dtype=int)
for i in range(N):
    w = l[i][0]
    dp[w:] = np.maximum(dp[w:], dp[:-w] + l[i][1])
print(dp[-1])

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

import numpy as np

N,W = map(int,readline().split())
m = map(int,read().split())
WV = list(zip(m,m))



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

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

answer = dp.max()
print(answer)

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

Solution (Python):
n,k=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
dpv=[0]*(k+1)
dpw=[0]*(k+1)
for j in range(n):
    for i in range(k,-1,-1):
        if i-w[j]>=0:
            if dpv[i-w[j]]+v[j]>dpv[i]:
                dpw[i]=dpw[i-w[j]]+w[j]
                dpv[i]=dpv[i-w[j]]+v[j]
        else:
            break
print(dpv[k])

Solution (Python):

si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

N,W = nm()
Weight = []
Value = []

for i in range(N):
    w,v = nm()
    Weight.append(w)
    Value.append(v)

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

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

print(dp[N][W])

Solution (Python):
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    l = [0] * (m + 1)
    for i in range(n):
        for j in range(m, w[i] - 1, -1):
            x = v[i] + l[j-w[i]]
            if x > l[j]:
                l[j] = x
    print(l[-1])
main()

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


if __name__ == '__main__':
    main()

Solution (Python):
N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W):
    if(wei<=j+1):
      if(array[i][j] < array[i][j-wei+1]+V):
        array[i+1][j+1]=array[i][j-wei+1]+V
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])

Solution (Python):
N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W):
    if(wei<=j+1):
      if(array[i][j] < array[i][j-wei+1]+V):
        array[i+1][j+1]=array[i][j-wei+1]+V
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])

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

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N, W = map(int, readline().split())
    wv = map(int, read().split())
    dp = np.zeros(W + 1, np.int64)

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

    print(dp.max())


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N, W = map(int, readline().split())
    wv = map(int, read().split())
    dp = np.zeros(W + 1, np.int64)

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

    print(dp.max())


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, W = map(int, readline().split())
wv = map(int, read().split())
dp = np.zeros(W + 1, np.int64)

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

print(dp.max())

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

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

    for ni in range(1,len(min_costs)):
        for wi in range(1,len(min_costs[ni])):
            if wi < weights[ni]:
                min_costs[ni][wi] = min_costs[ni -1][wi]
            else:
                min_costs[ni][wi] = max(min_costs[ni -1][wi],min_costs[ni -1][wi-weights[ni]] + values[ni])

    print(min_costs[-1][-1])
    
resolve()

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

dp=[]
for i in range(w+1):
    dp.append([0,0])
dp[0][0]=1
it=[]
val=[]
for i in range(n):
    a,b=input().split()
    it.append(int(a))
    val.append(int(b))
for i in range(n):
    x=it[i]
   
    ac=[]
    for j in range(w-x,-1,-1):
        if dp[j][0]==1:
           
            ac.append(j+x)
            dp[j+x][1]=max(dp[j+x][1],val[i]+dp[j][1])
   
    for i in ac:
        dp[i][0]=1
  
print(max([i[1] for i in dp]))

Solution (Python):


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