Problem:


Huge Knapsack Problem

You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

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
v1 w1
v2 w2
:
vN wN

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 ≤ vi ≤ 1015
	

 1 ≤ wi ≤ 1015

 1 ≤ W ≤ 1015
	

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



Sample input:
4 5
4 2
5 2
2 1
8 3


Sample output:
13

Submission status: Wrong Answer

Solution code:
import bisect

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


def make_half_knapsack(hn, items):
    hk = {}
    for i in range(1, 1 << hn):
        vs, ws = 0, 0
        j, k = i, 0
        while j:
            if j & 1:
                v, w = items[k]
                vs += v
                ws += w
            j >>= 1
            k += 1
        if ws not in hk or hk[ws] < vs:
            hk[ws] = vs
    return hk


hn = n // 2
hk = make_half_knapsack(hn, items[:hn])
hk1w = sorted(hk.keys())
hk1v = [hk[w] for w in hk1w]

hk = make_half_knapsack(n - hn, items[hn:])
ans = 0

for w2, v2 in hk.items():
    i = bisect.bisect(hk1w, knapsack - w2)
    ans = max(ans, max(hk1v[:i], default=0) + v2)

print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
v = [0]*N;w = [0]*N

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

value = [0 for i in range(W+1)]
for i in range(N):
    for j in range(W,W-w[i]*2,-1):
        if j>=w[i]:
            value[j] = max(value[j],value[j-w[i]]+v[i])

print(value[W])

Submission status: Wrong Answer

Solution code:
def solve():
    from bisect import bisect_left
    N, W = map(int, input().split())
    n1 = N//2
    n2 = N-n1
    a1 = [tuple(map(int, input().split())) for _ in [0]*n1]
    a2 = [tuple(map(int, input().split())) for _ in [0]*n2]
    dp1, dp2 = [(0, 0) for _ in [0]*(2**n1)], [(0, 0) for _ in [0]*(2**n2)]

    for a, dp in ((a1, dp1), (a2, dp2)):
        n = len(a)
        append = dp.append
        for bit in range(1, 2**n):
            v, w = 0, 0
            for i in range(n):
                if 2**i & bit:
                    v += a[i][0]
                    w += a[i][1]
            if w <= W:
                dp[bit] = (w, v)
        dp = sorted(dp)
        dp = [pair for w in [[0]] for sa in [w.__setitem__] for pair in dp if pair[1] > w[0] and not sa(0, pair[1])]

    result = 0
    inf = float("inf")
    l = len(dp2)
    for w, v in dp1:
        i = bisect_left(dp2, (W-w, inf))
        newv = v + dp2[i-1][1] if i > 0 else 0

        if newv > result:
            result = newv

    print(result)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    from bisect import bisect_left
    N, W = map(int, input().split())
    n1 = N//2
    n2 = N-n1
    a = [[tuple(map(int, input().split())) for _ in [0]*n1], [tuple(map(int, input().split())) for _ in [0]*n2]]
    dp = [[(0, 0) for _ in [0]*(2**n1)], [(0, 0) for _ in [0]*(2**n2)]]

    for i in range(2):
        n = len(a[i])
        cdp = dp[i]
        ca = a[i]
        for j in range(n):
            _v, _w = ca[j]
            if _w > W:
                continue
            for bitset in range(2**j, 2**(j+1)):
                v, w = _v, _w
                j = 1
                for k in range(j-1):
                    if 2**k & bitset:
                        v += ca[k][0]
                        w += ca[k][1]
                if w <= W:
                    cdp[bitset] = (w, v)
            cdp = sorted(cdp)
        dp[i] = [pair for w in [[-1]] for sa in [w.__setitem__] for pair in cdp if pair[1] > w[0] and not sa(0, pair[1])]

    result = 0
    inf = float("inf")
    l = len(dp[1])
    for w, v in dp[0]:
        i = bisect_left(dp[1], (W-w, inf))
        newv = v + dp[1][i-1][1] if i > 0 else 0
        #print(w, v, i, newv)

        if newv > result:
            result = newv

    print(result)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    from bisect import bisect_left
    N, W = map(int, input().split())
    n1 = N//2
    n2 = N-n1
    a = [[tuple(map(int, input().split())) for _ in [0]*n1], [tuple(map(int, input().split())) for _ in [0]*n2]]
    dp = [[(0, 0) for _ in [0]*(2**n1)], [(0, 0) for _ in [0]*(2**n2)]]

    for i in range(2):
        n = len(a[i])
        cdp = dp[i]
        ca = a[i]
        for j in range(n):
            if ca[j][1] > W:
                continue
            for bitset in range(2**j, 2**(j+1)):
                v, w = ca[j]
                j = 1
                for k in range(j-1):
                    if 2**k & bitset:
                        v += ca[k][0]
                        w += ca[k][1]
                if w <= W:
                    cdp[bitset] = (w, v)
        cdp = sorted(cdp)
        dp[i] = [pair for w in [[-1]] for sa in [w.__setitem__] for pair in cdp if pair[1] > w[0] and not sa(0, pair[1])]

    #print(dp)
    result = 0
    inf = float("inf")
    l = len(dp[1])
    for w, v in dp[0]:
        i = bisect_left(dp[1], (W-w, inf))
        newv = v + dp[1][i-1][1] if i > 0 else 0
        #print(w, v, i, newv)

        if newv > result:
            result = newv

    print(result)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

