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):
N,W=map(int,input().split())
wv=[ tuple([int(j) for j in input().split()]) for _ in range(N) ]
w1=wv[0][0]
w2=w1+1
w3=w1+2 
w4=w1+3

wv=sorted(wv,key=lambda x:x[1],reverse=True)
wv=sorted(wv,key=lambda x:x[0])
wvv = list(map(lambda x:x[1], wv))


inf = float("inf")
ans=0
from collections import defaultdict
counter = defaultdict(int)

for i in range(N):
    w,v = wv[i]
    counter[w] += 1

from bisect import bisect_left as bll

for e1 in range(0, counter[w1]+1):
  for e2 in range(0, counter[w2]+1):
    for e3 in range(0,counter[w3]+1):
      for e4 in range(0, counter[w4]+1):
          tmp=0

          if w1*e1 + w2*e2 + w3*e3 + w4*e4 > W:
              continue

          i1=bll(wv, (w1,-inf))
          i2=bll(wv, (w2,-inf))
          i3=bll(wv, (w3,-inf))
          i4=bll(wv, (w4,-inf))

          tmp= tmp \
             +sum(wvv[i1:i1+e1])  \
             +sum(wvv[i2:i2+e2])  \
             +sum(wvv[i3:i3+e3])  \
             +sum(wvv[i4:i4+e4])

          ans=max(ans,tmp)
      
print(ans)

Solution (Python):
from itertools import accumulate
import heapq

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

N, W = map(int, input().split())
first_item = list(map(int, input().split()))
basew = first_item[0]
w0 = []
w1 = []
w2 = []
w3 = []
w0.append(first_item[1])
for _ in range(N-1):
    w, v = map(int, input().split())
    w -= basew
    if w == 0:
        w0.append(v)
    elif w == 1:
        w1.append(v)
    elif w == 2:
        w2.append(v)
    elif w == 3:
        w3.append(v)

w0_acc = [0]+list(accumulate(sorted(w0, reverse=True)))
w1_acc = [0]+list(accumulate(sorted(w1, reverse=True)))
w2_acc = [0]+list(accumulate(sorted(w2, reverse=True)))
w3_acc = [0]+list(accumulate(sorted(w3, reverse=True)))
v = 0
for i0 in range(len(w0)+1):
    for i1 in range(len(w1)+1):
        for i2 in range(len(w2)+1):
            for i3 in range(len(w3)+1):
                if basew*(i0+i1+i2+i3)+3*i3 + 2*i2 + i1 > W:
                    break
                else:
                    v = max(v, w0_acc[i0]+w1_acc[i1]+w2_acc[i2]+w3_acc[i3])
print(v)

Solution (Python):
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1):
    if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)

Solution (Python):



import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

N, W = map(int, input().split())
d = defaultdict(list)
w1 = 0
for n in range(N):
    w, v = map(int, input().split())
    d[w].append(v)
    if n == 0:
        w1 = w


best_ks = {}
for w in range(w1, w + 4):
    vs = sorted(d[w], reverse=True)
    s = 0
    best_k = [0]
    for v in vs:
        s += v
        best_k.append(s)
    best_ks[w] = best_k

ans = 0
for w1_num in range(len(d[w1])+1):
    for w2_num in range(len(d[w1+1])+1):
        for w3_num in range(len(d[w1+2])+1):
            for w4_num in range(len(d[w1+3])+1):
                weight \
                    = w1_num * w1 \
                    + w2_num * (w1 + 1) \
                    + w3_num * (w1 + 2) \
                    + w4_num * (w1 + 3)
                
                if weight > W:
                    continue
                value \
                    = best_ks[w1][w1_num] \
                    + best_ks[w1 + 1][w2_num] \
                    + best_ks[w1 + 2][w3_num] \
                    + best_ks[w1 + 3][w4_num]
                ans = max(ans, value)
print(ans)

