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 string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    n, W = readi(2)
    ws, vs = zip(*readi(n, 2))
    dp = arr(n + 1, W + 1)
    for i in range(n):
        for w in range(W + 1):
            if w - ws[i] >= 0:
                dp[i + 1][w] = dp[i][w - ws[i]] + vs[i]
            dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
    print(dp[n][W])


if __name__ == "__main__":
    main()

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

Solution (Python):
def main():
    [N, W] = [int(num) for num in input().split()]

    products = []
    for i in range(N):
        products.append([int(num) for num in input().split()])

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

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

    print(dp[N][W])

if __name__ == '__main__':
    main()

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    n, W = readi(2)
    ws, vs = zip(*readi(n, 2))
    dp = arr(n + 1, W + 1)
    for i in range(n):
        for w in range(W + 1):
            if w - ws[i] >= 0:
                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w - ws[i]] + vs[i])
            dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
    print(dp[n][W])


if __name__ == "__main__":
    main()

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

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

dp = [[0 for i in range(2*W)] for j in range(2*N)]

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):
from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)


def main():
	n,w = map(int,input().split())
	wv = [list(map(int,input().split())) for i in range(n)]
	dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
	for i in range(1,n+1):
		cw = wv[i-1][0]
		cv = wv[i-1][1]
		for j in range(w+1):
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-cw] + cv) if j-cw >= 0 else dp[i-1][j]
	print(dp[-1][-1])

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

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

value = [[-1 for j in range(W + 1)] for i in range(N + 1)]

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

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

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

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

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

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


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

dp[0][0] = 0

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

print(dp[N][W])

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

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

print(max(dp[N]))

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

Solution (Python):
import sys
import numpy as np

n, k = map(int, sys.stdin.readline().split())

dp = np.zeros((n+1, k+1))

for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    dp[i] = dp[i-1]
    dp[i][w:] = np.maximum(dp[i-1][:-w]+v, dp[i-1][w:])

print(int(np.max(dp[n])))

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


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

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

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    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][W])

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

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

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

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

print(DP[0])

Solution (Python):
if __name__ == '__main__':
    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]:
                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):
n, w = map(int, input().split())

wei = []
val = []

for i in range(n):
    x, y = map(int, input().split())
    wei.append(x)
    val.append(y)

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

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

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

print(dp[N][W])

Solution (Python):
def knapsack(n,W,v,w):
    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 or j==0):
                dp[i][j]=0
            elif(v[i-1]<=j):
                dp[i][j] = max(w[i-1] + dp[i-1][j-v[i-1]],dp[i-1][j]) 
            else:
                dp[i][j]=dp[i-1][j]
    
    return dp[n][W] 



n,W=map(int,input().split())
v=[]
w=[]
for i in range(n):
    a,b=map(int,input().split())
    v.append(a)
    w.append(b)
print(knapsack(n,W,v,w))

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

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math






def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()

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

print(max(dp[n]))

Solution (Python):
n,wmax = 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]*(wmax+1)
for weight,value in zip(w,v):
    for i in reversed(range(weight,wmax+1)):
        dp[i] = max(dp[i],dp[i-weight]+value)

print(max(dp))

Solution (Python):


def knapsack(N, W, wv):
    
    dp = [list(0 for _ in range(W+1)) for j 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]
    return dp[N][W]

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

Solution (Python):
def dp():
    n,w = map(int,input().split())
    lis = (map(int,input().split()) for i in range(n))
    
    dpp = [0] * (w + 1)
    for weight, value in lis:
        for j in range(w,weight-1,-1):
            dp = dpp[j-weight] + value
            if dpp[j] < dp:
                dpp[j] = dp
    return max(dpp)
print(dp())

Solution (Python):



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

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

if __name__ == '__main__':
    d()

Solution (Python):



def main():
    n, w = map(int, input().split())
    ws = [0 for _ in range(n)]
    vs = [0 for _ in range(n)]
    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

    for i in range(n):
        wi, vi = map(int, input().split())
        ws[i] = wi
        vs[i] = vi

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

    print(dp[n][w])


