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

Solution (Python):
import itertools as itr
n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

for i, j in itr.product(range(1,n+1), range(1,w+1)):
        jw = j-warr[i]
        if jw <0:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = max(dp[i-1][jw] + varr[i], dp[i-1][j])
        
print(dp[n][w])

Solution (Python):

n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

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

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

DP = [0] * (W+1)
V.sort(key=lambda x: x[1])

for w, v in V:
    for i in range(W, -1, -1):
        if w > i:
            break
        DP[i] = max(DP[i], DP[i-w] + v)

print(DP[W])

Solution (Python):
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0 for i in range(W+1)]
dp=np.array(dp)
for i in range(N):
    dp[w[i]:]=np.maximum(dp[w[i]:],dp[:W-w[i]+1]+v[i])
print(dp.max())

Solution (Python):
N, W = map(int, input().split())
inf = 1 << 60

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

for i in range(1, N + 1):
    wi, vi = map(int, input().split())
    for w in range(0, W + 1):
        dp[i][w] = max(dp[i][w], dp[i - 1][w])
    for w in range(wi, W + 1):
        dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi)
    
ans = max(dp[N])
print(ans)

Solution (Python):
import numpy as np

N_W = list(map(int,input().split()))

N = N_W[0]
W = N_W[1]

w = []
v = []

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

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

for w1,v1 in zip(w,v):

    dp[w1:] = np.maximum(dp[w1:],dp[:W-w1 + 1] + v1)

print(dp.max())

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

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

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


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

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

    print(max(dp[N]))


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


solve2()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N)]


first_item = items[0]
for i in range(W+1):
    if i >= first_item[0]:
        dp[0][i] = first_item[1]


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

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

Solution (Python):

import numpy as np
n,w = map(int, input().split())
 
items = list(map(int, input().split()) for _ in [0]*n)
dp = np.zeros(w+1, dtype='int64')
 
for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())



N, W = 0, 0
Ws, Vs = [0], [0]


def set_inputs():
    global N, W, Ws, Vs
    N, W = get_list_of_int()
    ws, vs = [], []
    for _ in range(N):
        w, v = get_list_of_int()
        ws.append(w)
        vs.append(v)
    Ws, Vs = ws, vs


def main():
    set_inputs()
    values = [0] * (W + 1)
    items = [0] * (W + 1)
    for w in range(1, W + 1):
        values[w], items[w] = max((values[w - Ws[i]] + Vs[i], items[w - Ws[i]] | 1 << i) if w - Ws[i] >= 0 and (items[w - Ws[i]] & 1 << i) == 0 else (values[w-1], items[w-1]) for i in range(N))
    print(values[W])


if __name__ == '__main__':
    main()

Solution (Python):
n,w=map(int,input().split())
wv=[]
dp=[[0 for i in range(100010)]for j in range(110)]
for i in range(n):
    a=[int(j) for j in input().split()]
    wv.append(a)

from operator import itemgetter
wv.sort(key=itemgetter(0))

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

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

items = list(map(int, input().split()) for _ in [0]*n)
dp = np.zeros(w+1, dtype='int64')

for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())

Solution (Python):
n,k = [int(i) for i in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(i) for i in input().split()]
    w.append(a)
    v.append(b)

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

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

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

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

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

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

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

for i in range(N) :
    weight_i,value_i = L[i]
    for weight in range(W+1) :
        if weight-weight_i >= 0 :
            dp[i+1][weight] = max(dp[i][weight-weight_i]+value_i, dp[i][weight])
        else :
            dp[i+1][weight] = dp[i][weight]

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

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

dp = [{0:0} for i in range(N+1)]
for i,(w,v) in enumerate(src):
    for w0,v0 in dp[i].items():
        if w0 not in dp[i+1]:
            dp[i+1][w0] = v0
        else:
            dp[i+1][w0] = max(dp[i+1][w0], v0)
        if w0+w > W: continue
        if w0+w not in dp[i+1]:
            dp[i+1][w0+w] = v0+v
        else:
            dp[i+1][w0+w] = max(dp[i+1][w0+w], v0+v)
