Problem:
Huge Knapsack Problem You have N items that you want to put them into a knapsack. Item i has value v i and weight w i . You want to find a subset of items to put such that:  The total value of the items is as large as possible.  The items have combined weight at most W , that is capacity of the knapsack.  Find the maximum total value of items in the knapsack. Input  N  W  v 1  w 1  v 2  w 2 : v N  w N  The first line consists of the integers N and W . In the following N lines, the value and weight of the i -th item are given. Output Print the maximum total values of the items in a line. Constraints  1 ≤ N ≤ 40  1 ≤ v i ≤ 10 15  1 ≤ w i ≤ 10 15  1 ≤ W ≤ 10 15  Sample Input 1 4 5
4 2
5 2
2 1
8 3 Sample Output 1 13 Sample Input 2 2 20
5 9
4 10 Sample Output 2 9

Solution (Python):
def solve():
    from bisect import bisect_right
    N, W = map(int, input().split())
    a = [tuple(map(int, input().split())) for _ in [0]*N]

    def bitdp(items):
        n = len(items)
        dp = [(0, 0) for _ in [0]*(2**n)]
        for bitset in range(1, 2**n):
            for item_num, (item_v, item_w) in enumerate(items):
                if bitset & 2**item_num:
                    w, v = dp[bitset-2**item_num]
                    if w+item_w <= W:
                        dp[bitset] = (w+item_w, v+item_v)
                    break

        dp.sort()
        l, maxv, inf = [(0, 0)], 0, float("inf")
        append = l.append
        for item, (w, v), (nextw, _) in zip(dp, dp, dp[1:]+[(inf, inf)]):
            if w < nextw and maxv < v:
                append(item)
                maxv = v
        return l

    dp1 = bitdp(a[:N//2])
    dp2 = bitdp(a[N//2:])

    inf = float("inf")
    result = 0
    for w, v in dp1:
        total = v + dp2[bisect_right(dp2, (W-w, inf))-1][1]
        if result < total:
            result = total

    print(result)


if __name__ == "__main__":
    solve()

Solution (Python):
n, W = map(int, input().split())
value = []
weight = []

n1 = n // 2
n2 = n - n1

vw1 = [[0, 0]]
vw2 = [[0, 0]]

for _ in range(n1):
  v, w = map(int, input().split())
  sz = len(vw1)
  for i in range(sz):
    p = vw1[i][:]
    p[0] += w
    p[1] += v
    vw1.append(p)

for _ in range(n2):
  v, w = map(int, input().split())
  sz = len(vw2)
  for i in range(sz):
    p = vw2[i][:]
    p[0] += w
    p[1] += v
    vw2.append(p)

vw1.sort()
vw2.sort()

maxv = 0
for i in range(2 ** (n - n // 2)):
  w, v = vw2[i]
  if maxv < v:
    maxv = v
  else:
    vw2[i][1] = maxv


ind1 = 0
ind2 = 2 ** (n - n // 2) - 1
ans = 0
while ind1 < 2 ** (n // 2) and ind2 >= 0:
  w1, v1 = vw1[ind1]
  w2, v2 = vw2[ind2]
  while ind2 > 0 and w1 + w2 > W:
    ind2 -= 1
    w2, v2 = vw2[ind2]
  if w1 + w2 <= W:
    ans = max(ans, v1 + v2)
  ind1 += 1

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,W = LI()
    vw = [LI() for _ in range(n)]

    def rk(vw):
        r = collections.defaultdict(int)
        r[0] = 0
        for v,w in vw:
            rl = list(r.items())
            for rw,rv in rl:
                if rw + w > W:
                    continue
                if r[rw+w] < rv + v:
                    r[rw+w] = rv + v

        t = []
        m = -1
        for w,v in sorted(r.items()):
            if m < v:
                m = v
                t.append((w,v))

        return t

    r1 = rk(vw[:n//2])
    r2 = rk(vw[n//2:])

    i2 = len(r2) - 1
    r = 0
    for w,v in r1:
        while w + r2[i2][0] > W:
            i2 -= 1

        vv = v + r2[i2][1]
        if r < vv:
            r = vv

    return r

print(main())

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def branchAndBound(N, items, lim_w):
	items.sort(key=lambda x: x[0] / x[1], reverse=True)
	Value = []
	Weight = []
	Ratio = []
	for v, w in items:
		Value.append(v)
		Weight.append(w)
		Ratio.append(v / w)

	def upperbound(cur, cur_w, cur_v):
		rest_w = lim_w - cur_w
		max_v = ub_v = cur_v
		for j in range(cur + 1, N):
			if Weight[j] <= rest_w:
				rest_w -= Weight[j]
				max_v += Value[j]
				ub_v = max_v
			else:
				ub_v += Ratio[j] * rest_w
				break
		return max_v, ub_v

	answer_v, ub_v = upperbound(-1, 0, 0)

	def dfs(cur, ub_v, cur_w, cur_v):
		nonlocal answer_v
		if answer_v > ub_v or cur == N:
			return
		if cur_w + Weight[cur] <= lim_w:
			dfs(cur + 1, ub_v, cur_w + Weight[cur], cur_v + Value[cur])
		max_v, ub_v = upperbound(cur, cur_w, cur_v)
		if max_v > answer_v:
			answer_v = max_v
		if ub_v > answer_v:
			dfs(cur + 1, ub_v, cur_w, cur_v)

	dfs(0, ub_v, 0, 0)

	return answer_v


def main():
	N, lim_w = map(int, input().split())
	items = [list(map(int, input().split())) for _ in range(N)]
	print(branchAndBound(N, items, lim_w))


if __name__ == "__main__":
	main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n, w = ns()
    d = []
    for _ in range(n):
        vi, wi = ns()
        d.append([wi, vi])

    def allcase(array):
        res = [[0, 0]]
        for wi, vi in array:
            nxt = [[wi + wt, vi + vt] for wt, vt in res]
            res += nxt
        res.sort(key=lambda x: x[1])
        res.sort()

        maximum = -1
        tres = []

        for wi, vi in res:
            if vi > maximum:
                tres.append([wi, vi])
                maximum = vi

        return tres

    a = allcase(d[:n // 2])
    b = allcase(d[n // 2:])

    a_idx = len(a) - 1
    b_idx = 0
    ans = 0
    while a_idx > -1:
        a_idx -= 1
        b_idx = max(0, b_idx - 1)
        while len(b) > b_idx > -1:
            if a[a_idx][0] + b[b_idx][0] <= w:
                ans = max(ans, a[a_idx][1] + b[b_idx][1])
                b_idx += 1
            else:
                break

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
"""
半分全列挙
"""
from bisect import bisect
N,W = map(int,input().split())
items = []
for i in range(N):
    v,w = map(int,input().split())
    items.append((v,w))
A = [(0,0)]
for i in range(N//2):
    v,w = items[i]
    A += [(v+x,w+y) for x,y in A]
A.sort(key = lambda x: (x[1],-x[0]))
underV = -1
tmpA = []
for v,w in A:
    if underV < v and w <= W:
        tmpA.append((v,w))
        underV = v
A = tmpA

B = [(0,0)]
for i in range(N//2,N):
    v,w = items[i]
    B += [(v+x,w+y) for x,y in B]
B.sort(key = lambda x: (x[1],-x[0]))
underV = -1
tmpB = []
for v,w in B:
    if underV < v and w <= W:
        tmpB.append((v,w))
        underV = v
B = tmpB

ans = 0
BV,BW = zip(*B)
for v,w in A:
    idx = bisect(BW,W-w)-1
    ans = max(ans,BV[idx]+v)

print(ans)

Solution (Python):

from bisect import bisect_right


def main():

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

    d1 = [[0,0]]
    d2 = [[0,0]]
    half = N // 2

    for i in range(half):
        w,v = wv[i]
        size = len(d1)
        
        for j in range(size):
            d1.append([d1[j][0] + w, d1[j][1] + v])

    for i in range(N - half):
        w,v = wv[half + i]
        size = len(d2)
        for j in range(size):
            d2.append([d2[j][0] + w, d2[j][1] + v])

    d1.sort()
    d2.sort()

    
    for i in range(len(d2) - 1):
        if d2[i+1][1] < d2[i][1]:
            d2[i+1][1] = d2[i][1]

    ans = 0
    INF = float("inf")
    for w,v in d1:
        if w > W:
            continue

        rest = W - w
        idx = bisect_right(d2, [rest, INF])
        ans = max(ans, d2[idx - 1][1] + v)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
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

def main():
	N, W = MAP()

	n1 = N // 2
	n2 = N - n1

	vw1 = [[0, 0]]
	vw2 = [[0, 0]]

	for _ in range(n1):
		v, w = MAP()
		for i in range(len(vw1)):
			p = vw1[i].copy()
			p[0] += v
			p[1] += w
			vw1.append(p)

	for _ in range(n2):
		v, w = MAP()
		for i in range(len(vw2)):
			p = vw2[i].copy()
			p[0] += v
			p[1] += w
			vw2.append(p)
	vw1.sort(key=lambda x:(x[1], -x[0]))
	vw2.sort(key=lambda x:(x[1], -x[0]))
	tmp_v = 0
	for i in range(1<<n2):  
		v, w = vw2[i]
		if tmp_v < v:
			tmp_v = v
		else:
			vw2[i][0] = tmp_v

	idx1 = 0
	idx2 = 2 ** n2 - 1
	ans = 0
	while idx1 < 2 ** n1 and idx2 >= 0:  
		v1, w1 = vw1[idx1]
		v2, w2 = vw2[idx2]
		while idx2 > 0 and w1 + w2 > W:
			idx2 -= 1
			v2, w2 = vw2[idx2]
		if w1 + w2 <= W:
			v_sum = v1 + v2
			ans = ans if ans > v_sum else v_sum
		idx1 += 1

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]



def allp(aa):
    now = [(0, 0)]
    for v, w in aa:
        nxt = [(w + w0, v + v0) for w0, v0 in now]
        now += nxt
    
    now.sort(key=lambda x: (x[0], -x[1]))
    
    
    pv = -1
    ww = []
    vv = []
    for w, v in now:
        if v <= pv: continue
        ww.append(w)
        vv.append(v)
        pv = v
    return vv, ww

def main():
    n, wn = MI()
    vw = [LI() for _ in range(n)]
    
    vv1, ww1 = allp(vw[:n // 2])
    vv2, ww2 = allp(vw[n // 2:])
    
    
    ans = 0
    j = len(vv2) - 1
    for v1, w1 in zip(vv1, ww1):
        while w1 + ww2[j] > wn:
            if j == 0:
                print(ans)
                exit()
            else:
                j -= 1
        if v1 + vv2[j] > ans: ans = v1 + vv2[j]
    print(ans)

main()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def resolve():
    N, W = iim()

    S = [list(iim()) for i in range(N)]
    S.sort(key=lambda x: x[0] / x[1], reverse=True)

    def ubounds(w, v, i):
        for j in range(i, N):
            vj, wj = S[j]
            if w + wj > W:
                return (-v, -v - vj / wj * (W - w))
            w += wj
            v += vj

        return (-v, -v)

    v1, v2 = ubounds(0, 0, 0)
    q = []
    heappush(q, (v2, v1, 0, 0, 0))
    vm1 = v1
    
    while q:
        
        vq1, vq2, wq, vq, i = heappop(q)

        if i == N:
            continue

        vi, wi = S[i]
        if wq + wi <= W:
            heappush(q, (vq1, vq1, wq+wi, vq+vi, i+1))
        v1, v2 = ubounds(wq, vq, i + 1)

        if v2 < vm1:
            if v1 < vm1:
                vm1 = v1
            heappush(q, (v2, v1, wq, vq, i + 1))

    print(-vm1)



if __name__ == "__main__":
    resolve()

Solution (Python):
def make_combination(fro, to, value, weight, W):
    """ビット演算が重いのでグレイコードを使った"""
    combination = []
    w = 0
    v = 0
    combination.append([w, v])
    for i in range(1, 1 << (to - fro)):
        code = i ^ (i >> 1)
        bitpos = 0
        while not (1 << bitpos & i):
            bitpos += 1
        if (1 << bitpos & code):
            w += weight[bitpos + fro]
            v += value[bitpos + fro]
        else:
            w -= weight[bitpos + fro]
            v -= value[bitpos + fro]
        combination.append([w, v])

    
    combination.sort()
    for i in range(len(combination) - 1):
        if combination[i][1] > combination[i + 1][1]:
            combination[i + 1][1] = combination[i][1]

    return combination


def cal_ans(from_0_to_half_combination, from_half_to_N_combination, W):
    ans = 0

    """ 尺取り法 """
    left = 0
    right = len(from_half_to_N_combination) - 1
    for left in range(len(from_0_to_half_combination)):
        now_weight = from_0_to_half_combination[left][0]
        now_value = from_0_to_half_combination[left][1]
        while now_weight + from_half_to_N_combination[right][0] > W and right != 0:
            right -= 1
        if now_weight + from_half_to_N_combination[right][0] <= W:
            ans = max(ans, now_value + from_half_to_N_combination[right][1])

    """ 二分探索 """
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    return ans


def main():
    N, W = map(int, input().split())
    half = N // 2
    value = []
    weight = []
    for i in range(N):
        v, w = map(int, input().split())
        value.append(v)
        weight.append(w)

    
    from_0_to_half_combination = make_combination(0, half, value, weight, W)
    from_half_to_N_combination = make_combination(half, N, value, weight, W)

    
    ans = cal_ans(from_0_to_half_combination, from_half_to_N_combination, W)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from typing import Tuple, List
from heapq import heappush, heappop


def max_value(max_weight: int, items: List[Tuple[int, int]]) -> float:
    def _cost(weight: int, value: int, i: int) -> Tuple[int, float]:
        
        for j in range(i, n):
            v, w = items[j]
            if (weight + w > max_weight):
                return (-value, -value - (v / w) * (max_weight - weight))
            weight += w
            value += v
        return (-value, -value * 1.0)

    n = len(items)
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if (cost > maxcost):
            break
        if (i < n):
            v, w = items[i]
            if (weight + w <= max_weight):
                heappush(heap, (cost, upper, weight + w, value + v, i + 1))
            u, c = _cost(weight, value, i + 1)
            if (c < maxcost):
                if (u < maxcost):
                    maxcost = u
                heappush(heap, (c, u, weight, value, i + 1))

    return -maxcost


if __name__ == '__main__':
    N, W = map(lambda x: int(x), input().split())
    items: List[Tuple[int, int]] = []

    for _ in range(N):
        v, w = map(lambda x: int(x), input().split())
        items.append((v, w))

    print(max_value(W, items))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



"""
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(n):
    for j in c:
        if i+j <= n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])
"""

"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
memo = [[] for i in range(w+1)]
for i in range(w):
    for j in range(n):
        if i+b[j][1] <= w and j not in memo[i]:
            if dp[i+b[j][1]] > dp[i]+b[j][0]:
                continue
            else:
                memo[i+b[j][1]] = memo[i]+[j]
                dp[i+b[j][1]] = dp[i]+b[j][0]

print(max(dp))
"""

"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
for i in range(w):
    for j in b:
        if i+j[1] <= w:
            dp[i+j[1]] = max(dp[i+j[1]], dp[i]+j[0])
print(dp[w])
"""

"""
import bisect

n = int(input())
s = [int(input()) for i in range(n)]
dp = [float("INF") for i in range(n)]
for i in range(n):
    dp[bisect.bisect_left(dp,s[i])] = s[i]
print(bisect.bisect_left(dp,100000000000000))
"""


"""
s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = i
for j in range(m+1):
    dp[0][j] = j
for i in range(1,n+1):
    for j in range(1,m+1):
        cost = 0 if s1[i-1] == s2[j-1] else 1
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost)
print(dp[n][m])
"""

"""
import bisect

n,W = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [float("INF") for i in range(10001)]
dp[0] = 0
for v,w in b:
    for i in range(10001):
        if 10000-i+v < 10001:
            dp[10000-i+v] = min(dp[10000-i+v], dp[10000-i]+w)
for i in range(1,10000):
    dp[10000-i] = min(dp[10000-i], dp[10001-i])
print(bisect.bisect_right(dp,W)-1)
"""


"""
n,W = LI()
g = LIR(n)
"""


n,W = LI()
v = [None for i in range(n)]
w = [None for i in range(n)]
for i in range(n):
    v[i],w[i] = LI()
a = [[0,0]]
b = [[0,0]]
m = n//2
for i in range(m):
    for j in range(1<<i):
        a.append([a[j][0]+v[i],a[j][1]+w[i]])
for i in range(n-m):
    for j in range(1<<i):
        b.append([b[j][0]+v[i+m],b[j][1]+w[i+m]])
a.sort(key = lambda x:x[1])
b.sort(key = lambda x:x[1])
ma = b[0][0]
for i in range(1,len(b)):
    if ma > b[i][0]:
        b[i][0] = ma
    else:
        ma = b[i][0]
ans = 0
i = len(b)-1
for v,w in a:
    rem = W-w
    while b[i][1] > rem:
        if i == 0:break
        i -= 1
    if b[i][1] <= rem:
        ans = max(ans,v+b[i][0])
print(ans)


"""
n,e = LI()
v = [[] for i in range(n)]
f = [-1 for i in range(n)]
for i in range(e):
    s,t,d = LI()
    v[s].append([t,d])
    if t == 0:
        f[s] = d
po = [1 for i in range(n+1)]
for i in range(n):
    po[i+1] = po[i]*2
dp = [[float("inf") for i in range(po[n])] for j in range(n)]
dp[0][1] = 0
for j in range(po[n]):
    for x in range(n):
        if po[x]&j:
            for y,d in v[x]:
                if not po[y]&j:
                    dp[y][j|po[y]] = min(dp[y][j|po[y]],dp[x][j]+d)
ans = float("inf")
for i in range(n):
    if f[i] != -1:
        ans = min(ans,dp[i][-1]+f[i])
if ans == float("inf"):
    print(-1)
else:
    print(ans)
"""



"""
h,w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    dp[i][0] = 1 if c[i][0] == 0 else 0
for i in range(w):
    dp[0][i] = 1 if c[0][i] == 0 else 0
for i in range(1,h):
    for j in range(1,w):
        if c[i][j] == 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
ans = 0
for i in dp:
    for j in i:
        ans = max(ans, j)
print(ans**2)
"""





"""
n,v = LI()
a = LI()
b = LI()
c = LI()
d = LI()
p = defaultdict(int)
q = defaultdict(int)
for i in a:
    for j in b:
        if i+j <= v-2:
            p[i+j] += 1
for i in c:
    for j in d:
        if i+j <= v-2:
            q[i+j] += 1
ans = 0
for i,j in p.items():
    ans += j*q[v-i]
print(ans)
"""





"""
n,k = map(int, input().split())
ans = k
for i in range(n-1):
    ans *= k
    ans %= 1000000007
print(ans)
"""


"""
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
n,k = map(int, input().split())
if n > k:
    ans = 0
else:
    ans = fact(k)//fact(k-n)
print(ans%1000000007)
"""


"""
def comb(a,b):
    return fac[a]*inv[b]*inv[a-b]%mod
n,k = LI()
if n < k:
    print(0)
    quit()
fac = [1 for i in range(k+1)]
for i in range(k):
    fac[i+1] = fac[i]*(i+1)%mod
inv = [None for i in range(k+1)]
inv[k] = pow(fac[k],mod-2,mod)
for i in range(k)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
ans = 0
for i in range(k+1):
    if i%2:
        ans -= comb(k,i)*pow(k-i,n,mod)%mod
    else:
        ans += comb(k,i)*pow(k-i,n,mod)%mod
    ans %= mod
print(ans)
"""


"""
n,k = map(int, input().split())
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
ans = fact(n+k-1)//(fact(n)*fact(k-1))%1000000007
print(ans)
"""


"""
def comb(a,b):
    return fac[a]*inv[b]*inv[a-b]%mod
n,k = LI()
if n > k:
    print(0)
    quit()
fac = [1 for i in range(k+1)]
for i in range(k):
    fac[i+1] = fac[i]*(i+1)%mod
inv = [None for i in range(k+1)]
inv[k] = pow(fac[k],mod-2,mod)
for i in range(k)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
print(comb(k,n))
"""


"""
def comb(a,b):
    return fac[a]*inv[b]*inv[a-b]%mod
n,k = LI()
if n < k:
    print(0)
    quit()
fac = [1 for i in range(n+1)]
for i in range(n):
    fac[i+1] = fac[i]*(i+1)%mod
inv = [None for i in range(n+1)]
inv[n] = pow(fac[n],mod-2,mod)
for i in range(n)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
print(comb(n-1,n-k))
"""

Solution (Python):
import bisect
 
n,maxw = map(int , input().split())
data1 = [[0,0]] 
data2 = [[0,0]]
nn = n // 2

for i in range(nn):
    v,w = map(int , input().split())
    sz = len(data1)
    for j in range(sz):
        ppp = data1[j][:]
        ppp[0] += w
        ppp[1] += v
        data1.append(ppp)

for i in range(n-nn):
    v,w = map(int , input().split())
    sz = len(data2)
    for j in range(sz):
        ppp = data2[j][:]
        ppp[0] += w
        ppp[1] += v
        data2.append(ppp)

data2.sort()
maxx = 0
ss = len(data2)
for i in range(ss):
    maxx = max(maxx , data2[i][1])
    data2[i][1] = maxx
ans = 0
ss = len(data1)
for i in range(ss):
    ww , vv = data1[i]
    if (ww > maxw) : continue
    amari = maxw - ww
    ans = max (ans , vv + data2[bisect.bisect_right(data2, [amari , float('inf')])-1][1])

print(ans)

Solution (Python):





from heapq import heappush, heappop


def max_value(t, xs):
    def _cost(weight, value, i):
        for j in range(i, n):
            v, w = xs[j]
            if weight + w > t:
                return (-value, -value - (v/w)*(t-weight))
            weight += w
            value += v
        return (-value, -value*1.0)

    n = len(xs)
    xs.sort(key=lambda x: x[0]/x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if cost > maxcost:
            break
        if i < n:
            v, w = xs[i]
            if weight+w <= t:
                heappush(heap, (cost, upper, weight+w, value+v, i+1))
            u, c = _cost(weight, value, i+1)
            if c < maxcost:
                if u < maxcost:
                    maxcost = u
                heappush(heap, (c, u, weight, value, i+1))

    return -maxcost


def run():
    n, t = [int(i) for i in input().split()]
    xs = []

    for _ in range(n):
        v, w = [int(i) for i in input().split()]
        xs.append((v, w))

    print(max_value(t, xs))


if __name__ == '__main__':
    run()

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

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

def make(S):
    T = {0: 0}
    for v, w in S:
        T0 = dict(T)
        for k, val in T.items():
            if k+w > W:
                continue
            if k+w in T0:
                T0[k+w] = max(T0[k+w], val + v)
            else:
                T0[k+w] = val + v
        T = T0
    v = 0
    R = []
    for k in sorted(T):
        v = max(v, T[k])
        R.append((k, v))
    return R

def solve(T0, T1):
    T0.sort()
    T1.sort(reverse=1)

    it = iter(T1); k1, v1 = next(it)
    yield 0
    for k0, v0 in T0:
        while k0 + k1 > W:
            k1, v1 = next(it)
        yield v0 + v1


T0 = make(S[:N//2])
T1 = make(S[N//2:])

print(max(solve(T0, T1)))

Solution (Python):
import sys
from bisect import bisect_right


def meet_in_the_middle(a: list, limit: int) -> tuple:
    first_v, first_w, second_v, second_w = [], [], [], []
    for items, v_append, w_append in (
            (a[:len(a)//2], first_v.append, first_w.append),
            (a[len(a)//2:], second_v.append, second_w.append)
    ):
        enumerated = [(0, 0)]
        for v, w in items:
            enumerated += [(w+_w, v+_v) for _w, _v in enumerated]

        enumerated.sort()
        enumerated = enumerated[:bisect_right(enumerated, (limit, float("inf")))] + [(limit+1, 0)]
        max_v = -1
        for (cw, cv), (nw, nv) in zip(enumerated, enumerated[1:]):
            if cw < nw and max_v < cv:
                v_append(cv)
                w_append(cw)
                max_v = cv

    return (first_v, first_w), (second_v, second_w)


N, W = map(int, input().split())
a = [list(map(int, l.split())) for l in sys.stdin]

(first_v, first_w), (second_v, second_w) = meet_in_the_middle(a, W)
ans = 0
for v, w in zip(first_v, first_w):
    i = bisect_right(second_w, W-w)-1
    new_v = v + second_v[i]
    if ans < new_v:
        ans = new_v
print(ans)