if __name__ == '__main__':
    main()

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

dp = [0]*(W+1)

for w,v in  wvs:
    for i in reversed(range(W+1)):
        
        dp[i] = max(dp[i-w]+v,dp[i])
        if i == w:
            break

print(max(dp))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

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

for w,v in wvs:
    for i in reversed(range(W+1)):
        dp[i] = max(dp[i-w] + v,dp[i])
        if i == w:
            break

print(max(dp))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, W = LI()
wv = LIR(N)

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

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

print(dp[N][W])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, W = LI()
wv = LIR(N)

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

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

print(dp[N][W])

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

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

Solution (Python):
import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))

Solution (Python):


import sys

class DKnapsack1:
    def solve(self):
        n, W = [int(_) for _ in input().split()]
        w = [0] * (n + 1)
        v = [0] * (n + 1)
        for i in range(1, n + 1):
            w[i], v[i] = [int(_) for _ in input().split()]

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

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

        print(dp[W][n])

solver = DKnapsack1()
input = sys.stdin.readline

solver.solve()

Solution (Python):
inf = float('inf')

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

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

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

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

Solution (Python):
inf = float('inf')

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

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

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

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

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

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

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


for i in range(weight[0], W+1):
    dp[0][i] = value[0]

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

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

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

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


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


        w,v = items[i]
        if w_sum - w >= 0:
            dp[i + 1][w_sum]  = dp[i][w_sum - w] + v
        
        a,b = dp[i + 1][w_sum],dp[i][w_sum]
        dp[i + 1][w_sum] = max(a,b)

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

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

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

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

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

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

Solution (Python):

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

lis = [ [0] * (W+1) ]


for i in range(N):

    w,v = map(int,input().split())

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print (lis[-1][W])

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):
"D Knapsack 1"
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])


"""
dp[:-w]は後ろからw個より前の要素、つまり（N-w）個
dp[w:]は前からw個より後ろの要素、つまり（N-w）個
よって形状が一致する
"""

"""
dp[:-w]は今見ている重さw、価値vの荷物を入れることのできる状態のナップサック
dp[:-w]+vをすることで、今見ている荷物を入れた時の価値の総和になる。
今、重さw、価値vの荷物を入れたナップサックと、dp[w:]を比較する。
それぞれの要素について大きい方が新しい要素となり、out=dp[w:]によって上書きされる。
maximumが返すのはnp配列。形状は比較対象となっている配列の形状と一致する
"""

Solution (Python):
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w_tmp, v_tmp = map(int, input().split())
    weight.append(w_tmp)
    value.append(v_tmp)

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

print(dp[N][W])

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

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

Solution (Python):
n,w=map(int,input().split())
dp=[0]*(w+1)
for i in range(n):
    w2,v2=map(int,input().split())
    for j in range(w,w2-1,-1):
        tmp=dp[j-w2]+v2
        if tmp>dp[j]:
            dp[j]=tmp
print(dp[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 resolve():
    (N, W) = list(map(int, input().split(" ")))
    wvs = [[None, None]]
    wvs.extend([list(map(int, input().split(" "))) for _ in range(N)])
    dps = [[0] * (W+1) for _ in range(N+1)]

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

    print(dps[N][W])

if __name__ == '__main__':
    resolve()

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

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))

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

dp = [[None] * (10**5 + 1) for _ in range(100 + 1)]

















dp[-1] = [0] * len(dp[-1])
for depth in range(0, N):
    for weight in range(10**5 + 1):
        v = dp[depth - 1][weight]
        if weight + ws[depth] <= W:
            dp[depth][weight] = max(v, dp[depth - 1][weight + ws[depth]] + vs[depth])
        else:
            dp[depth][weight] = v

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

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

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

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

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

print(dp[N][W])

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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)]
dp[0][w[0]] = v[0]

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

ans = 0

for j in range(W + 1):
    if dp[-1][j] > ans:
        ans = dp[-1][j]

print(ans)

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