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

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

n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [0]*w] + [[-float("inf")]*(w+1) for _ in range(n)]
wei, val = 0, 1

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

print(dp[n][w])

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

n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [0]*w] + [[0] + [-float("inf")]*w for _ in range(n)]
wei, val = 0, 1

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

print(dp[n][w])

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

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

import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W+1) for _ 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],
                    dp[i+1][j-1],
                    dp[i][j-w[i]] + v[i]
                )
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-1])

    print(dp[-1][-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))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
def resolve():
    n, w = map(int, input().split())
    goods = np.array([list(map(int, input().split())) for _ in range(n)])
    
    
    dp = np.zeros([w + 1], dtype=int)

    for i in range(1, n + 1):
        tmp = np.zeros(w + 1, dtype=int)
        tmp[goods[i - 1][0]:] = dp[:-goods[i - 1][0]] + goods[i - 1][1]
        dp = np.maximum(dp, tmp)

    print(dp[w])
    
resolve()

Solution (Python):
import numpy as np
def resolve():
    n, w = map(int, input().split())
    goods = np.array([list(map(int, input().split())) for _ in range(n)])
    dp = np.zeros([n + 1, w + 1], dtype=int)

    for i in range(1, n + 1):
        tmp = np.zeros(w + 1, dtype=int)
        tmp[goods[i - 1][0]:] = dp[i - 1][:-goods[i - 1][0]] + goods[i - 1][1]
        dp[i] = np.maximum(dp[i - 1], tmp)

    print(dp[n][w])
    
resolve()

Solution (Python):
def resolve():
    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(1, n + 1):
        for j in range(w + 1):
            tmp = dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1] if j >= goods[i - 1][0] else 0
            dp[i][j] = max(dp[i - 1][j], tmp)

    print(dp[n][w])
    
resolve()

Solution (Python):
def resolve():
    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(1, n + 1):
        for j in reversed(range(w + 1)):
            tmp = dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1] if j >= goods[i - 1][0] else 0
            dp[i][j] = max(dp[i - 1][j], tmp)

    print(dp[n][w])

resolve()

Solution (Python):
def resolve():
    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(1, n + 1):
        for j in reversed(range(w + 1)):
            
            if goods[i - 1][0] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[n][w])
    
resolve()

Solution (Python):

import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd

from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

def chmax(a, b):
    if a < b:
        return b
    else:
        return a

def input():
    return sys.stdin.readline()[:-1]

def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]
    dp = [[0] * (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] >= 0):
                dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])

            dp[i+1][sum_w] = chmax(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())
li = [list(map(int,input().split())) for i in range(N)]

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 >= li[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w-li[i][0]]+li[i][1],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())
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(1,n+1):
    wi,vi = [int(i) for i in input().split()]
    
    for j in range(w+1):
        if j >= wi : 
            dp[i][j] = max(dp[i-1][j] , dp[i-1][j-wi]+vi) 
        else:
            dp[i][j] = max(dp[i-1][j] , dp[i][j]) 
print(dp[n][w])

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

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

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

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


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

print(dp[-1])

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

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
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, k = inpl()
dp = [[0] * (k+1) for i in range(n+1)]
for i in range(n):
    w, v = inpl()
    for j in range(k + 1):
        include = dp[i][j - w] + v if j >= w else 0
        not_include = dp[i][j]
        dp[i + 1][j] = max(include, not_include)
print(max(dp[n][:]))

Solution (Python):
import numpy as np

N, W = map(int, input().split())
pairs = list(tuple(map(int, input().split())) for _ in range(N))

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

for (i, (w, v)) in enumerate(pairs):
    dp[i+1] = dp[i]
    dp[i+1, w:] = np.maximum(dp[i+1, w:], dp[i, :W-w+1] + v)

print(np.amax(dp[N]))

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

ans = [[0]*(10**5+10) for i in range(N+10)]
  
for i in range(N):
  for j in range(W+1):
    if j >= lst[i][0]:
      ans[i+1][j] = max(ans[i][j-lst[i][0]] + lst[i][1], ans[i][j])
    else:
      ans[i+1][j] = ans[i][j]
  
print(ans[N][W])

Solution (Python):
import numpy as np

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

Solution (Python):
[N,W]=[int(i) for i in input().split()]
WV=[]
for i in range(N):
	WV+=[[int(j) for j in input().split()]]
DP=[[0 for i in range(W+1)]for j in range(N)]
for i in range(N):
	for sum_w in range(W+1):
		if sum_w>=WV[i][0]:
			DP[i][sum_w]=max(DP[i-1][sum_w],DP[i-1][sum_w-WV[i][0]]+WV[i][1])
		else:
			DP[i][sum_w]=DP[i-1][sum_w]
