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 Counter
from itertools import product

N, W = map(int, input().split())
items = {}
weight = []

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    
    if items.get(w, None) is None:
        items[w] = []
    items[w].append(v)
    items[w] = sorted(items[w], reverse = True)

cnt = Counter(weight)

w_num = [] 
w_set = [] 

for w in range(weight[0], weight[0] + 4):
    if cnt[w] == 0:
        continue
    
    w_num.append(range(cnt[w] + 1))
    w_set.append(w)

ans = 0

for i in product(*w_num):
    w = sum(map(lambda x: x[0] * x[1], zip(i, w_set)))
    if 1 > w or w > W:
        continue
    v = sum([sum(items[k][:j]) for j, k in zip(i, w_set)])
    if ans < v:
        ans = v

print(ans)

Solution (Python):



N, W = map(int, input().split())
wl = [0]*N
vl = [0]*N
for i in range(N):
  wl[i], vl[i] = map(int, input().split())

dp = {}
for i in range(len(wl)):
  w, v = wl[i], vl[i]

  newdp = {}
  
  
  for ew, ev in dp.items():
    if ew not in newdp:
      newdp[ew] = ev
    else:
      newdp[ew] = max(newdp[ew], ev)

    if ew + w not in newdp:
      newdp[ew+w] = ev+v
    else:
      newdp[ew+w] = max(newdp[ew+w], ev + v)

  
  if w not in newdp:
    newdp[w] = v
  else:
    newdp[w] = max(newdp[w], v)
    
  dp = newdp

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

Solution (Python):
from collections import Counter
from itertools import product

N, W = map(int,input().split())
w2vl = {}
lw = []

for i in range(N):
    w, v = map(int, input().split())
    lw.append(w)
    if w2vl.get(w, None) is None:
        w2vl[w] = []
    w2vl[w].append(v)
    w2vl[w] = sorted(w2vl[w],reverse=True)

ct = Counter(lw)

args = []
ws = []
for w in range(lw[0], lw[0]+4):
    if ct[w] == 0: continue
    args.append(range(ct[w]+1))
    ws.append(w)

a = 0
for i in product(*args):
    w = sum(map(lambda x: x[0] * x[1] ,zip(i,ws)))
    if 1 > w or w > W: continue
    v = sum([sum(w2vl[k][:j]) for j,k in zip(i,ws)])
    if a < v:
        a = v

print(a)

Solution (Python):
from collections import defaultdict

memo = {}
def dfs(i, w, l, W):
    if i >= len(l):
        return 0

    if (i, w) in memo:
        return memo[(i, w)]

    
    ans = dfs(i + 1, w, l, W)

    
    if w + l[i][0] <= W:
        ans = max(ans, dfs(i + 1, w + l[i][0], l, W) + l[i][1])

    memo[(i, w)] = ans
    return ans


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


if __name__ == '__main__':
    main()

Solution (Python):
import sys



n, W = map(int, input().split())
g = {}
w1 = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        for x in range(w, w + 4):
            g[x] = []
    g[w].append(v)
for w, values in g.items():
    values.sort(reverse=True)

sg = {}
sg[w1] = {}
sg[w1 + 1] = {}
sg[w1 + 2] = {}
sg[w1 + 3] = {}
for a in range(len(g[w1]) + 1):
    sg[w1][a] = sum(g[w1][:a])
for b in range(len(g[w1 + 1]) + 1):
    sg[w1 + 1][b] = sum(g[w1 + 1][:b])
for c in range(len(g[w1 + 2]) + 1):
    sg[w1 + 2][c] = sum(g[w1 + 2][:c])
for d in range(len(g[w1 + 3]) + 1):
    sg[w1 + 3][d] = sum(g[w1 + 3][:d])

