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())
dp=[[0]*(w+1) for i in range(n+1)]
wet=[]
val=[]
for i in range(n):
  we,va=map(int,input().split())
  wet.append((we,va))
wet.sort()

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

Solution (Python):
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))

Solution (Python):
N,W = map(int,input().split())
Value = []
weight = []
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):
    w,v = map(int,input().split())
    Value.append(v)
    weight.append(w)


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

print(dp[N][W])

Solution (Python):
N,W = map(int,input().split())
Value = []
weight = []
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):
    w,v = map(int,input().split())
    Value.append(v)
    weight.append(w)


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

print(dp[N][W])

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

def main():
    input = sys.stdin.readline  
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

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

    for i, item in enumerate(item_list, 1):
        for w in range(W+1):
            
            if w + item[0] <= W:
                dp[i][w+item[0]] = max(dp[i][w+item[0]], dp[i-1][w]+item[1])
            
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    print(dp[N][W])

if __name__ == '__main__':
    main()

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

def main():
    input = sys.stdin.readline  
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

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

    for i, item in enumerate(item_list):
        for w in range(W+1):
            
            if w + item[0] <= W:
                dp[i][w+item[0]] = max(dp[i][w+item[0]], dp[i-1][w]+item[1])
            
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    print(dp[N-1][W])

if __name__ == '__main__':
    main()

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

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

Solution (Python):
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,w=mp()
item=[lmp() for i in range(n)]
dp=[[0]*(w+1) for i in range(n+1)]
for i in range(n):
    for k in range(1,w+1):
        if k<item[i][0]:
            dp[i+1][k]=dp[i][k]
        else:
            dp[i+1][k]=max(dp[i][k],dp[i][k-item[i][0]]+item[i][1])
print(dp[-1][-1])

Solution (Python):
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,w=mp()
dp=[0]*(w+1)
for i in range(n):
    x,y=mp()
    for k in range(w,x-1,-1):
        dp[k]=max(dp[k],dp[k-x]+y)
print(dp[-1])

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

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

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

print(dp[n][w])

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

Solution (Python):
N, W = map(int, input().split())
w_list = [0]
v_list = [0]

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

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

Solution (Python):
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    weight,value = map(int,input().split())
    w.append(weight)
    v.append(value)
    
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):







N, W, = 6, 15
ARR = [
    [6, 5],
    [5, 6],
    [6, 4],
    [6, 6],
    [3, 5],
    [7, 2],
]



N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))


def calculate(n, w, arr):
    srr = [[0] * (w+1) for i in range(n+1)]

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

    print(srr[-1][-1])


calculate(N, W, ARR)

Solution (Python):



















N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))

def calculate(n, w, arr):
    srr = [[0] * (w+1) for i in range(n+1)]

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

    print(srr[-1][-1])

calculate(N, W, ARR)

Solution (Python):







N, W, = 6, 15
ARR = [
    [6, 5],
    [5, 6],
    [6, 4],
    [6, 6],
    [3, 5],
    [7, 2],
]


N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))


def calculate(n, w, arr):
    srr = [[0] * (w + 1) for i in range (n + 1)]

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

    print(srr[-1][-1])


calculate(N, W, ARR)

Solution (Python):
def main():
    n, w_max = map(int, input().split())
    dp = [[0] * (w_max + 1) for _ in range(n + 1)]
    items = [tuple(map(int, input().split())) for _ in range(n)]
    for i1 in range(1, n + 1):
        w, v = items[i1 - 1][0], items[i1 - 1][1]
        for col in range(1, w_max + 1):
            if w <= col:
                dp[i1][col] = max(dp[i1 - 1][col], dp[i1 - 1][col - w] + v)
            else:
                dp[i1][col] = dp[i1 - 1][col]

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, w_max = map(int, input().split())
    dp = [[0] * (w_max + 1) for _ in range(n + 1)]
    for i1 in range(1, n + 1):
        w, v = map(int, input().split())
        for col in range(1, w_max + 1):
            if w <= col:
                dp[i1][col] = max(dp[i1 - 1][col], dp[i1 - 1][col - w] + v)
            else:
                dp[i1][col] = dp[i1 - 1][col]

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