Solution (Python):
def solve():
  I=lambda:map(int,input().split())
  N,W=I()
  g={}
  for _ in[0]*N:
    a,b=I()
    g[a]=g.get(a,[])+[b]
  *w,=g.keys()
  v=[]
  for i in range(len(w)):
    s=[0]+sorted(g[w[i]])[::-1]
    for i in range(1,len(s)):
      s[i]+=s[i-1]
    v.append(s)
  for _ in[0]*(4-len(w)):
    w.append(10**18)
    v.append([0])
  ans=0
  for i in range(len(v[0])):
    s0=w[0]*i
    for j in range(len(v[1])):
      s1=s0+w[1]*j
      if s1>W:break
      for k in range(len(v[2])):
        s2=s1+w[2]*k
        if s2>W:break
        l=min((W-s2)//w[3],len(v[3])-1)
        ans=max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l])
  print(ans)
if __name__=='__main__':
  solve()

Solution (Python):
I=lambda:list(map(int,input().split()))
N,W=I()
g={}
for _ in[0]*N:
  a,b=I()
  g[a]=g.get(a,[])+[b]
*w,=g.keys()
v=[]
for i in range(len(w)):
  s=[0]+sorted(g[w[i]])[::-1]
  for i in range(1,len(s)):
    s[i]+=s[i-1]
  v.append(s)
for i in range(len(w),4):
  w.append(10**18+i)
  v.append([0,10**18])
ans=0
for i in range(len(v[0])):
  s0=w[0]*i
  for j in range(len(v[1])):
    s1=s0+w[1]*j
    if s1>W:break
    for k in range(len(v[2])):
      s2=s1+w[2]*k
      if s2>W:break
      l=min((W-s2)//w[3],len(v[3])-1)
      ans=max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l])
print(ans)

Solution (Python):
I=lambda:list(map(int,input().split()))
N,W=I()
g={}
for _ in[0]*N:
  a,b=I()
  g[a]=g.get(a,[])+[b]
*w,=g.keys()
v=[]
for i in range(len(w)):
  s=[0]+sorted(g[w[i]])[::-1]
  for i in range(1,len(s)):
    s[i]+=s[i-1]
  v.append(s)
for i in range(len(w),4):
  w.append(10**18+i)
  v.append([0,10**18])
ans=0
for i in range(len(v[0])):
  s0=w[0]*i
  for j in range(len(v[1])):
    s1=s0+w[1]*j
    if s1>W:break
    for k in range(len(v[2])):
      s2=s1+w[2]*k
      if s2>W:break
      l=min((W-s2)//w[3],len(v[3])-1)
      ans=max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l])
print(ans)

Solution (Python):
from collections import defaultdict
n,ww = map(int,raw_input().split())
dic = defaultdict(list)
m = 10**20
for i in range(n):
    w,v = map(int,raw_input().split())
    m = min(w,m)
    dic[w].append(v)
mxv = 0
for i in dic:
    dic[i].sort(reverse = True)
for w in range(len(dic[m+3])+1):
    for i in range(len(dic[m+2])+1):
        for j in range(len(dic[m+1])+1):
            for k in range(len(dic[m])+1):
                tw = w*(m+3)+i*(m+2)+j*(m+1)+k*(m)
                if tw > ww:
                    continue
                else:
                    val = sum(dic[m+3][:w])+sum(dic[m+2][:i])+sum(dic[m+1][:j])+sum(dic[m][:k])
                    mxv = max(mxv,val)
print mxv

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

N,W = inpl()
H = {0: 0}
for i in range(N):
    w, v = inpl()
    for iw, iv in H.copy().items():
        if iw+w <=W:
            H[iw + w] = max(H.get(iw + w, 0),iv+v)
print(max(H.values()))

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

N,W = inpl()
H = {0: 0}
for i in range(N):
    w, v = inpl()
    for iw, iv in H.copy().items():
        if iw+w <=W:
            H[iw + w] = max(H.get(iw + w, 0),iv+v)