res = 0
wa = 0
for a in range(len(g[w1]) + 1):
    wa = w1 * a
    if wa > W:
        continue
    for b in range(len(g[w1 + 1]) + 1):
        wb = (w1 + 1) * b
        if wa + wb > W:
            continue
        for c in range(len(g[w1 + 2]) + 1):
            wc = (w1 + 2) * c
            if wa + wb + wc > W:
                continue
            for d in range(len(g[w1 + 3]) + 1):
                wd = (w1 + 3) * d
                if wa + wb + wc + wd > W:
                    continue
                total_w = wa + wb + wc + wd

                total_v = sg[w1][a] + sg[w1 + 1][b] + sg[w1 + 2][c] + sg[w1 + 3][d]
                if total_v > res:
                    res = total_v
print(res)

Solution (Python):
import sys



n, W = map(int, input().split())
g = {}
w1 = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        for x in range(w, w + 4):
            g[x] = []
    g[w].append(v)
for w, values in g.items():
    values.sort(reverse=True)

sg = {}
sg[w1] = {}
sg[w1 + 1] = {}
sg[w1 + 2] = {}
sg[w1 + 3] = {}
for a in range(len(g[w1]) + 1):
    sg[w1][a] = sum(g[w1][:a])
for b in range(len(g[w1 + 1]) + 1):
    sg[w1 + 1][b] = sum(g[w1 + 1][:b])
for c in range(len(g[w1 + 2]) + 1):
    sg[w1 + 2][c] = sum(g[w1 + 2][:c])
for d in range(len(g[w1 + 3]) + 1):
    sg[w1 + 3][d] = sum(g[w1 + 3][:d])

res = 0
for a in range(len(g[w1]) + 1):
    for b in range(len(g[w1 + 1]) + 1):
        for c in range(len(g[w1 + 2]) + 1):
            for d in range(len(g[w1 + 3]) + 1):
                total_w = w1 * a + (w1 + 1) * b + (w1 + 2) * c + (w1 + 3) * d
                if total_w > W:
                    continue

                total_v = sg[w1][a] + sg[w1 + 1][b] + sg[w1 + 2][c] + sg[w1 + 3][d]
                if total_v > res:
                    res = total_v
print(res)

Solution (Python):
import sys



n, W = map(int, input().split())
g = {}
w1 = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        for x in range(w, w + 4):
            g[x] = []
    g[w].append(v)
for w, values in g.items():
    values.sort(reverse=True)

res = 0
for a in range(len(g[w1]) + 1):
    for b in range(len(g[w1 + 1]) + 1):
        for c in range(len(g[w1 + 2]) + 1):
            for d in range(len(g[w1 + 3]) + 1):
                total_w = w1 * a + (w1 + 1) * b + (w1 + 2) * c + (w1 + 3) * d
                if total_w > W:
                    continue

                total_v = 0
                for i in range(a):
                    total_v += g[w1][i]
                for i in range(b):
                    total_v += g[w1 + 1][i]
                for i in range(c):
                    total_v += g[w1 + 2][i]
                for i in range(d):
                    total_v += g[w1 + 3][i]
                if total_v > res:
                    res = total_v
print(res)

Solution (Python):
def solve(depth, left_w):
	if depth == 4:
		return 0
	res = solve(depth+1, left_w)
	r = 0
	for vi in w4[depth]:
		left_w -= w0+depth
		if left_w < 0:
			break
		r += vi
		res = max(res, r + solve(depth+1, left_w))
	return res

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

w4 = [[] for i in xrange(4)]
for i in xrange(n):
	wi,vi = map(int, raw_input().split())
	if i == 0:
		w0 = wi
	w4[wi-w0].append(vi)
	
for ww in w4:
	ww.sort()
	ww.reverse()

ans = solve(0,w)
print ans

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

dp=[{} for _  in range(N+1)]
def rec(i,j):
    if j in dp[i] :
        return dp[i][j]
    if i==N:
         res=0
    elif j<w[i]:
        res=rec(i+1,j)
    else:
        res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
    dp[i][j]=res
    
    return res

print(rec(0,W))

Solution (Python):
import copy
N, W = [int(i) for i in input().split(' ')]
dic = {}
dic_num = {}
dic4calc  = {}