print(DP[N-1][W])

Solution (Python):
[n,w] = [int(i) for i in input().split()]
dp = [[0]*(w+1) for i in range(n)]
wv = []
for i in range(n):
    wv.append([int(j) for j in input().split()])
"""
dp[i][w] = v
i : i番目まで
w : それまでの合計
"""

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

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

Solution (Python):





import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string


BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def main():
    nv=list(map(int,input().split()))
    n,v=nv[0],nv[1]
    wc=[list(map(int,input().split())) for i in range(n)]
    w=[x[0] for x in wc]
    c=[x[1] for x in wc]
    dp=[[0]*(v+1) for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(v+1):
            if j>=w[i-1]:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+c[i-1])
            else:
                dp[i][j]=dp[i-1][j]
        
    print (dp[n][v])
if __name__ == "__main__":
    main()

Solution (Python):
N, W = list(map(int, input().split(" ")))
dp =  [[0] * (W+1) for _ in range(N+1)]
 
for i in range(0, N):
	weight, value = map(int, input().split(" "))
	for w in range(1, W+1):
		if w >= weight:
			dp[i + 1][w] = max([dp[i][w - weight] + value, dp[i][w]])
		else:
			dp[i + 1][w] = dp[i][w]
print(dp[N][W])

Solution (Python):
n,w=map(int,raw_input().split())
a=[map(int,raw_input().split()) for _ in xrange(n)]
z=[[0]*(w+1)]
for i in xrange(n):
    z.append(z[-1][:])
    for j in xrange(w+1):
        if a[i][0]<=j:
            z[i+1][j]=max(z[i+1][j],z[i][j-a[i][0]]+a[i][1])
print max(z[-1])

Solution (Python):
import numpy as np

N, W = map(int, input().split())
dp = np.zeros(W + 1, np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])
print(dp[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):
    we,v=map(int,input().split())
    np.maximum(dp[we:],dp[:-we]+v,out = dp[we:])
print(dp[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):
    we,v=map(int,input().split())
    if we > w:
        continue
    else:
        np.maximum(dp[we:],dp[:-we]+v,out = dp[we:])
print(dp[w])

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

dp = [0]*(max_w+1)
dp = np.array(dp)

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

print(max(dp))

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

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

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

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

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

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

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

dp = [0]*(W+1)

for w, v in wv:
    newdp = dp[:]
    for ww in range(W+1):
        if w+ww > W:
            continue
        newdp[w+ww] = max(dp[ww+w], dp[ww]+v)
    dp = newdp

print(dp[-1])

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

print(dp[n][max_weight])

Solution (Python):
import numpy as np

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

dp = np.zeros(W + 1, dtype=np.int64)
for n in range(N):
    tmp = np.zeros_like(dp, dtype=np.int64)
    tmp[goods[n][0]:] = dp[:W + 1 - goods[n][0]] + goods[n][1]
    dp = np.maximum(dp, tmp)
print(dp[W])

Solution (Python):
def knapsack(sizes, vals, volume):
    n = len(sizes)

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

    for i in range(n):
        for j in range(volume+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])

    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print(knapsack(sizes, vals, volume))

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

Solution (Python):
def knapsack(sizes, vals, volume):
    n = len(sizes)

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

    for i in range(n):
        for j in range(volume+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])
            

    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print(knapsack(sizes, vals, volume))

Solution (Python):
def knapsack(sizes, vals, volume):
    n = len(sizes)

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

    for i in range(n):
        for j in range(volume+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])
            dp[i][j] = max(dp[i][j], dp[i-1][j])

    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print(knapsack(sizes, vals, volume))

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def solve():
    dp = np.zeros(W + 1, dtype=int)
    w0, v0 = things[0]
    dp[w0:] = v0
    for i in range(1, N):
        weight, value = things[i]
        np.maximum(dp[weight:], dp[:-weight] + value, out=dp[weight:])
    return dp[W]


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

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
wv.sort()
cost=[[0]*(w+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(w+1):
        if wv[i-1][0] <= j:
            cost[i][j]=max(wv[i-1][1]+cost[i-1][j-wv[i-1][0]],cost[i-1][j])
        else:
            cost[i][j]=cost[i-1][j]
print(cost[n][w])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def solve():
    dp = [0] * (W + 1)
    w0, v0 = things[0]
    for i in range(w0, W + 1):
        dp[i] = v0
    for i in range(1, N):
        dn = list(dp)
        weight, value = things[i]
        for j in range(weight, W + 1):
            dn[j] = max(dn[j], dp[j - weight] + value)
        dp = dn
    return dp[W]


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

Solution (Python):
def solve(items, w):
    dp = [[0]*(w+1)]
    for item in items:
        curr = []
        for i in range(w+1):
            if i - item[0] >= 0:
                curr.append(max(dp[-1][i], dp[-1][i - item[0]]+item[1]))
            else:
                curr.append(dp[-1][i])
        dp.append(curr)
    return dp[-1][-1]


if __name__ == "__main__":
    n, w = map(int, input().split())
    items = [[int(x) for x in input().split()] for y in range(n)]
    print(solve(items, 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 _ in range(N+1) ]

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

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

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

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

print(dp[n][w])

Solution (Python):
import numpy as np
N, W = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=int)

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

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])

