Pythonで理解する蟻本「3-2 巨大ナップサック」(p.148)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-2 巨大ナップサック」(p.148)
のコードをPythonで書き直したものとなっています。

入力

入力例

4
2 1 3 2
3 2 4 2
5

解答

from bisect import bisect_left
INF = float('inf')

# 入力
n = int(input())
w = list(map(int,input().split()))
v = list(map(int,input().split()))
W = int(input())

ps = []    # (重さ、価値)

# 前半分を全列挙
n2 = n // 2
for i in range(1 << n2):
    sw = 0
    sv = 0
    for j in range(n2):
        if (i >> j) & 1:
            sw += w[j]
            sv += v[j]
    ps.append((sw, sv))
    
# 無駄な要素を取り除く
ps.sort()
m = 1
for i in range(1, 1 << n2):
    if ps[m - 1][1] < ps[i][1]:
        ps[m] = ps[i]
        m += 1

# 後ろ半分を全列挙し解を求める
res = 0
for i in range(1 << (n - n2)):
    sw = 0
    sv = 0
    for j in range(n - n2):
        if (i >> j) & 1:
            sw += w[n2 + j]
            sv += v[n2 + j]
    if sw <= W:
        tv = ps[bisect_left(ps[:m], (W - sw, INF)) - 1][1]
        res = max(res, sv + tv)

print(res)