Problem:
 Score : 400 points    Problem Statement You have N items and a bag of strength W .
The i -th item has a weight of w_i and a value of v_i .  You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W .  Your objective is to maximize the total value of the selected items.      Constraints  1 ≤ N ≤ 100  1 ≤ W ≤ 10^9  1 ≤ w_i ≤ 10^9  For each i = 2,3,...,N , w_1 ≤ w_i ≤ w_1 + 3 .  1 ≤ v_i ≤ 10^7  W , each w_i and v_i are integers.         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 total value of the selected items.        Sample Input 1 4 6
2 1
3 4
4 10
3 4      Sample Output 1 11  The first and third items should be selected.       Sample Input 2 4 6
2 1
3 7
4 10
3 6      Sample Output 2 13  The second and fourth items should be selected.       Sample Input 3 4 10
1 100
1 100
1 100
1 100      Sample Output 3 400  You can take everything.       Sample Input 4 4 1
10 100
10 100
10 100
10 100      Sample Output 4 0  You can take nothing.

Solution (Python):
from collections import defaultdict

def cumsum(ls):
    for i in range(1,len(ls)):
        ls[i] += ls[i-1]
    ls.insert(0,0)
    return ls

def main():
    n,w = map(int,input().split())
    dc = defaultdict(list)
    W1,V1 = map(int,input().split())
    dc[W1].append(V1)
    for _ in range(1,n):
        wk,vk = map(int,input().split())
        dc[wk].append(vk)

    
    dc = sorted(dc.items(),key=lambda x:x[0],reverse=True)
    for i in range(len(dc)):
        dc[i] = list(dc[i])
        dc[i][1] = cumsum(sorted(list(dc[i][1]),reverse=True))
    
    for i in range(4-len(dc)):
        dc.append([0,[0]])
    can = [0,0] 
    ans = 0
    for i in range(len(dc[0][1])):
        for j in range(len(dc[1][1])):
            for k in range(len(dc[2][1])):
                for l in range(len(dc[3][1])):
                    can[0] = dc[0][0]*i + dc[1][0]*j + dc[2][0]*k + dc[3][0]*l
                    can[1] = dc[0][1][i] + dc[1][1][j] + dc[2][1][k]+ dc[3][1][l]
                    if can[0]<=w:
                        ans = max(ans,can[1])
                    can = [0,0]
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b, c = LS()
    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return


def B():
    a, b, c = LI()
    for i in range(1, b):
        if a * i % b == c:
            print("YES")
            return
    print("NO")
    return


def C():
    _, T = LI()
    t = LI()
    ans = 0
    now = t[0]
    for i in t[1:]:
        if now + T <= i:
            ans += T
        else:
            ans += i - now
        now = i
    print(ans + T)

    return


def D():
    n, W = LI()
    wv = LIR(n)
    wv.sort()
    dp = [-inf] * ((3 * n + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * n, w - 1, -1):
                dp[i] = max(dp[i - w] + v, dp[i])
        print(max(dp[:W + 1]))
    else:
        for w, v in wv:
            w -= minw
            for i in range(min(W // minw, n - 1), 0, -1):
                for k in range(3 * n, w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k - w] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * (3 * n + 1) + W % minw + 1]))
    return


if __name__ == '__main__':
    D()

Solution (Python):

import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    V = [[0] for _ in range(4)]
    for ww, vv in zip(w, v):
        V[ww-w[0]].append(vv)
    V = [[0]+list(accumulate(sorted(v, reverse=True))) for v in V]

    m = 0
    M = N+1
    for i in range(M):
        if i*w[0] > W:
            break
        if len(V[0]) <= i:
            break
        for j in range(M-i):
            if i*w[0] + j*(w[0]+1) > W:
                break
            if len(V[1]) <= j:
                break
            for k in range(M-i-j):
                if i*w[0] + j*(w[0]+1) + k*(w[0]+2) > W:
                    break
                if len(V[2]) <= k:
                    break
                for l in range(M-i-j-k):
                    if i*w[0] + j*(w[0]+1) + k*(w[0]+2) + l*(w[0]+3) > W:
                        break
                    if len(V[3]) <= l:
                        break
                    tot = V[0][i]+V[1][j]+V[2][k]+V[3][l]
                    m = max(m, tot)
    print(m)
    return


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):
N,W,*A=map(int,open(0).read().split());d={0:0}
while A:
 v,w=A.pop(),A.pop()
 for x,y in d.copy().items():
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print(max(d.values()))

