(2020/07/14追記) ソースコードを優先度付きキュー（heapq）を用いた実装から単純なDFSを用いたものに書き換えました。それに伴い幾つかの箇所を更新しました。
ナップサック問題を分枝限定法(Branch and Bound)で解きます。
分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、
各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作と限定操作から構成される。
全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。
――― wikipedia より
分枝限定法は枝刈り全探索の一種です。
整数計画問題の整数条件を一旦無視して、緩和問題を解きます。これはナップサック問題においては荷物を小数個選択することに相当します。それによって元の問題の解の上界が得られ、暫定解と比較することによって効率的に枝刈りを行うことができると考えられます。詳細は後述の参考記事等をご参照ください。
ナップサック問題を解く手法としては動的計画法(DP)が有名ですが、制約条件に応じてコードを書き分ける必要があります（価値が大きい場合 or 重さが大きい場合 など)。一方で分枝限定法はその汎用性の高さゆえ、複数の場合をカバーできることが期待できます。
#問題
容量$M$のナップサックと$N$種類の荷物(それぞれ価値$V_i$、重さ$W_i$)が与えられる。容量を超えないように荷物を詰めたときの、価値の最大値を求めよ。
#入力
$N$ $M$
$V_1$ $W_1$
$V_2$ $W_2$
$,,\vdots$
$V_N$ $W_N$
#ソースコード(ABC032Dに提出したもの)
関数・変数名が適当なのはお許しのほどを。
不備や改善点などがあれば遠慮なくご教示ください。
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):
# (cur)番目の荷物まで選択済み。(cur+1)番目から順番に取っていく。
# max_v は価値の最大値の候補。 ub_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:
# 暫定解 > 上界 or 荷物の選択が完了
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()
#結果
AtCoder ABC032D - ナップサック問題は、DPによって解く場合は
- $N$ が小さく、$M$, $W_i$, $V_i$が大きい場合。（いわゆる巨大ナップサック問題）
- $W_i$ が大きい場合
- $V_i$ が大きい場合
の３ケースを場合分けする必要がありました。
しかし、分枝限定法を用いれば場合分けの必要はありません。
上記のコードを提出したところ無事AC(34ms)。（提出）
これはnumpyを用いたDPなどと比べても十分に高速と言えるでしょう。
DPを用いる場合と比べても、意外と単純な実装で済みました。
ベテランの方の提出されたコードを見るに、速度面ではもう少し改善の余地がありそうです。
詳細が気になる方は、Python3の提出一覧をご参照ください。
拙い記事とは思いますが、ご覧いただきありがとうございました。
#参考
以下の記事や動画が大変参考になりました。この場にて感謝申し上げます。