if __name__ == '__main__':
    main()

Solution (Python):

from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil, factorial, log
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
from fractions import Fraction
from functools import reduce
import string
import sys
import os
import re
inf = float('inf')
mod_ = int(1e9) + 7
mod = 998244353

def factors(n):
    from functools import reduce
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def sieve(m):
    n=1
    primes = {}
    arr=set([])
    for i in range(2, int(m ** 0.5) + 1):
        a = n // i
        b = m // i
        for k in range(max(2, a), b + 1):
            c = i * k
            primes[c] = 1

    for i in range(max(n, 2), m + 1):
        if i not in primes:
            arr.add(i)

    return arr


class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
 
    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
 
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a
 
            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]
 
    def set_size(self, a):
        return self.size[self.find(a)]
 
    def __len__(self):
        return self.num_sets


def main():
    n,W=map(int,input().split())
    wt=[]
    val=[]
    for i in range(n):
        w,v=map(int,input().split())
        wt.append(w)
        val.append(v)
    t=[[-1 for i in range(W+1)] for j in range(n+1)]
    for i in range(n+1):
        t[i][0]=0
    for i in range(W+1):
        t[0][i]=0
    for i in range(1,n+1):
        for j in range(1,W+1):
            if wt[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-wt[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    print(t[n][W])









        

        
    




    





BUFSIZE = 8192

class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    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("\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()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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



if __name__ == "__main__":
    main()

Solution (Python):



import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())

def main():
    N, W = geta(int)
    cur = [0] * (W+1) 

    for i in range(N):
        w, v = geta(int)
        update = cur[:]
        for j in range(w,W+1):
            tmp = cur[j-w] + v
            if tmp > cur[j]: update[j] = tmp
        
        cur = update

    print(cur[W])

if __name__ == "__main__":
    main()

Solution (Python):



import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())


N, W = geta(int)
cur = [0] * (W+1) 

for i in range(N):
    w, v = geta(int)
    update = cur[:]
    for j in range(w,W+1):
        tmp = cur[j-w] + v
        if tmp > cur[j]: update[j] = tmp
    
    cur = update

print(cur[W])

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N, W = geta(int)
cur = [0] * (W+1) 

for i in range(N):
    w, v = geta(int)
    update = cur[:]
    for j in range(w,W+1):
        tmp = cur[j-w] + v
        if tmp > cur[j]: update[j] = tmp
    
    cur = update

print(cur[W])

Solution (Python):
import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n,W+1), dtype='int64')
for i in range(n):
    w, v = map(int , input().split())
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.fmax(dp[i-1, w:], dp[i-1,:W-w+1]+v)
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 _ 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])
 
ans = 0

print(dp[N][W])

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

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

out=0
for i in range(W+1):
    out=max(out,dp[N][i])
print(out)

Solution (Python):
import numpy as np

n, w = list(map(int, input().split()))
wv = np.array([list(map(int, input().split(" "))) for _ in range(n)])

dp = np.zeros((w + 1, n), dtype=np.int)
dp[wv[0, 0] :, 0] = np.full(dp[wv[0, 0] :, 0].shape, wv[0, 1])
for i in range(1, n):
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i, 0], wv[i, 1]
    dp[wNew:, i] = np.fmax(dp[wNew:, i - 1], vNew + dp[:-wNew, i - 1])

print(dp[w, n - 1])

Solution (Python):
N, W = map(int, input().strip().split())
 
values = []
weights = []
 
for _ in range(N):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    
dp = [0]*(W+1)
for i in range(N):
    for w in range(W, weights[i] - 1, -1):
        dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
print(dp[W])

Solution (Python):
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

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

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

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

def solve(N, W):
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp[i][:wi] = dp[i-1][:wi]
        dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)
    return dp[N-1][W]

print(solve(N, W))

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

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

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

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

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

Solution (Python):
def main():
    n,w = map(int, input().split())
    weight = []
    value = []
    for i in range(n):
        wi, vi = map(int, input().split())
        weight.append(wi)
        value.append(vi)
    
    def chmax(a, b):
        if a < b:
            a = b
        return a
    
    dp = [[0 for i in range(100100)] for j in range(110)]

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

            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):