ans = 0
for aw,av in H.items():
    ans = max(ans,av)

print(ans)

Solution (Python):

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

w1 = []
w2 = []
w3 = []
w4 = []


for i in range(N):
    w,v = list(map(int,input().split()))
    if i==0:
        w0 = w
    
    if w==w0:
        w1.append(v)
    elif w==w0+1:
        w2.append(v)
    elif w==w0+2:
        w3.append(v)
    else:
        w4.append(v)

w1.sort()
w1=w1[::-1]

w2.sort()
w2=w2[::-1]

w3.sort()
w3=w3[::-1]

w4.sort()
w4=w4[::-1]
max_V = 0
for i1 in range(len(w1)+1):
    for i2 in range(len(w2)+1):
        for i3 in range(len(w3)+1):
            for i4 in range(len(w4)+1):
                w = i1*w0 + i2*(w0+1) + i3*(w0+2) + i4 * (w0+3)
                if w<=W:
                    V = sum(w1[:i1])+sum(w2[:i2])+sum(w3[:i3])+sum(w4[:i4])
                    max_V = max(V,max_V)

print(max_V)

Solution (Python):
from collections import defaultdict
N, W = map(int, input().split())
dp = defaultdict(int)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for pw, pv in dp.copy().items():
        if pw + w <= W:
            dp[pw + w] = max(dp[pw + w], pv + v)

print(max(dp.values()))

Solution (Python):

n,W = map(int, input().split())
iw,v = map(int, input().split())
d = {
    0: [v]
    ,1: []
    ,2: []
    ,3: []
}
for _ in range(1,n):
    w,v = map(int,input().split())
    d[w-iw].append(v)

for i in range(4):
    d[i] = sorted(d[i], reverse=True)

ret = -1
for i in range(min(n,len(d[0]))+1):
    if i*iw>W:
        break
    for j in range(min(n-i,len(d[1]))+1):
        if i*iw+j*(iw+1)>W:
            break
        for k in range(min(n-(i+j),len(d[2]))+1):
            if i*iw+j*(iw+1)+k*(iw+2)>W:
                break
            for l in range(min(n-(i+j+k),len(d[3]))+1):
                if i*iw+j*(iw+1)+k*(iw+2)+l*(iw+3)>W:
                    continue
                V = sum(d[0][:i])+sum(d[1][:j])+sum(d[2][:k])+sum(d[3][:l])
                ret = max(ret, V)
print(ret)

Solution (Python):
N, W = map(int, input().split())
recW = [[] for i in range(4)]
W0, W1, W2, W3 = 0, 0, 0, 0
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        recW[0].append((w, v))
        W0, W1, W2, W3 = w, w + 1, w + 2, w + 3
    elif w == W0:
        recW[0].append((w, v))
    elif w == W0 + 1:
        recW[1].append((w, v))
    elif w == W0 + 2:
        recW[2].append((w, v))
    else:
        recW[3].append((w, v))

for i in range(4):
    recW[i] = sorted(recW[i], reverse=True)


a, b, c, d = len(recW[0]), len(recW[1]), len(recW[2]), len(recW[3])
recV0 = [0] * (a + 1)
for i in range(1, a + 1):
    recV0[i] = recV0[i - 1] + recW[0][i - 1][1]

recV1 = [0] * (b + 1)
for i in range(1, b + 1):
    recV1[i] = recV1[i - 1] + recW[1][i - 1][1]

recV2 = [0] * (c + 1)
for i in range(1, c + 1):
    recV2[i] = recV2[i - 1] + recW[2][i - 1][1]

recV3 = [0] * (d + 1)
for i in range(1, d + 1):
    recV3[i] = recV3[i - 1] + recW[3][i - 1][1]