print(max(dp[-1].values()))

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

DP = [0]*(W+1)
for _ in range(N):
    DP2 = [0]*(W+1)
    w, v = inpl()
    for i in range(w):
        DP2[i] = DP[i]
    for i in range(w, W+1):
        DP2[i] = max(DP[i], DP[i-w]+v)
    DP = DP2
print(DP[-1])

Solution (Python):

n, w = map(int, raw_input().split())
items = []
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))

dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    wi, vi = items[i - 1]
    for j in range(1, w + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if j >= wi:
            dp[i][j] = max(dp[i][j], vi + dp[i - 1][j - wi])
print(dp[n][w])

Solution (Python):
from sys import stdin

n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

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




i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][wi] = vi
    else:
        for X in xrange(wi):
            dp[i][X] = dp[i - 1][X]
        for X in xrange(wi, W + 1):
            dp[i][X] = max(dp[i - 1][X], dp[i - 1][X - wi] + vi)

    i += 1

print max(dp[n - 1])

Solution (Python):
import numpy as np
from inspect import signature

N, W = map(int, input().split())
w = [0]
v = [0]
for i in range(N):
    tw, tv = map(int, input().split())
    w.append(tw)
    v.append(tv)
w = np.array(w)
v = np.array(v)

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

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


print(dp[N][W])

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

Solution (Python):
from sys import stdin

N, W = map(int, stdin.readline().split())
dp = [0] * (W + 1)
for i in range(N):
    w, v = [int(k) for k in stdin.readline().split()]
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)
print(dp[W])

Solution (Python):

from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)

for n in range(1, N + 1):
    w0, v0 = s[n - 1]
    for w in range(W, w0 - 1, -1):

        dp[w] = max(dp[w], dp[w - w0] + v0)

print(dp[W])

Solution (Python):

from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print(dp[W])

Solution (Python):

from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w],
                             dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print(dp[W])

Solution (Python):

from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

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

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

print(dp[N][W])

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

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

for item in range(N) :
    weight_i,value_i = L[item]
    for weight in range(W+1) :
        if weight - weight_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight - weight_i] + value_i)
        else :
            dp[item+1][weight] = dp[item][weight]
ans = dp[N][W]

print(ans)

Solution (Python):
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]


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

for j in range(k+1):
    if j >= e[0][0]:
      dp[0][j]=e[0][1]

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

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

Solution (Python):
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]


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

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

print(max(dp[0]))

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

for w, v in a:
    max_w = min(max_weight, W-w)
    for old_v, from_i in zip(dp[max_w::-1], range(max_w, -1, -1)):
        if dp[from_i+w] < old_v + v:
            dp[from_i+w] = old_v + v
    max_weight = min(max_weight+w, W)

print(max(dp))

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, W = map(int, raw_input().split())
DP = [0] * (W + 1)
for _ in range(N):
    w, v = map(int, raw_input().split())
    for i in range(w, W + 1)[::-1]:
        DP[i] = max(DP[i], DP[i - w] + v)

print DP[W]

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

for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_w in range(k+1):
        if sum_w - w[i] >=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - w[i]] + v[i])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

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

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

for item in range(N) :
    weight_i,value_i = L[item]
    for weight in range(W+1) :
        if weight - weight_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight - weight_i] + value_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)

Solution (Python):
N,W = map(int,input().split())
L = list(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) :
    w_i,v_i = L[i]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[i+1][weight] = max(dp[i][weight], dp[i][weight - w_i] + v_i)
        else :
            dp[i+1][weight] = dp[i][weight]

ans = dp[-1][-1]

print(ans)

Solution (Python):
N,W = map(int,input().split())
L = list(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 item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)

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

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

for i in range(n):
    w, c = IN()
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)
    
print(int(dp[-1]))

Solution (Python):



import numpy as np
N,W = list(map(int, input().split()))

wvlist = sorted( [ [int(x) for x in input().split()] for _ in range(N)] ) 