Solution (Python):
N,W,*A=map(int,open(0).read().split());d={0:0}
for w,v in zip(A[::2],A[1::2]):
 for x,y in d.copy().items():
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print(max(d.values()))

Solution (Python):
N,W=map(int,input().split());d={0:0}
for _ in [0]*N:
 w,v=map(int,input().split())
 for x,y in d.copy().items():
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print(max(d.values()))

Solution (Python):
N, W = map(int, input().split())
d = {0:0}
for _ in range(N):
  w, v = map(int, input().split())
  for dw, dv in d.copy().items():
    if dw + w <= W:
      d[dw + w] = max(d.get(dw + w, 0), dv + v)
print(max(d.values()))

Solution (Python):
N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [{} for i in range(N + 1)]
def cal(i, w):
  if w in M[i]:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [{} for i in range(N + 1)]
def cal(i, w):
  if w in M[i]:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

Solution (Python):

import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]


def partial_sum(xs):
    if not xs:
        return [0]
    ys = [0, xs[0][1]]
    for i in range(1, len(xs)):
        xs[i][1] += xs[i-1][1]
        ys.append(xs[i][1])
    return ys

n,w=getints()
items=getint2d(n)
w0 = items[0][0]
kind0=list(sorted(filter(lambda s: s[0] == w0,     items), reverse=True))
kind1=list(sorted(filter(lambda s: s[0] == w0 + 1, items), reverse=True))
kind2=list(sorted(filter(lambda s: s[0] == w0 + 2, items), reverse=True))
kind3=list(sorted(filter(lambda s: s[0] == w0 + 3, items), reverse=True))

kind0 = partial_sum(kind0)
kind1 = partial_sum(kind1)
kind2 = partial_sum(kind2)
kind3 = partial_sum(kind3)



res = 0

for n0 in range(len(kind0)):
    for n1 in range(len(kind1)):
        for n2 in range(len(kind2)):
            for n3 in range(len(kind3)):
                weight = n0*w0 + n1*(w0+1) + n2*(w0+2) + n3*(w0+3)
                if weight > w: continue
                tmp = kind0[n0] + kind1[n1] + kind2[n2] + kind3[n3]
                res = max(res, tmp)

print(res)

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

items = [[] for _ in range(4)]
w0, v0 = map(int, input().split())
items[0].append(v0)

for _ in range(N - 1):
    w, v = map(int, input().split())
    items[w - w0].append(v)

for i in range(4):
    items[i].sort(reverse=True)

sumItems = [[0 for _ in range(len(items[i]) + 1)] for i in range(4)]

for i in range(4):
    for j, v in enumerate(items[i]):
        sumItems[i][j + 1] = sumItems[i][j] + v

ans = 0
for firstCount in range(len(items[0]) + 1):
    for secondCount in range(len(items[1]) + 1):
        for thirdCount in range(len(items[2]) + 1):
            for forthCount in range(len(items[3]) + 1):
                sumWeight = w0 * firstCount + (w0 + 1) * secondCount + (w0 + 2) * thirdCount + (w0 + 3) * forthCount
                if sumWeight > W:
                    break
                sumV = 0
                for i, count in enumerate([firstCount, secondCount, thirdCount, forthCount]):
                    sumV += sumItems[i][count]
                ans = max(ans, sumV)

print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n,W = [int(i) for i in readline().split()]
wv = [[int(i) for i in readline().split()] for j in range(n)]

w0 = wv[0][0]

d = [[] for i in range(4)]
for w,v in wv:
    d[w-w0].append(v)

from itertools import accumulate
ac = [None]*4
for i in range(4):
    d[i].sort(reverse=True)
    ac[i] = list(accumulate([0]+d[i]))