print(dp[N,-1])

Solution (Python):
import sys
import numpy as np


input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1),dtype=int)
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

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

Solution (Python):

from sys import stdin

def main():
    ds_in = lambda: list(map(int, stdin.readline().split()))  

    N, W = ds_in()

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

    for i in range(N):
    
        w, v = ds_in()  
        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]
    ans = 0
    for i in range(W+1):
        ans = max(ans, dp[N][i])
    print(ans)
    return 0
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]*100010 for i in range(N+10)]
for i in range(N):
    for now_w in range(W+1):
        if (now_w >= w[i]):
            dp[i+1][now_w] = max(dp[i][now_w-w[i]] + v[i], dp[i][now_w])
        else:
            dp[i+1][now_w] = dp[i][now_w]

print(dp[N][W])

Solution (Python):


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

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

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

print(max(dp[-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 = [[0]*(W+1) for _ in range(N+1)]




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

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

Solution (Python):
def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i]
                    )
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j-w_list[i]>=0:
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0
 
if __name__ == "__main__":
    solve()

Solution (Python):

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)
    
dp = [[0]*(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 = list(map(int,input().split()))
WV = []
for i in range(N):
    WV.append(list(map(int,input().split())))

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

for j in range(W+1):
    if WV[0][0]>j:
        dp[0][j]=0
    else:
        dp[0][j]=WV[0][1]

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

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

Solution (Python):

def main():
    import sys
    import copy
    N, limit = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    dp = [[0 for _ in range(limit+1)] for _ in range(N)]
    dp[0][L[0][0]] = L[0][1] 
    for i in range(1, N):
        dp[i] = copy.copy(dp[i-1]) 
        w, v = L[i][0], L[i][1]
        dp[i][w] = max(v, dp[i][w])
        for j in range(limit+1-w):
            if dp[i-1][j] >0:
                dp[i][w+j] = max(v+ dp[i-1][j], dp[i][w+j])
            
    
    
    print(max(dp[-1]))



if __name__=='__main__':
    main()

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

w = [w_v[i][0] for i in range(N)]
v = [w_v[i][1] for i in range(N)]



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

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

print(dp[N][W])

Solution (Python):
def main():
    n, w = tuple([int(e) for e in input().split()])
    items = []
    for i in range(n):
        items.append(tuple([int(e) for e in input().split()]))
    
    t = [[0] * (n + 1) for _ in range(w + 1)]
    for i in range(1, w + 1):
        for j in range(1, n + 1):
            if i - items[j - 1][0] >= 0:
                t[i][j] = t[i - items[j - 1][0]][j - 1] + items[j - 1][1]
            t[i][j] = max(t[i][j], t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
    print(t[w][n])
    return 0

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, w = tuple([int(e) for e in input().split()])
    items = []
    for i in range(n):
        items.append(tuple([int(e) for e in input().split()]))
    items.sort(key=lambda x: x[0])
    
    t = [[0] * (n + 1) for _ in range(w + 1)]
    for i in range(1, w + 1):
        for j in range(1, n + 1):
            if i - items[j - 1][0] >= 0:
                t[i][j] = t[i - items[j - 1][0]][j - 1] + items[j - 1][1]
            t[i][j] = max(t[i][j], t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
    print(t[w][n])
    return 0

if __name__ == "__main__":
    main()

Solution (Python):
nw=list(map(int, input().split(" ")))
dp=[[0]*(nw[1]+1) for _ in range(nw[0]+1)]
w=[]
v=[]
i=0
ww=0
for _ in range(nw[0]):
    wv=list(map(int, input().split(" ")))
    w.append(wv[0])
    v.append(wv[1])
for i in range(nw[0]):
    for ww in range(nw[1]+1):
        if w[i] <= ww:
            dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww-w[i]]+v[i])
        dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww])
print(dp[nw[0]][nw[1]])

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

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

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

    print(max(dp[-1]))

if __name__ == "__main__":
    main()