dp = [0] * (W+1)
cnt = 0
for w,v in wvlist:
    cnt = cnt+w
    for i in range(min(cnt, W), w-1, -1):
        if dp[i] < dp[i-w]+v:
            dp[i] = dp[i-w] + v

print(max(dp))

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


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, W = MAP()
wN, vN = [0]*N, [0]*N
for i in range(N):
    wN[i], vN[i] = MAP()


dp = [[0] * (W+1) for i 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 + wN[i] <= W:
            
            dp[i+1][j+wN[i]] = max(dp[i+1][j+wN[i]], dp[i][j] + vN[i])
print(dp[N][W])

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

Solution (Python):
N, W = map(int, input().split())
cf=sorted( [ [int(x) for x in input().split()] for _ in range(N) ] )
dp = [0]*(W+1)
cnt=0
for w, c in cf:
    cnt=cnt+w
    for i in range(min(cnt, W), w-1, -1):
        if dp[i]<dp[i-w]+c:
            dp[i]=dp[i-w]+c
print(max(dp))

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

Solution (Python):
import sys
 
n, we = map(int, input().split())
 
cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )
 
dp=[0]*(we+1)
cnt=0
 
for w,c in cf:
    cnt=cnt+w
    for j in range(min(cnt, we-w), -1, -1):
        if dp[j+w]<(dp[j] + c): dp[j+w]=dp[j] + c
 
print(max(dp))

Solution (Python):
import sys

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

cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )

dp=[0]*(we+1)
cnt=0

for w,c in cf:
    cnt=cnt+w
    for j in range(min(cnt, we-w), -1, -1):
        if dp[j+w]<(dp[j] + c): dp[j+w]=dp[j] + c

print(max(dp))

Solution (Python):
import sys

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

cf=[(0, 0)]*n

cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print(max(dp))

Solution (Python):
import sys

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

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in sys.stdin.readline().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print(max(dp))

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

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print(max(dp))

Solution (Python):
import sys

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

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, sys.stdin.readline().split()) )

dp=[0]*(we+1)

best=0

for i in range(1, n+1):
    for j in reversed(range(cf[i][0], we+1)):
        dp[j]=max( dp[j], dp[j-cf[i][0]]+ cf[i][1] )
        
    best=max(best, dp[we])


print(best)

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

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

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

best=0

for i in range(1, n+1):
    for j in range(cf[i][0]):
        dp[i][j]=dp[i-1][j]
    for j in range(cf[i][0], we+1):
        dp[i][j]=max( dp[i][j-1], dp[i-1][j], dp[i-1][j-cf[i][0]]+ cf[i][1] )
    best=max(best, dp[i][we])


print(best)

Solution (Python):
import numpy as np 

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

w_all = np.zeros(W + 1, dtype=int)

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

print(w_all[W])

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

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

dp = [-INF] * (capW+1)
dp[0] = 0
for wi, vi in items:
    for w in reversed(range(capW+1)):
        if dp[w] == -INF: continue
        if w+wi <= capW:
            dp[w+wi] = max(dp[w+wi], dp[w] + vi)

print(max(dp))

Solution (Python):
from sys import stdin, stdout

INF = float('inf')
n, W = map(int, stdin.readline().split())

dp = [[-INF for i in range(W + 1)] for j in range(2)]
dp[0][0] = 0
cur = 0

for i in range(n):
    w, c = map(int, stdin.readline().split())
    for j in range(W + 1):
        dp[cur ^ 1][j] = max(dp[cur ^ 1][j], dp[cur][j])
        
        if j + w <= W:
            dp[cur ^ 1][j + w] = max(dp[cur ^ 1][j + w], dp[cur][j] + c)
        
        dp[cur][j] = -INF
    
    cur ^= 1

stdout.write(str(max(dp[cur])))

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


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

Solution (Python):
def main():
  N, W = list(map(int, input().split()))
  Data = []
  for i in range(N):
    Data.append(list(map(int, input().split())))
  
  DP = [0 for i in range(W+1)]
  
  for i in range(N):
    for j in range(W - Data[i][0], -1, -1):
      k = j + Data[i][0]
      DP[k] = max(DP[j] + Data[i][1], DP[k])
  
  print(DP[-1])
  