num = 0
for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            for l in range(d + 1):
                tmpW = W0 * i + W1 * j + W2 * k + W3 * l
                if tmpW > W:
                    continue
                else:
                    num = max(num, recV0[i] + recV1[j] + recV2[k] + recV3[l])

print(num)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, W = reads()

items = [[] for _ in range(4)]
w1, v1 = reads()
items[0].append(v1)

for _ in range(N-1):
  w, v = reads()
  items[w-w1].append(v)

psums = []
for u in range(4):
  items[u].sort()
  items[u].reverse()
  psums.append([0] +list(accumulate(items[u])))

ans = 0
for p in product(*(range(len(items[u])+1) for u in range(4))):
  if sum((w1+u)*p[u] for u in range(4)) <= W:
    ans = max(ans, sum(psums[u][p[u]] for u in range(4)))
print(ans)

Solution (Python):
n, W = map(int, input().split())
w0, v0 = map(int, input().split())
zero = [v0]
one = []
two = []
three = []

lzero, lone, ltwo, lthree = 1, 0, 0, 0

for _ in range(n - 1):
	w, v = map(int, input().split())
	if w == w0:
		zero.append(v)
		lzero += 1
	elif w == w0 + 1:
		one.append(v)
		lone += 1
	elif w == w0 + 2:
		two.append(v)
		ltwo += 1
	else:
		three.append(v)
		lthree += 1

zero.sort(reverse=True)
one.sort(reverse=True)
two.sort(reverse=True)
three.sort(reverse=True)

zero_sum = [0]
for i in range(len(zero)):
	zero_sum.append(zero_sum[-1] + zero[i])

one_sum = [0]
for i in range(len(one)):
	one_sum.append(one_sum[-1] + one[i])

two_sum = [0]
for i in range(len(two)):
	two_sum.append(two_sum[-1] + two[i])

three_sum = [0]
for i in range(len(three)):
	three_sum.append(three_sum[-1] + three[i])

ans = 0
for i in range(lzero + 1):
	for j in range(lone + 1):
		for k in range(ltwo + 1):
			for l in range(lthree + 1):
				wei = w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l
				val = zero_sum[i] + one_sum[j] + two_sum[k] + three_sum[l]
				if wei <= W and val > ans:
					ans = val

print(ans)

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

from collections import defaultdict
from itertools import accumulate

cs = defaultdict(list)

for w, v in WV:
    cs[w].append(v)

minw = min(cs.keys())

for k in range(minw, minw+4):
    cs[k] = [0] + list(accumulate(sorted(cs[k], reverse=True)))

result = 0

for w0, t0 in enumerate(cs[minw]):
    for w1, t1 in enumerate(cs[minw+1]):
        tw1 = w0 * minw + w1 * (minw+1)
        tv1 = t0 + t1
        if tw1 > W:
            break
        for w2, t2 in enumerate(cs[minw+2]):
            tw2 = tw1 + w2 * (minw+2)
            tv2 = tv1 + t2
            if tw2 > W:
                break
            for w3, t3 in enumerate(cs[minw+3]):
                tw3 = tw2 + w3 * (minw+3)
                tv3 = tv2 + t3
                if tw3 > W:
                    break
                result = max(result, tv3)

print(result)

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

def solve(N, W, WV):
    if N == 0:
        return 0
    if W == 0:
        return 0

from collections import defaultdict
from itertools import accumulate

cs = defaultdict(list)

for w, v in WV:
    cs[w].append(v)

minw = min(cs.keys())

for k in range(minw, minw+4):
    cs[k] = [0] + list(accumulate(sorted(cs[k], reverse=True)))

ts = defaultdict(int)

result = solve(N, W, WV)
result = 0