for i in range(N):
    new_w, new_v = [int(i) for i in input().split(' ')]
    if new_w in dic:
        dic[new_w].append(new_v)
    else:
        dic[new_w] = [new_v]
        
w = sorted(list(dic.keys()))
for wi in w:
    dic[wi].sort(reverse=True)
    dic_num[wi] = len(dic[wi])
    dic4calc[wi] = 0

cond = []
def rec(i, rest, dic4calc):
    if rest<w[i]:
        cond.append(dic4calc)
        return

    if i+1<len(w):
        new_dic4calc = copy.deepcopy(dic4calc)
        rec(i+1, rest, new_dic4calc)
    if not dic_num[w[i]]-dic4calc[w[i]]==0:
        new_dic4calc = copy.deepcopy(dic4calc)
        new_dic4calc[w[i]] += 1
        rec(i, rest-w[i], new_dic4calc)
    if i+1>=len(w):
        cond.append(dic4calc)
        return

rec(0, W, dic4calc)
ans = 0
for c in cond:
    total = 0
    for wi in w:
        total += sum(dic[wi][:c[wi]])
    if ans < total:
        ans = total
        
print(ans)

Solution (Python):
import numpy as np
N, W0 = map(int, raw_input().split())
items = [map(int, raw_input().split()) for i in range(N)]
w0, _ = items[0]
dp = {}
def dfs(i, W):
    if i < 0:
        return 0
    if (i, W) in dp:
        return dp[i, W]
    w, v = items[i]
    res = dfs(i-1, W)
    if W >= w:
        res = max(res, dfs(i-1, W-w) + v)
    dp[i, W] = res
    return res
print dfs(N-1, W0)

Solution (Python):

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

weights = []
values = []
for i in range(N):
    lst = [int(e) for e in input().split()]
    weights.append(lst[0])
    values.append(lst[1])


dp = [{} for j in range(N+1)]

def rec(i, j):
    if j in dp[i]:
        return dp[i][j]

    res = 0
    if i == N:
        res = 0
    elif j < weights[i]:
        res = rec(i+1, j)
    else:
        res = max(
            rec(i+1, j),
            rec(i+1, j-weights[i]) + values[i]
        )

    dp[i][j] = res
    return res


print(rec(0, W))

Solution (Python):

nw = list(map(int, input().split()))
N = nw[0]
w_limit = nw[1]

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


dp = [{} for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    elif(j < w[i]):
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-w[i]) + v[i])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))

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

    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []

    i = 0
    while i < N:
        w, v = map(int, input().split())
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    if w <= W:
                        v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                        ans.append(v)

    print(max(ans))

main()

Solution (Python):
def main():
    N, W = map(int, input().split())
    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []
    i = 0
    while i < N:
        w, v = map(int, input().split())
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                    if w <= W:
                        ans.append(v)

    print(max(ans))

main()

Solution (Python):

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


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

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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


Wmin = min(w)    
w.insert(0,"0")
v.insert(0,"0")
for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]



nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[i]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Solution (Python):
N, W = list(map(int, input().split()))
w0, v0 = list(map(int, input().split()))
w_dict = dict()
w_dict[w0] = [v0]
w_dict[w0+1] = list()
w_dict[w0+2] = list()
w_dict[w0+3] = list()

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

w_dict[w0]   = sorted(w_dict[w0],   reverse=True)
w_dict[w0+1] = sorted(w_dict[w0+1], reverse=True)
w_dict[w0+2] = sorted(w_dict[w0+2], reverse=True)
w_dict[w0+3] = sorted(w_dict[w0+3], reverse=True)

max_sum_v = 0
for i_0 in range(len(w_dict[w0])+1):
    for i_1 in range(len(w_dict[w0+1])+1):
        for i_2 in range(len(w_dict[w0+2])+1):
            for i_3 in range(len(w_dict[w0+3])+1):
                sum_w = w0 * i_0 + (w0 + 1) * i_1 + (w0 + 2) * i_2 + (w0 + 3) * i_3
                if sum_w > W:
                    continue
                sum_v = sum(w_dict[w0][:i_0])   + \
                        sum(w_dict[w0+1][:i_1]) + \
                        sum(w_dict[w0+2][:i_2]) + \
                        sum(w_dict[w0+3][:i_3])
                max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)

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