main()

Solution (Python):
import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i, wi in itr.product(range(1, n+1), range(1, wmax+1)):
    if wi-w[i] >= 0:
        dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
    else:
        dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])

Solution (Python):
import numpy as np
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,wmax=IL()
dp=np.zeros(wmax+1,dtype=int)
for i in range(n):
    w,v=IL()
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[wmax])

Solution (Python):
import numpy as np

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

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

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

print(value[-1])

Solution (Python):
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    vals = list(map(int, input().split()))
    w.append(vals[0])
    v.append(vals[1])

dp = [0] * (W + 1)
for i in range(n):
    for j in reversed(range(W - w[i] + 1)):
        dp[w[i] + j] = max(dp[w[i] + j], dp[j] + v[i])
print(dp[W])

Solution (Python):
N,W=map(int,input().split())
weight=[0]*N
value=[0]*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(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]
print(dp[N][W])

Solution (Python):
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print(max([v for k, v in dp.items()]))

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

dp = [0]*(W+1)

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

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

print(dp[N][W])

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

Solution (Python):


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

DP = np.zeros(W+1, dtype=int)

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

Solution (Python):


N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [0] * (W+1)

for i in range(N):
    for weight in range(W,-1,-1):
        if weight - w[i] < 0 :continue
        DP[weight] = max(DP[weight], DP[weight - w[i]] +v[i])
print(DP[-1])

Solution (Python):

import sys
import numpy as np


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

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

print(dp[W])

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

for i in range(N):
    for w in range(W+1):
        if w-c[i][0] < 0:
            DP[i+1][w] = DP[i][w]
        else:
            DP[i+1][w] = max(DP[i][w-c[i][0]]+c[i][1],DP[i][w])
print(DP[N][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 n_ in range(1, n+1):
    for w_ in range(1, w+1):
        temp_w = wv[n_-1][0]
        temp_v = wv[n_-1][1]
        
        if temp_w <= w_:
            dp[n_][w_] = max(dp[n_-1][w_-temp_w]+temp_v, dp[n_-1][w_])
        else:
            dp[n_][w_] = dp[n_-1][w_]

print(dp[n][w])

Solution (Python):
N, W = map(int, input().split())
W_list = []
V_list = []
for i in range(N):
    w, v = map(int, input().split())
    W_list.append(w)
    V_list.append(v)
dp = [[0]*(W+1)]
for n in range(N):
    tmp = [0] * (W + 1)
    tmp_w = W_list[n]
    tmp_v = V_list[n]
    for w in range(W+1):
        if w-tmp_w >= 0:
            tmp[w] = max(dp[-1][w], dp[-1][w-tmp_w] + tmp_v)
        else:
            tmp[w] =dp[-1][w]
    dp.append(tmp)
print(dp[-1][-1])

Solution (Python):
N,W=map(int, raw_input().split())
A=[ map(int, raw_input().split())  for i in range(N) ] 

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

for w,v in A:
	for i in range(W,-1,-1):
		if dp[i] is not None:
			if 0<=i+w<=W:
				dp[i+w]=max( dp[i+w],  dp[i]+v )
print max(dp)

Solution (Python):
N, W = map(int, input().split())
X = [0] + [-1] * W

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

print(max(X))

Solution (Python):
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
T=zeros(W+1,'i8')
exec('w,v=f();T[w:]=maximum(T[w:],T[:-w]+v);'*N)
print(T[-1])

Solution (Python):
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
J=arange(0,W+1,1,'i8')
T=J*0
exec('w,v=f();T=maximum(T,(T[J-w]+v)*(J>=w));'*N)
print(T[-1])

Solution (Python):
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
J=arange(0,W+1,1,'i8')
T=J*0
exec('w,v=f();T=maximum(T,(T[J-w]+v)*(J>=w));'*N)
print(T[-1])