import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin


def solve():
    n,mw = [int(i) for i in stdin.readline().split()]
    iw, iv = [], []
    for _ in range(n):
        w,v = [int(i) for i in stdin.readline().split()]
        iw.append(w)
        iv.append(v)
    dp = [[0 for _ in range(mw+1)] for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(mw+1):
            if iw[i-1] > j: dp[i][j] = dp[i-1][j]
            else: dp[i][j] = max(dp[i-1][j], iv[i-1] + dp[i-1][j-iw[i-1]])
    return dp[-1][-1]

print(solve())

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(w + 1):
        if j - a[i][0] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - a[i][0]] + a[i][1])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[n][w])

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

dp = [0 for _ in range(Max_W + 1)]
dp = np.array(dp)

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


print(dp[Max_W])

Solution (Python):
def knap(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]


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)
print(knap(n,W,w,v))

Solution (Python):
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)



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


result = dp_table[n][w]
print(result)

Solution (Python):
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)



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


result = dp_table[n][w]
print(result)

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(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][j], dp[i + 1][j])          
print(dp[n][w])

Solution (Python):
import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


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

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

print(dp[N][W])

Solution (Python):


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

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

print(dp[N][W])

Solution (Python):
import numpy as np


N, W = map(int, input().split())
wv = np.array([[int(i) for i in input().split()] for j in range(N)])


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


for i in range(N):    
    dp[i+1][:wv[i-1][0]] = dp[i][:wv[i-1][0]]
    dp[i+1][wv[i-1][0]:] = np.maximum(dp[i][wv[i-1][0]:], dp[i][:(W+1)-wv[i-1][0]] + wv[i-1][1])
        

print(dp[N][W])

Solution (Python):




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





if __name__ == "__main__":
    main()

Solution (Python):
def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapSack(W,w,v,n))

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

Solution (Python):


















N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))

def calculate(n, w, arr):
    result = [[0] * (w + 1) for i in range(n + 1)]


    for i in range(n):
        width = arr[i][0]
        value = arr[i][1]
        for j in range(w + 1):

            if j >= width:
                result[i + 1][j] = max(result[i][j - width] + value, result[i + 1][j])

            result[i + 1][j] = max(result[i + 1][j], result[i][j])

    
    print(result[n][w])


calculate(N, W, ARR)

Solution (Python):
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [collections.defaultdict(int) for _ in range(N+1)] 
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for dw,dv in dp[i-1].items():
        dp[i][dw] = max(dp[i][dw],dv)
        if w+dw<=W:
            dp[i][w+dw] = max(dp[i][w+dw],v+dv)
print(max(dp[-1].values()))

Solution (Python):

import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    dp = [0] * (W + 1)
    for w, v in item:
        for i in range(w, W + 1)[::-1]:
            tmp = dp[i - w] + v
            if tmp > dp[i]:
                dp[i] = tmp

    print(max(dp))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def chmax(dp, i, j, b):
    if dp[i][j] < b:
        dp[i][j] = b
        return True
    return False
def main():
    N, W = map(int, input().split())
    goods = []
    for _ in range(N):
        goods.append(list(map(int, input().split())))
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for i in range(N):
        w, v = goods[i][0], goods[i][1]
        for j in range(W+1):
            chmax(dp, i+1, j, dp[i][j])
            if j-w >= 0:chmax(dp, i+1, j, dp[i][j-w]+v)
    print(dp[-1][-1])
if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, W = map(int, input().split())
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    item = [(0, 0)]
    for _ in range(N):
        w, v = map(int, input().split())
        item.append((w, v))

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

    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Solution (Python):
N,W = [int(_n) for _n in input().split()]
A = []
for i in range(N):
    w,v = [int(_n) for _n in input().split()]
    A.append((w,v))
dp = [[0]*(W+1) for _ in range(N)]

for w in range(W+1):
    dp[0][w] = 0 if w < A[0][0] else A[0][1]

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

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