wv = [list(map(int, input().split())) for i in range(n)]
cache = [{} for x in range(n)]

def solve(i, w):
    if i >= n:
        return 0

    cache_value = cache[i].get(w)
    if cache_value:
        return cache_value

    if w - wv[i][0] >= 0:
        value = max(solve(i + 1, w), solve(i + 1, w - wv[i][0]) + wv[i][1])
        cache[i][w] = value
        return value
    else:
        value = solve(i + 1, w)
        cache[i][w] = value
        return value

print(solve(0, w))

Solution (Python):
N,W=list(map(int,input().split()))
v=[[],[],[],[]]
kosu=[0,0,0,0]
kr=list(map(int,input().split()))
v[0].append(kr[1])
w0=kr[0]
for i in range(1,N):
    kr=list(map(int,input().split()))
    v[kr[0]-w0].append(kr[1])
for i in range(4):
    v[i].sort()
    v[i].reverse()
kos=[len(v[0]),len(v[1]),len(v[2]),len(v[3])]
kk=[-1]*((kos[0]+1)*(kos[1]+1)*(kos[2]+1)*(kos[3]+1))
def toru(a,b,c,d,nw):
    global kk
    if kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]!=-1:
        return kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]
    max=0
    if a<kos[0] and W>=nw+w0 and max<toru(a+1,b,c,d,nw+w0)+v[0][a]:
        max=toru(a+1,b,c,d,nw+w0)+v[0][a]
    if b<kos[1] and W>=nw+w0+1 and max<toru(a,b+1,c,d,nw+w0+1)+v[1][b]:
        max=toru(a,b+1,c,d,nw+w0+1)+v[1][b]
    if c<kos[2] and W>=nw+w0+2 and max<toru(a,b,c+1,d,nw+w0+2)+v[2][c]:
        max=toru(a,b,c+1,d,nw+w0+2)+v[2][c]
    if d<kos[3] and W>=nw+w0+3 and max<toru(a,b,c,d+1,nw+w0+3)+v[3][d]:
        max=toru(a,b,c,d+1,nw+w0+3)+v[3][d]
    kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]=max
    return max
 
 
maxv=toru(0,0,0,0,0)
 
print(maxv)

Solution (Python):

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}


def nap(i,W2):
    
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    
    elif i == 0:
        r = 0
    
    elif W2 < Wmin:
        r = 0
    
    elif W2 < w[i]:
        r = nap(i-1,W2)
    
    elif Wsum[i] <= W2:
        r = Vsum[i]
    
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Solution (Python):