ans = 0
di = len(ac[0])
dj = len(ac[1]) 
dk = len(ac[2]) 
dl = len(ac[3])

ac3 = ac[3]
for i in range(di):
    for j in range(min(n+1-i,dj)):
        for k in range(min(n+1-i-j,dk)):
            Wres = i*w0 + j*(w0+1) + k*(w0+2)
            if Wres > W: continue

            res = ac[0][i] + ac[1][j] + ac[2][k]
            idx = (W-Wres)//(w0+3)
            res += ac3[min(dl-1,idx)]
            if ans < res:
                ans = res

print(ans)

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

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

s = [[] for _ in range(4)]
w0 = wv[0][0]
for w, v in wv :
    s[w-w0].append(v)
for i in range(4) :
    s[i].sort(reverse=True)
    s[i] = [0] + s[i]
    for j in range(1, len(s[i])) :
        s[i][j] += s[i][j-1]

M = 0
for i0 in range(len(s[0])) :
    for i1 in range(len(s[1])) :
        for i2 in range(len(s[2])) :
            for i3 in range(len(s[3])) :
                if i0*w0+i1*(w0+1)+i2*(w0+2)+i3*(w0+3) <= W :
                    M = max(M, s[0][i0]+s[1][i1]+s[2][i2]+s[3][i3])
                    
print(M)

Solution (Python):
n,w=map(int,input().split())
w1,v1=map(int,input().split())
l1=[v1]
l2=[]
l3=[]
l4=[]
for _ in range(n-1):
    p=[int(i) for i in input().split()]
    if p[0]==w1:
        l1.append(p[1])
    if p[0]==w1+1:
        l2.append(p[1])
    if p[0]==w1+2:
        l3.append(p[1])
    if p[0]==w1+3:
        l4.append(p[1])
l1.sort()
l2.sort()
l3.sort()
l4.sort()
l1.reverse()
l2.reverse()
l3.reverse()
l4.reverse()
ans=0
for a in range(len(l1)+1):
    for b in range(len(l2)+1):
        for c in range(len(l3)+1):
            for d in range(len(l4)+1):
                if a*w1+b*(w1+1)+c*(w1+2)+d*(w1+3)<=w:
                    ans=max(ans,sum(l1[:a])+sum(l2[:b])+sum(l3[:c])+sum(l4[:d]))
print(ans)

Solution (Python):
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)
ww = [w[0], w[0]+1, w[0]+2, w[0]+3]
d = {}
for i in range(4):
    d[ww[i]] = []
for i in range(N):
    d[w[i]].append(v[i])
for i in range(4):
    d[ww[i]] = sorted(d[ww[i]], reverse=True)
    
ans = 0
for i in range(N+1):
    if len(d[ww[0]]) < i:
        
        break
    for j in range(N+1):
        if i + j > N or len(d[ww[1]]) < j:
            
            break
        for k in range(N+1):
            if i + j + k > N or len(d[ww[2]]) < k:
                
                break
            for l in range(N+1):
                

                if i + j + k + l > N or\
                        len(d[ww[3]]) < l or\
                        ww[0] * i + ww[1] * j +\
                        ww[2] * k + ww[3] * l > W:
                    
                    break

                av = sum([d[ww[0]][p] for p in range(i)])
                bv = sum([d[ww[1]][p] for p in range(j)])
                cv = sum([d[ww[2]][p] for p in range(k)])
                dv = sum([d[ww[3]][p] for p in range(l)])
                ans = max(ans, av+bv+cv+dv)
print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(n)]
mw = wv[0][0]
w = [[] for _ in range(4)]
for i,j in wv:
    w[i-mw].append(j)
for i in range(4):
    w[i].sort(reverse = True)
    w[i] = list(accumulate(w[i]))