for w1, t1 in enumerate(cs[minw]):
    for w2, t2 in enumerate(cs[minw+1]):
        tw2 = w1 * minw + w2 * (minw+1)
        tv2 = t1 + t2
        if tw2 > W:
            break
        for w3, t3 in enumerate(cs[minw+2]):
            tw3 = tw2 + w3 * (minw+2)
            tv3 = tv2 + t3
            if tw3 > W:
                break
            for w4, t4 in enumerate(cs[minw+3]):
                tw4 = tw3 + w4 * (minw+3)
                tv4 = tv3 + t4
                
                if tw4 > W:
                    break
                result = max(result, tv4)

print(result)

Solution (Python):
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [long(input_raw[0]), long(input_raw[1])]
    v = []
    item = {}
    v_sum = {}
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [long(input_raw[0]), long(input_raw[1])]
        if wi not in item:
            item[wi] = [vi]
        else:
            item[wi].append(vi)

    for i in range(4 - len(item)):
        item[long(-(i + 1))] = [0L]

    w_list = []
    for wi in item:
        item[wi].sort(reverse = True)
        w_list.append(wi)
        v_sum[wi] = [0L for i in range(len(item[wi]) + 1)]
        v_sum[wi][1] = item[wi][0]
        for i in range(1, len(item[wi])):
            v_sum[wi][i + 1] = v_sum[wi][i] + item[wi][i]

    max_value = 0L
    for i in range(len(item[w_list[0]]) + 1):
        for j in range(len(item[w_list[1]]) + 1):
            for k in range(len(item[w_list[2]]) + 1):
                for l in range(len(item[w_list[3]]) + 1):
                    if W - (i * max(0L, w_list[0]) + j * max(0L, w_list[1]) + k * max(0L, w_list[2]) + l * max(0L, w_list[3])) >= 0:
                        value = v_sum[w_list[0]][i] + v_sum[w_list[1]][j] + v_sum[w_list[2]][k] + v_sum[w_list[3]][l]
                        if max_value < value:
                            max_value = value
    print max_value



























if __name__ == '__main__':
    main()

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


def main():
    w, v = [], []
    for i in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

    dp = [[[0 for k in range(3*MAX_N+1)] for j in range(N+1)] for i in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, i+1):
            for k in range(3*j+1):
                if k - (w[i-1]-w[0]) >= 0:
                    if j * w[0] + k <= W and j > 0:
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-(w[i-1]-w[0])]+v[i-1])
                    else:
                        dp[i][j][k] = 0
                else:
                    dp[i][j][k] = dp[i-1][j][k]

    ans = 0
    for i in range(N+1):
        for j in range(3*i+1):
            ans = max(ans, dp[N][i][j])

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,W=map(int,input().split())
table=[[] for i in range(4)]
a,b = map(int,input().split())
table[0].append(b)
for i in range(1,N):
    w,v = map(int,input().split())
    table[w-a].append(v)
for i in range(4):
    table[i].sort()
    table[i]+=[0]
ans=0
for i in range(len(table[3])+1):
    for j in range(len(table[1])+1):
        for k in range(len(table[2])+1):
            t=(W-a*(i+j+k)-j-2*k-3*i)//a
            if t<0:
                break
            else:
                x=sum(table[3][-i-1:]+table[1][-j-1:]+table[2][-k-1:]+table[0][-t-1:])
                ans=max(ans,x)  
print(ans)

Solution (Python):
ints = input().split(" ")
N = int(ints[0])
maxW = int(ints[1])
ints = input().split(" ")
a = int(ints[0])
b = int(ints[1])
weight = [a, a+1, a+2, a+3] 
va = [[b],[],[],[]]
for i in range(1, N):
	ins = input().split(" ")
	w = int(ins[0])
	v = int(ins[1])
	for j in range(0, 4):
		if w == weight[j]:
			va[j].append(v)
for i in range(0, len(va)):
	va[i].sort(reverse=True)
	va[i].insert(0,0)

sum = [[0],[0],[0],[0]]
for j in range(0, 4):
	for i in range(1, len(va[j])):
		try:
			sum[j].append(sum[j][i-1] + va[j][i])
		except:
			pass