for _ in range(n):
  v, w = map(int, input().split())
  value.append(v)
  weight.append(w)


def search(i, k, acc, vlst, wlst, vwlst):
  if i == k:
    vsum = sum(vlst[i] for i in range(k) if acc[i])
    wsum = sum(wlst[i] for i in range(k) if acc[i])
    vwlst.append([wsum, vsum])
  else:
    search(i + 1, k, acc + [0], vlst, wlst, vwlst)
    search(i + 1, k, acc + [1], vlst, wlst, vwlst)

vw1 = []
vw2 = []

search(0, n // 2, [], value[:n//2], weight[:n//2], vw1)
search(0, n - n // 2, [], value[n//2:], weight[n//2:], vw2)

vw1.sort()
vw2.sort()

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

maxv = 0
for i in range(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)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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


def make_half_knapsack(hn, items):
    hk = {}
    for i in range(1, 1 << hn):
        vs, ws = 0, 0
        j, k = i, 0
        while j:
            if j & 1:
                v, w = items[k]
                vs += v
                ws += w
            j >>= 1
            k += 1
        if ws <= knapsack and (ws not in hk or hk[ws] < vs):
            hk[ws] = vs
    return hk


hn = n // 2
hk = make_half_knapsack(hn, items[:hn])
hk1w = sorted(hk.keys())
hk1v = [hk[w] for w in hk1w]

hk = make_half_knapsack(n - hn, items[hn:])
ans = 0

for w2, v2 in hk.items():
    i = bisect.bisect(hk1w, knapsack - w2)
    ans = max(ans, max(hk1v[:i], default=0) + v2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from bisect import bisect_left
    N, W = map(int, input().split())
    n1 = N//2
    n2 = N-n1
    a = [[tuple(map(int, input().split())) for _ in [0]*n1], [tuple(map(int, input().split())) for _ in [0]*n2]]
    dp = [[(0, 0) for _ in [0]*(2**n1)], [(0, 0) for _ in [0]*(2**n2)]]

    for i in range(2):
        n = len(a[i])
        cdp = dp[i]
        ca = a[i]
        append = cdp.append
        for bit in range(1, 2**n):
            v, w = 0, 0
            for j in range(n):
                if 2**j & bit:
                    v += ca[j][0]
                    w += ca[j][1]
            if w <= W:
                cdp[bit] = (w, v)
        cdp = sorted(cdp)
        dp[i] = [pair for w in [[-1]] for sa in [w.__setitem__] for pair in cdp if pair[1] > w[0] and not sa(0, pair[1])]

    result = 0
    inf = float("inf")
    l = len(dp[1])
    for w, v in dp[0]:
        i = bisect_left(dp[1], (W-w, inf))
        newv = v + dp[1][i-1][1] if i > 0 else 0
        #print(w, v, i, newv)

        if newv > result:
            result = newv

    print(result)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from bisect import bisect_left
    N, W = map(int, input().split())
    n1 = N//2
    n2 = N-n1
    a = [[tuple(map(int, input().split())) for _ in [0]*n1], [tuple(map(int, input().split())) for _ in [0]*n2]]
    dp = [[(0, 0) for _ in [0]*(2**n1)], [(0, 0) for _ in [0]*(2**n2)]]

    for i in range(2):
        n = len(a[i])
        cdp = dp[i]
        ca = a[i]
        for j in range(n):
            if ca[j][1] > W:
                continue
            for bitset in range(2**j, 2**(j+1)):
                #print(bin(bitset))
                v, w = ca[j]
                for k in range(j):
                    if 2**k & bitset:
                        v += ca[k][0]
                        w += ca[k][1]
                if w <= W:
                    cdp[bitset] = (w, v)
        cdp = sorted(cdp)
        dp[i] = [pair for w in [[-1]] for sa in [w.__setitem__] for pair in cdp if pair[1] > w[0] and not sa(0, pair[1])]

    #print(dp)
    result = 0
    inf = float("inf")
    l = len(dp[1])
    for w, v in dp[0]:
        i = bisect_left(dp[1], (W-w, inf))
        newv = v + dp[1][i-1][1] if i > 0 else 0
        #print(w, v, i, newv)

        if newv > result:
            result = newv

    print(result)

if __name__ == "__main__":
    solve()

Submission status: Memory Limit Exceeded

Solution code:
N,W = map(int,input().split())
v = [0]*N;w = [0]*N
 
for i in range(N):
    v[i],w[i] = map(int,input().split())
 
value = [0 for i in range(W+1)]
for i in range(N):
    for j in range(W,-1,-1):
        if j<w[i]:
            value[j] = value[j]
        else:
            value[j] = max(value[j],value[j-w[i]]+v[i])
 
print(value[W])

Submission status: Memory Limit Exceeded

Solution code:
N,W = map(int,input().split())
v = [0]*N;w = [0]*N

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

value = [0 for i in range(W+1)]
for i in range(N):
    for j in range(W,-1,-1):
        if j>=w[i]:
            value[j] = max(value[j],value[j-w[i]]+v[i])

print(value[W])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

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

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


# ===CODE===


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

Submission status: Accepted

Solution code:
"""
半分全列挙
"""
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)

Submission status: Accepted

Solution code:

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)
        # i-1までに作っている組について、iを足すパターンを加える
        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()

    # i+1番目はiより重いが、iより価値が低いなら、i+1の重さまででiの価値ができるやで、に塗り替える
    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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H&lang=ja
# 全列挙する関数
def allp(aa):
    now = [(0, 0)]
    for v, w in aa:
        nxt = [(w + w0, v + v0) for w0, v0 in now]
        now += nxt
    # wでソート
    now.sort(key=lambda x: (x[0], -x[1]))
    # wが昇順ならvも昇順でないと、無駄な組み合わせがあるということなので
    # それを除いて、wとvを別々に返す
    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:])
    # 前半は1つずつ動かして、後半はできるだけ動かさない
    # wの和が制限を越えたら後半は動かす
    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()

Submission status: Accepted

Solution code:
#!python3

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
    #print(W, S)
    while q:
        #print(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()

Submission status: Accepted

Solution code:
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])

    """ 二分探索 """
    # for now in range(len(from_0_to_half_combination)):
    #     now_weight = from_0_to_half_combination[now][0]
    #     now_value = from_0_to_half_combination[now][1]
    #     count = 0
    #     left = 0
    #     right = len(from_0_to_half_combination) - 1
    #     while count < 45:
    #         mid = (left + right) // 2
    #         if now_weight + from_half_to_N_combination[mid][0] > W:
    #             right = mid - 1
    #         else:
    #             ans = max(ans, now_value + from_half_to_N_combination[mid][1])
    #             left = mid + 1
    #         count += 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()

Submission status: Accepted

Solution code:
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]:
        # Use value as negative cost
        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))