w = [[0] + w[i] for i in range(4)]
a,b,c,d = len(w[0]),len(w[1]),len(w[2]),len(w[3])
ans = 0
for i in range(a):
    for j in range(b):
        for k in range(c):
            for l in range(d):
                if i*mw + j*(mw+1) + k*(mw+2) + l*(mw+3) <= W:
                    ans = max(ans,w[0][i]+w[1][j]+w[2][k]+w[3][l])
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,W=map(int,input().split())
w_1,v=map(int,input().split())
w_list=[[] for i in range(4)]
w_list[0].append(v)
for i in range(n-1):
    w,v=map(int,input().split())
    w_list[w-w_1].append(v)
w_cum=[[] for i in range(4)]
for i in range(4):
    w_list[i].sort(reverse=True)
    Sum=0
    w=w_1+i
    for j in range(len(w_list[i])):
        w_cum[i].append((Sum,w*j))
        Sum+=w_list[i][j]
    w_cum[i].append((Sum,w*len(w_list[i])))
a,b,c,d=len(w_cum[0]),len(w_cum[1]),len(w_cum[2]),len(w_cum[3])
ans=0
for h in range(a):
    for i in range(b):
        for j in range(c):
            for k in range(d):
                weight=w_cum[0][h][1]+w_cum[1][i][1]+w_cum[2][j][1]+w_cum[3][k][1]
                if weight<=W:
                    temp=w_cum[0][h][0]+w_cum[1][i][0]+w_cum[2][j][0]+w_cum[3][k][0]
                    ans=max(ans,temp)
print(ans)

Solution (Python):
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in [0]*n]
d={0:0}
for w,v in wv:
    temp=dict()
    for k,i in d.items():
        if k+w in d.keys():
            temp[k+w]=max(d[k+w],i+v)
        else:
            temp[k+w]=i+v
    d.update(temp)
    s=sorted(d.keys())
    m=-1
    for i in s:
        if d[i]<=m:
            del d[i]
        else:
            m=d[i]
print(max([v for w,v in d.items() if w<=W]+[0]))

Solution (Python):
def main():
    N, W = map(int, input().split())
    wv = {0: 0}
    for _ in range(N):
        w, v = map(int, input().split())
        kw = sorted(list(wv.keys()), reverse=True)
        for k in kw:
            if k + w not in wv:
                wv[k + w] = wv[k] + v
            else:
                wv[k + w] = max(wv[k + w], wv[k] + v)
    kw = sorted(list(wv.keys()))
    ans = 0
    for k in kw:
        if k > W:
            break
        ans = max(ans, wv[k])
    print(ans)


main()

Solution (Python):
N, W = map(int, input().split())
wv = []
for _ in range(N):
    w, v = map(int, input().split())
    wv.append((w, v))
memo = [{} for _ in range(N + 1)]


def f(i, j):
    if 0 >= i or 0 >= j:
        return 0
    if j in memo[i]:
        return memo[i][j]
    w, v = wv[i - 1]
    t = f(i - 1, j)
    if j - w >= 0:
        t = max(t, f(i - 1, j - w) + v)
    memo[i][j] = t
    return t


def main():
    print(f(N, W))


main()

Solution (Python):

N,W = map(int,input().split())
WV = [list(map(int,input().split())) for _ in [0]*N]
memo = [{} for _ in [0]*(N+1)]
def dp(i,j):
    if j<=0 or i<=0: return 0
    if j in memo[i]:return memo[i][j]
    w,v = WV[i-1]
    ret = dp(i-1,j)
    if j-w>=0: ret = max(ret,dp(i-1,j-w)+v)
    memo[i][j] = ret
    return ret
print(dp(N,W))

Solution (Python):
N,W = map(int,input().split())
WV = [list(map(int,input().split())) for _ in [0]*N]


dp = [[[0]*(3*N+1) for _ in [0]*(N+1)] for _ in [0]*(N+1)]
w0 = WV[0][0]
for i,wv in enumerate(WV,1):
    w,v = wv
    w -= w0
    for n in range(1,i+1):
        for dW in range(3*N+1):
            if n*w0 + dW > W:break
            if w>dW:
                dp[i][n][dW] = dp[i-1][n][dW]
                continue
            dp[i][n][dW] = max(dp[i-1][n][dW],dp[i-1][n-1][dW-w]+v)