N, W = map(int, raw_input().split(" "))
items = [tuple(map(int, raw_input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print search(0, 0)

Solution (Python):


if __name__ == "__main__":
	n, w = map(int, input().split())
	vs, ws = [], []

	for i in range(n):
		w_, v_ = map(int, input().split())
		ws.append(w_)
		vs.append(v_)

	nap_memo = {}
	def nap(i, j):
		key = str(i)+':'+str(j)

		if key in nap_memo:
			return nap_memo[key]

		r = 0
		if i == n:
			r = 0
		elif j < ws[i]:
			r = nap(i+1, j)
		else:
			r = max(nap(i+1, j),
					nap(i+1, j-ws[i]) + vs[i])

		nap_memo[key] = r
		return r

	print(nap(0, w))

Solution (Python):
n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for _ in range(n)]
d = {}
def f(i,j):
    if i==n:
        return 0
    if (i,j) not in d:
        d[i,j]=f(i+1,j)
        w,v=a[i]
        if j+w<=m:
            d[i,j]=max(d[i,j],v+f(i+1,j+w))
    return d[i,j]
print(f(0,0))

Solution (Python):
N, W = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(N)]
 
dp = {}
dp[0] = 0
 
for w, v in X:
    d = dp.copy()
    for k in d:
        if k + w > W:
            continue
        if k + w in dp:
            dp[k + w] = max(dp[k + w], d[k] + v)
        else:
            dp[k + w] = d[k] + v
 
print max(dp.values())

Solution (Python):
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
	
def f3():
	L.sort(key = (lambda x: - x[1]//x[0]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000000:
	print(f1())
elif W > 10000000:
	print(f3())
else:
	print(f2())

Solution (Python):


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
W=int(hyo[1])

weight=[]
values=[]
for idx in range(0,N,1):
    mozir=input()
    hyo=mozir.split(' ')
    weight.append(int(hyo[0]))
    values.append(int(hyo[1]))

minimum_weight=min(weight)
weight_values=list(range(0,4,1))
for idx in range(0,4,1):
    weight_values[idx]=[]

for idx in range(0,N,1):
    weight_values[weight[idx]-minimum_weight].append(values[idx])

for idx in range(0,4,1):
    weight_values[idx].sort(reverse=True)



jogen=min(W//minimum_weight,len(weight_values[0]))

tmpten=[0,0,0]
tmpomo=[0,0,0]
ans=0
for idx in range(0,jogen+1,1):
    tmpten[0]=sum(weight_values[0][0:idx])
    tmpomo[0]=minimum_weight*idx

    jogen=min((W-tmpomo[0])//(minimum_weight+1),len(weight_values[1]))
    for idy in range(0,jogen+1,1):
        tmpten[1]=tmpten[0]+sum(weight_values[1][0:idy])
        tmpomo[1]=tmpomo[0]+(minimum_weight+1)*idy

        jogen=min((W-tmpomo[1])//(minimum_weight+2),len(weight_values[2]))
        for idz in range(0,jogen+1,1):
            tmpten[2]=tmpten[1]+sum(weight_values[2][0:idz])
            tmpomo[2]=tmpomo[1]+(minimum_weight+2)*idz

            kosuu=min((W-tmpomo[2])//(minimum_weight+3),len(weight_values[3]))
            tmpans=tmpten[2]+sum(weight_values[3][0:kosuu])
            
            ans=max(ans,tmpans)

print(ans)

Solution (Python):
import collections

if __name__ == '__main__':
    N, W = map(int, input().split())

    dp = [collections.defaultdict(int) for _ in range(N + 1)]
    dp[0][0] = 0

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

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

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

dp = {}
dp[0] = 0

for w, v in X:
    d = dp.copy()
    for k in d:
        if k + w > W:
            continue
        if k + w in dp:
            dp[k + w] = max(dp[k + w], d[k] + v)
        else:
            dp[k + w] = d[k] + v

print max(dp.values())

Solution (Python):
from collections import defaultdict
N, W = map(int, raw_input().split())

w = []
v = []
for i in range(0, N):
    w_i, v_i = map(int, raw_input().split())
    w.append(w_i)
    v.append(v_i)

items = sorted([{'w': w[i], 'v': v[i]} for i in range(0, N)],
               lambda i1, i2: cmp(i2['w'], i1['w']))

def default():
    return defaultdict(lambda:-1)

results = defaultdict(default)

def add(i, w_max):
    if results[i][w_max] != -1:
        return results[i][w_max]

    if i == N:
        return 0;

    if w_max < items[i]['w']:
        res = add(i+1, w_max)
    else:
        res = max(
            add(i+1, w_max),
            add(i+1, w_max - items[i]['w']) + items[i]['v']
        )
    results[i][w_max] = res
    return res

print(add(0, W))

Solution (Python):

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

w = []
v = []

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


nap_memo = {}

def nap(i,j):
    key = str(i)+':'+str(j)
    if key in nap_memo:
        return nap_memo[key]
    r = 0
    if i == N:
        r= 0
    elif j < w[i]:
        r= nap(i+1,j)
    else:
        r= max([nap(i+1,j),nap(i+1,j-w[i])+v[i]])

    nap_memo[key] = r
    return r

print(nap(0,W))