ans = 0

for i in range(0, len(va[0])):
	for j in range(0, len(va[1])):
		for k in range(0, len(va[2])):
			for l in range(0, len(va[3])):
				sumw = weight[0]*i + weight[1]*j +weight[2]*k + weight[3]*l
				if(sumw <= maxW):
					ans = max(sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l],ans)
print(ans)

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

values = [[] for i in range(4)]

w0, v0 = list(map(int, input().split()))
values[0].append(v0)

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

for i in range(4):
    values[i].sort(reverse=True)
    for j in range(len(values[i])-1):
        values[i][j+1] = values[i][j] + values[i][j+1]
    values[i].append(0)

res = 0

for i1 in range(len(values[0])+1):
    for i2 in range(len(values[1])+1):
        for i3 in range(len(values[2])+1):
            for i4 in range(len(values[3])+1):
                if(w0*i1 + (w0+1)*i2 + (w0+2)*i3 + (w0+3)*i4 <= W):
                    res = max(res, values[0][i1-1] + values[1][i2-1] + values[2][i3-1] + values[3][i4-1])

print(res)

Solution (Python):

def inpl(): return list(map(int, input().split()))
from itertools import accumulate, product
 
N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]
 
for w, v in A:
    B[w-w1].append(v)
 
B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]
 
res = 0

for L in product(enumerate(C[0]),
                 enumerate(C[1]),
                 enumerate(C[2]),
                 enumerate(C[3])):
    if sum([(w1+i)*l[0] for i, l in enumerate(L)]) <= W:
        res = max(res, sum([l[1] for l in L]))

print(res)

Solution (Python):

from itertools import accumulate, product
from operator import itemgetter

def inpl(): return tuple(map(int, input().split()))
N, W = inpl()
I = [inpl() for _ in range(N)]
w1 = I[0][0]
A = {w1 + x: [] for x in range(4)}

for w, v in I:
    A[w].append(v)

for k, v in A.items():
    A[k] = [0] + list(accumulate(sorted(v, reverse=True)))

res = 0
g0 = itemgetter(0)
g1 = itemgetter(1)

for L in product(enumerate(A[w1]),
                 enumerate(A[w1+1]),
                 enumerate(A[w1+2]),
                 enumerate(A[w1+3])):
    if sum([(w1+i)*l for i, l in enumerate(map(g0, L))]) <= W:
        res = max(res, sum(map(g1, L)))

print(res)

Solution (Python):

from itertools import accumulate, product

def inpl(): return tuple(map(int, input().split()))
N, W = inpl()
I = [inpl() for _ in range(N)]
w1 = I[0][0]
A = {w1 + x: [] for x in range(4)}

for w, v in I:
    A[w].append(v)

for k, v in A.items():
    A[k] = [0] + list(accumulate(sorted(v, reverse=True)))

res = 0

for L in product(enumerate(A[w1]),
                 enumerate(A[w1+1]),
                 enumerate(A[w1+2]),
                 enumerate(A[w1+3])):
    if sum([(w1+i)*l[0] for i, l in enumerate(L)]) <= W:
        res = max(res, sum([l[1] for l in L]))

print(res)

Solution (Python):


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

ws = []
vs = []

for i in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)

dp = [{} for i in range(N)]
dp[0][ws[0]] = vs[0]
dp[0][0] = 0

for i in range(1,N):
    tmp = dp[i-1].copy()
    for key, value in tmp.items():
        dp[i].setdefault(ws[i]+key, 0)
        dp[i].setdefault(key, 0)
        
        dp[i][ws[i]+key] = max(value+vs[i], dp[i][ws[i]+key])
        dp[i][key] = max(value,dp[i][key])

max_value = 0
for i in range(N):
    tmp = []
    for key, value in dp[i].items():
        if key <= W:
            tmp.append(value)
    if len(tmp)!=0:
        max_value = max(max_value, max(tmp))