print(max(max(row) for row in dp[-1]))

Solution (Python):


def main():
    num, max_weigh = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    data.sort(key=lambda x: (x[0], -x[1]))
    split_data = []

    pre_data = data[0][0]
    pre_ind = 0
    for i in range(num):
        if pre_data != data[i][0]:
            split_data.append(data[pre_ind:i])
            pre_data = data[i][0]
            pre_ind = i
    split_data.append(data[pre_ind:num])

    while len(split_data) != 4:
        split_data.append([])

    ans = 0

    for i in range(-1, len(split_data[0])):
        if i == -1:
            sum_i = 0
            sum_i_w = 0
        else:
            sum_i += split_data[0][i][1]
            sum_i_w += split_data[0][i][0]
        if sum_i_w > max_weigh:
            break
        ans = max(ans, sum_i)

        for j in range(-1, len(split_data[1])):
            if j == -1:
                sum_j = 0
                sum_j_w = 0
            else:
                sum_j += split_data[1][j][1]
                sum_j_w += split_data[1][j][0]
            if sum_i_w + sum_j_w > max_weigh:
                break
            ans = max(ans, sum_i + sum_j)

            for k in range(-1, len(split_data[2])):
                if k == -1:
                    sum_k = 0
                    sum_k_w = 0
                else:
                    sum_k += split_data[2][k][1]
                    sum_k_w += split_data[2][k][0]
                if sum_i_w + sum_j_w + sum_k_w > max_weigh:
                    break
                ans = max(ans, sum_i + sum_j + sum_k)

                for l in range(-1, len(split_data[3])):
                    if l == -1:
                        sum_l = 0
                        sum_l_w = 0
                    else:
                        sum_l += split_data[3][l][1]
                        sum_l_w += split_data[3][l][0]
                    if sum_i_w + sum_j_w + sum_k_w + sum_l_w > max_weigh:
                        break
                    ans = max(ans, sum_i + sum_j + sum_k + sum_l)

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import sys
from copy import deepcopy
N, W = map(int, raw_input().split())
pre = []
V = 0
for i in range(N):
    w, v = map(int, raw_input().split())
    V += v
    pre.append((w, v))
minw = min(pre)[0]
items1 = []
items2 = []
items3 = []
items4 = []
for w, v in pre:
    if w == minw:
        items1.append((w, v))
    elif w == minw + 1:
        items2.append((w, v))
    elif w == minw + 2:
        items3.append((w, v))
    else:
        items4.append((w, v))
items1.sort(reverse=True)
items2.sort(reverse=True)
items3.sort(reverse=True)
items4.sort(reverse=True)
items = [items1, items2, items3, items4]
memo = {}

def dfs(indice, W, value):
    if W < 0:
        return -(10**9)
    if W < minw or W == 0:
        return value
    if indice in memo:
        return memo[indice]
    outOfAmmo = True
    indicel = list(indice)
    sofar = -(10**9)
    for i in range(4):
        if indice[i] < len(items[i]):
            outOfAmmo = False
            new_indice = deepcopy(indicel)
            new_indice[i] += 1
            current_item = items[i][indice[i]]
            sofar = max(sofar, dfs(tuple(new_indice), W-current_item[0], value+current_item[1]))
    memo[indice] = sofar
    if outOfAmmo:
        return value
    return sofar
print dfs((0, 0, 0, 0), W, 0)

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

DP = [[0] * (3 * N + 1) for _ in range(N + 1)]

for i in range(N):
  for j in range(i, -1, -1):
    for k in range(3 * i, -1, -1):
      kk = k + wv[i][0] - wv[0][0]
      DP[j + 1][kk] = max(DP[j + 1][kk], DP[j][k] + wv[i][1])

ans = 0
for i in range(N + 1):
  if i * wv[0][0] > W:
    break
  for j in range(3 * N + 1):
    if i * wv[0][0] + j > W:
      break
    ans = max(ans, DP[i][j])

print(ans)

