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

print(dp[N][W])

Solution (Python):
import sys

input=sys.stdin.readline

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

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

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

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

Solution (Python):
n,w = map(int, input().split())
a = [[int(x) for x in input().split()] for i in range(n)]
dp = [-1 for i in range(w + 1)]
dp[0] = 0
for i in range(n):
    for j in range(w, -1, -1):
        if dp[j] != -1 and j + a[i][0] <= w:
            dp[j + a[i][0]] = max(dp[j + a[i][0]], dp[j] + a[i][1])
print(max(dp))

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

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

    for n in range(N):
        weight, value = map(int, input().split())

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

    print(dp[N][W])


main()

Solution (Python):
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.zeros(W+1, dtype=int)

for i in range(N):
    DP[w[i]:] = np.maximum(DP[:-w[i]]+ v[i], DP[w[i]:])
print(DP[-1])

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

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

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

ans = Dp[-1][-1]
print(ans)

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

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

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

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

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

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

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


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


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

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

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


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

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            if dp[i][j-weight[i]] != None and dp[i][j] != None:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            elif dp[i][j-weight[i]] == None and dp[i][j] != None:
                dp[i+1][j] = dp[i][j]
            elif dp[i][j-weight[i]] != None and dp[i][j] == None:
                dp[i+1][j] = dp[i][j-weight[i]]+value[i]
            else:
                dp[i+1][weight[i]] = value[i]
        else:
            dp[i+1][j] = dp[i][j]
            
print(max(i for i in dp[n] if i is not None))

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

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

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

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

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

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

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

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


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

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

print(dp[N][W])

Solution (Python):
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
b = [tuple(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 + b[i][0] <= W:
      dp[i + 1][j + b[i][0]] = max(dp[i][j] + b[i][1], dp[i + 1][j + b[i][0]])
    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[-1]))

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

dp = [0] * (w + 1)

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

print(dp[w])

Solution (Python):
from pprint import pprint
import sys

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

w = []
for _ in range(N):
    w_i, v_i = map(int, sys.stdin.readline().strip().split(" "))
    w.append((w_i, v_i))

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


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

print(dp[N][W])

Solution (Python):
from pprint import pprint
import sys

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

w = []
for _ in range(N):
    w_i, v_i = map(int, sys.stdin.readline().strip().split(" "))
    w.append((w_i, v_i))

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


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

print(dp[N][W])

Solution (Python):
import numpy as np
n, w = map(int, input().split())
ndp = np.zeros(w+1)

for i in range(n):
    wi, vi = map(int, input().split())
    np.maximum(ndp[:-wi]+vi, ndp[wi:], out=ndp[wi:])

print(int(ndp[-1]))

Solution (Python):


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

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

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

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

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

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

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

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

def process(N,W):
  box=[0]*(W+1)
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(W,0,-1):
      idx = j-w
      if idx<0:
        break
      else:
        box[j] = max(box[j],box[idx]+v)
  return box[-1]

print(process(N,W))

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


def f(n, W):
    dp = [0] * (W + 1)
    for i in range(n):
        wi, vi = map(int, input().split())
        for w in range(W, wi - 1, -1):
            v_ = dp[w - wi] + vi
            if dp[w] < v_:
                dp[w] = v_
    return(dp[-1])


n, w = map(int, input().split())
print(f(n, w))

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**7)
    N,W=list(map(int,sys.stdin.readline().split()))

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

    WL=[0]*N
    VL=[0]*N

    for i in range(N):
        w,v=list(map(int,sys.stdin.readline().split()))
        WL[i]=w
        VL[i]=v

    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=WL[i-1]:
                a=dp[i-1][w-WL[i-1]]+VL[i-1]
                b=dp[i-1][w]
                dp[i][w]=max(a,b)
            else:
                dp[i][w]=dp[i-1][w]
    print(dp[-1][-1])
main()

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

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

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


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

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

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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):
def knapsack(N,W,wv):
  
  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 wv[i][0]<=w: 
        dp[i+1][w]=max(dp[i][w-wv[i][0]]+wv[i][1], dp[i][w])
      else: 
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

if __name__ == "__main__":
  N, W = map(int, input().split())
  wv = [list(map(int, input().split())) for i in range(N)]
  ans = knapsack(N, W, wv)
  print(ans)

Solution (Python):
def woo(n, w):
	res = [0 for i in range(0, w+1)]

	for i in range(0, n):
		ww, vv = map(int, input().split())
		for j in range(w, ww-1, -1):
			wtotal = j + ww
			vtotal = res[j-ww] + vv
			if vtotal > res[j]:
				res[j] = vtotal

	return res

if __name__ == '__main__':
	n, w = map(int, input().split())
	r = woo(n, w)
	print(max(r))

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

N, W = map(int, input().split())
dp = np.zeros((W+1),dtype=int)

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

print(dp.max())

Solution (Python):
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

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

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

print(dp[n][w])

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

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


dp = [0]*(w+1) 
"""


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

for i in range(n):
    for j in range(w,-1,-1): 
        if j - list1[i][0] >= 0:
            dp[j] = max(dp[j-list1[i][0]]+list1[i][1],dp[j])
"""
※例えば、i=0のループで、
jを前から回すと、wの条件を満たすたびにlist1[i][1]が足されていくので、
一つの商品に対して何度も重複を許すことになる。但し、後ろから回せば
dp[j-list1[i][0]]は必ずその要素を足し合わせていない値であることがわかる。
これを前から回したいときは、適宜一周前のループを参照する必要があるため、
二次元配列を作成する必要がある。
"""
print(dp[-1])

Solution (Python):
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(100111)] for j in range(111)]

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

print(dp[n][w])

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