print(max_value)

Solution (Python):

def inpl(): return list(map(int, input().split()))
from collections import Counter
from itertools import accumulate, product

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]

for w, v in A:
    B[w-w1].append(v)

B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]

res = 0

for a, b, c, d in product(range(len(C[0])),
                          range(len(C[1])),
                          range(len(C[2])),
                          range(len(C[3]))):
    if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
        res = max(res, C[0][a] + C[1][b] + C[2][c] + C[3][d])
print(res)

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



def kaihou():
    monos_by_omosa = [[] for _ in range(4)]
    w0 = w[0]
    for i in range(N):
        monos_by_omosa[w[i] - w0].append(v[i])
    for i in range(4):
        monos_by_omosa[i].sort()
        monos_by_omosa[i].reverse()
    
    ans = 0
    for i in range(N + 1):
        if i > len(monos_by_omosa[0]):
            break
        w0i = (w0) * i
        if w0i > W:
            break

        for j in range(N + 1 - i):
            if j > len(monos_by_omosa[1]):
                break
            w1j = (w0 + 1) * j
            if w0i + w1j > W:
                break

            for k in range(N + 1 - i - j):
                if k > len(monos_by_omosa[2]):
                    break
                w2k  = (w0 + 2) * k
                if w0i + w1j + w2k > W:
                    break

                for l in range(N + 1 - i - j - k):
                    if l > len(monos_by_omosa[3]):
                        break
                    w3l = (w0 + 3) * l
                    if w0i + w1j + w2k + w3l > W:
                        break

                    val = sum(monos_by_omosa[0][:i])
                    val += sum(monos_by_omosa[1][:j])
                    val += sum(monos_by_omosa[2][:k])
                    val += sum(monos_by_omosa[3][:l])
                    ans = max(ans, val)
    return ans

print(kaihou())

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



def kaihou():
    monos_by_omosa = [[] for _ in range(4)]
    w0 = w[0]
    for i in range(N):
        monos_by_omosa[w[i] - w0].append(v[i])
    for i in range(4):
        monos_by_omosa[i].sort()
        monos_by_omosa[i].reverse()
    
    ans = 0
    for i in range(N + 1):
        if i > len(monos_by_omosa[0]):
            break
        w0i = (w0) * i
        if w0i > W:
            break

        for j in range(N + 1 - i):
            if j > len(monos_by_omosa[1]):
                break
            w1j = (w0 + 1) * j
            if w0i + w1j > W:
                break

            for k in range(N + 1 - i - j):
                if k > len(monos_by_omosa[2]):
                    break
                w2k  = (w0 + 2) * k
                if w0i + w1j + w2k > W:
                    break

                for l in range(N + 1 - i - j - k):
                    if l > len(monos_by_omosa[3]):
                        break
                    w3l = (w0 + 3) * l
                    if w0i + w1j + w2k + w3l > W:
                        break

                    val = sum(monos_by_omosa[0][:i])
                    val += sum(monos_by_omosa[1][:j])
                    val += sum(monos_by_omosa[2][:k])
                    val += sum(monos_by_omosa[3][:l])
                    ans = max(ans, val)
    return ans

print(kaihou())

Solution (Python):


def rec(i, j):
    if (i, j) in dp:
        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


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 = {}
print(rec(0, W))

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

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

from collections import defaultdict
dp = defaultdict(int) 
dp[0] = 0

for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w <= W:
      dp[tw+w] = max(tv+v, dp[tw+w])

print(max(dp.values()))

Solution (Python):
from itertools import izip