Solution (Python):
N, W = map(int, input().split())
w, v = [None] * N, [None] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
wmin = w[0]
_w = [[], [], [], []]
for i in range(N):
    _w[w[i] - wmin].append(v[i])
for i in range(4):
    _w[i].sort(reverse = 1)
    for j in range(1, len(_w[i])):
        _w[i][j] += _w[i][j-1]
    _w[i].insert(0, 0)
ans = 0
for c0 in range(len(_w[0])):
    for c1 in range(len(_w[1])):
        for c2 in range(len(_w[2])):
            for c3 in range(len(_w[3])):
                if wmin * (c0 + c1 + c2 + c3) + c1 + 2 * c2 + 3 * c3 <= W:
                    ans = max(ans, _w[0][c0] + _w[1][c1] + _w[2][c2] + _w[3][c3])
print(ans)

Solution (Python):
from collections import defaultdict
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
w1 = wv[0][0]
ws = []
ijkl = [0,0,0,0]
for i in range(N):
    w = wv[i][0]
    ijkl[w-w1] += 1
for i in range(ijkl[0]+1):
    for j in range(ijkl[1]+1):
        for k in range(ijkl[2]+1):
            for l in range(ijkl[3]+1):
                w = i*w1+j*(w1+1)+k*(w1+2)+l*(w1+3)
                if w <= W:
                    ws.append(w)