def sol(n, w, wis, vis):
    rv = 0
    w1 = wis[0]
    coll = [[] for _ in xrange(n)]
    for wi, vi in izip(wis, vis):
        coll[wi - w1].append(vi)
    coll = map(lambda x: sorted(x, reverse=True), coll)
    lis = map(len, coll)
    for k1 in xrange(min(lis[0] + 1, n + 1)):
        for k2 in xrange(min(lis[1] + 1, n + 1 - k1)):
            for k3 in xrange(min(lis[2] + 1, n + 1 - k1 - k2)):
                for k4 in xrange(min(lis[3] + 1, n + 1 - k1 - k2 - k3)):
                    kis = [k1, k2, k3, k4]
                    if sum([(w1 + i) * kis[i] for i in xrange(4)]) > w:
                        continue
                    rv = max(rv, sum([sum(coll[i][:kis[i]]) for i in xrange(4)]))

    return rv


if __name__ == "__main__":
    n, w = map(int, raw_input().strip().split())
    wis, vis = [], []
    for _ in xrange(n):
        wi, vi = map(int, raw_input().strip().split())
        wis.append(wi)
        vis.append(vi)
    print(sol(n, w, wis, vis))

Solution (Python):
from itertools import product, accumulate

n, w = map(int, input().split())
w1, v1 = map(int, input().split())
packages = [[v1], [], [], []]
for _ in range(n - 1):
    wi, vi = map(int, input().split())
    packages[wi - w1].append(vi)
for ofs, lst in enumerate(packages):
    lst.sort(reverse=True)
    packages[ofs] = list(accumulate([0] + lst))

tmp_max = 0
for a, b, c, d in product(*(range(len(packages[ofs])) for ofs in range(4))):
    if w1 * (a + b + c + d) + b + 2 * c + 3 * d > w:
        continue
    tmp_max = max(tmp_max, sum(packages[ofs][m] for ofs, m in zip(range(4), (a, b, c, d))))
print(tmp_max)

Solution (Python):
from copy import deepcopy

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

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

print( max( map( max, dp ) ) )

Solution (Python):
n,W=map(int,raw_input().split())
wv=[map(int,raw_input().split()) for _ in xrange(n)]
diff=[[0] for _ in xrange(4)]
for i in xrange(n):
    w,v=wv[i]
    diff[w-wv[0][0]].append(v)
for i in xrange(4):
    diff[i].sort(reverse=True)
ans=0
for i in xrange(len(diff[0])):
    for j in xrange(len(diff[1])):
        for k in xrange(len(diff[2])):
            for l in xrange(len(diff[3])):
                if wv[0][0]*(i+j+k+l)+(j+2*k+3*l)<=W:
                    ans=max(ans,sum(diff[0][0:i])+sum(diff[1][0:j])+sum(diff[2][0:k])+sum(diff[3][0:l]))
print ans

Solution (Python):
import sys

def solve():
    N, W = map(int, input().split())
    v = [[] for i in range(4)]

    for i in range(N):
        wi, vi = map(int, input().split())

        if i == 0:
            base = wi
            v[0].append(vi)
        else:
            v[wi - base].append(vi)

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

    ans = 0

    for i in range(len(v[0]) + 1):
        for j in range(len(v[1]) + 1):
            for k in range(len(v[2]) + 1):
                for l in range(len(v[3]) + 1):
                    w = base*i + (base + 1)*j + (base + 2)*k + (base + 3)*l

                    if w > W:
                        continue

                    kakaku = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])

                    ans = max(ans, kakaku)

    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys

def solve():
    N, W = map(int, input().split())
    v = [[] for i in range(4)]

    for i in range(N):
        wi, vi = map(int, input().split())

        if i == 0:
            base = wi
            v[0].append(vi)
        else:
            v[wi - base].append(vi)

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

    ans = 0

    for i in range(len(v[0]) + 1):
        for j in range(len(v[1]) + 1):
            for k in range(len(v[2]) + 1):
                w = base*i + (base + 1)*j + (base + 2)*k

                if w > W:
                    continue

                l = (W - w) // (base + 3)

                kakaku = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])

                ans = max(ans, kakaku)

    print(ans)


if __name__ == '__main__':
    solve()