ws = list(set(ws))
ws.sort()
dp = [defaultdict(lambda:-float('inf')) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in ws:
        w,v = wv[i]
        dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
print(max(dp[N].values()))

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    base = w[0]
    max_w = 3 * N
    dp = [[-1] * (max_w + 1)  for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(N, -1, -1):
            for k in range(max_w, -1, -1):
                if dp[j][k] >= 0:
                    dp[j + 1][k + w[i] - base] = max(dp[j + 1][k + w[i] - base], dp[j][k] + v[i])
    ret = 0
    for j in range(N + 1):
        for k in range(max_w + 1):
            if base * j + k <= W:
                ret = max(ret, dp[j][k])
    print(ret)
    return


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):
n,l=map(int,input().split())
dic={0:0}
for _ in range(n):
  w,v=map(int,input().split())
  tmp=sorted(list(dic.keys()),reverse=True)
  for key in tmp:
    if key+w not in dic:
      dic[key+w]=dic[key]+v
    else:
      dic[key+w]=max(dic[key]+v,dic[key+w])
tmp=sorted(list(dic.keys()))
ans=0
for key in tmp:
  if key>l:
    break
  ans=max(ans,dic[key])
print(ans)

Solution (Python):
from itertools import accumulate
N, W = map(int, input().split())
Items = [[] for i in range(4)]

w, v = map(int, input().split())
base_w = w
Items[0].append(v)

for i in range(N - 1):
    w, v = map(int, input().split())
    Items[w - base_w].append(v)

for i in range(4):
    Items[i] = [0] + sorted(Items[i], reverse=True)
    Items[i] = list(accumulate((Items[i])))


ans = 0
for w0 in range(len(Items[0])):
    for w1 in range(len(Items[1])):
        for w2 in range(len(Items[2])):
            for w3 in range(len(Items[3])):
                if base_w * w0 + (base_w + 1) * w1 + (base_w + 2) * w2 + (base_w + 3) * w3 > W:
                    continue
                tmp_ans = Items[0][w0] + Items[1][w1] + Items[2][w2] + Items[3][w3]
                ans = max(ans, tmp_ans)

print(ans)

Solution (Python):
N,W = map(int,input().split())
w1,v = map(int,input().split())
wv = [[v],[],[],[]]
for i in range(N-1):
    w,v = map(int,input().split())
    wv[w-w1].append(v)
for i in range(4):
    wv[i]=[0] + sorted(wv[i],reverse=True)

for i in range(4):
    for j in range(1,len(wv[i])):
        wv[i][j] += wv[i][j-1]
ans = 0
hoge = [0,0,0,0]
for i in range(len(wv[0])):
    hoge[0] = wv[0][i]
    for j in range(len(wv[1])):
        hoge[1] = wv[1][j]
        for k in range(len(wv[2])):
            hoge[2] = wv[2][k]
            for l in range(len(wv[3])):
                hoge[3] = wv[3][l]
                if w1*(i+j+k+l)+j+2*k+3*l > W:
                    break
                else:
                    ans = max(ans,sum(hoge))
print(ans)

Solution (Python):
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, W = list(map(int, sys.stdin.readline().split()))
Ws, Vs = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

Ws = np.array(Ws)
Vs = np.array(Vs)

w1 = Ws[0]
ws = np.arange(4) + w1
v1s = Vs[Ws == ws[0]]
v2s = Vs[Ws == ws[1]]
v3s = Vs[Ws == ws[2]]
v4s = Vs[Ws == ws[3]]
v1s.sort()
v2s.sort()
v3s.sort()
v4s.sort()
v1s = np.concatenate([[0], v1s[::-1].cumsum()])
v2s = np.concatenate([[0], v2s[::-1].cumsum()])
v3s = np.concatenate([[0], v3s[::-1].cumsum()])
v4s = np.concatenate([[0], v4s[::-1].cumsum()])

counts = np.array(list(itertools.product(
    range(len(v1s)),
    range(len(v2s)),
    range(len(v3s)),
    range(len(v4s))
)))
counts = counts[np.dot(counts, ws) <= W]

sums = v1s[counts[:, 0]] + \
       v2s[counts[:, 1]] + \
       v3s[counts[:, 2]] + \
       v4s[counts[:, 3]]

print(sums.max())

Solution (Python):
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, W = list(map(int, sys.stdin.readline().split()))
WV = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


dp = defaultdict(int)
dp[0] = 0
for w, v in WV:
    for k, d in list(dp.items()):
        dp[k + w] = max(dp[k + w], d + v)

ans = 0
for w, v in dp.items():
    if w <= W:
        ans = max(ans, v)
print(ans)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right





def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")



N, W = l_inpl()
w, v = [], []
item = [[] for i in range(4)]

for i in range(N):
    wi, vi = l_inpl()
    if i == 0:
        item[0].append(vi)
        w_base = wi
    else:
        item[wi - w_base].append(vi)

w0, w1, w2, w3 = item
w0 = [0] + list(accumulate(sorted(w0, reverse=True)))
w1 = [0] + list(accumulate(sorted(w1, reverse=True)))
w2 = [0] + list(accumulate(sorted(w2, reverse=True)))
w3 = [0] + list(accumulate(sorted(w3, reverse=True)))

ans = 0
for i in range(len(w0)):
    for j in range(len(w1)):
        for k in range(len(w2)):
            tmp_weight = w_base * i + (w_base + 1) * j + (w_base + 2) * k
            if tmp_weight > W:
                continue
            l = min((W - tmp_weight) // (w_base + 3), len(w3) - 1)
            tmp_ans = w0[i] + w1[j] + w2[k] + w3[l]
            ans = max(ans, tmp_ans)

print(ans)

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, W = MI()
    items = [[] for _ in range(4)]
    w0, v0 = MI()
    items[0].append(v0)
    for _ in range(N-1):
        w, v = MI()
        items[w - w0].append(v)
    
    cumsum = [[0] + list(accumulate(sorted(items[i],reverse=True))) for i in range(4)]
    ans=0
    for i,c0 in enumerate(cumsum[0]):
        for j,c1 in enumerate(cumsum[1]):
            for k,c2 in enumerate(cumsum[2]):
                s = i * w0 + j * (w0 + 1) + k * (w0 + 2)
                if s <= W:
                    l = min(len(cumsum[3])-1,(W-s)//(w0+3))
                    ans = max(ans, c0 + c1 + c2 +cumsum[3][l])
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):





from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)

def cmb(n, r):
    if n-r<0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    n,W=map(int,input().split())
    d=defaultdict(int)
    d[0]=0
    for i in range(n):
        w,v=map(int,input().split())
        for k,j in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],j+v)

    print(max(d.values()))
if __name__ == '__main__':
    main()