「分枝操作」と「限定操作」を行うことで、効率的に問題を解く方法。
（※「上限」「大きい」というのは最大化問題の場合で、最小化問題なら「下限」「小さい」となる）
近い概念に動的計画法があるが、動的計画法は、分枝操作が可能で同じ部分問題を何回も要求される問題に対して、記録して同じ問題を解かないようにする。
分枝限定法は、同じ部分問題が要求されるかは重要ではなく、最適解が得られないことがわかった問題を切り捨てて調べる空間を減らす、というような理解。
緩和問題は適切な唯一の方法があるわけでは無い。 前提が誤っている（緩和問題の解より実際の解が大きくなるなど）でない限り、正しい解は求まる。
より実際の解に近い上限を推定できる緩和問題を採用すれば、より効率的に無駄な探索空間を除外できる。
しかし、緩和問題は部分問題毎に毎回計算するので、これに時間がかかるようでは本末転倒。削減できる探索空間とのトレードオフとなる。
1つめの品物を入れた場合と入れない場合に分割
もし品物が1個単位でなく、「3/5個入れる」ようなことができる場合、解くのは簡単である。
重さあたりの価値 $\frac{v_i}{w_i}$ が高い方から順に、貪欲に詰めていけばよい。
W = 13 v 8 5 9 4 7 1 (v/wの大きい順) w 3 2 5 4 8 2 3番目まで選んで、重さ 3+2+5=10、価値 8+5+9=22 4番目を"3/4個"選んで、価値 22+(4 * 3/4)=25
そして、1個単位でしか詰められない元の問題は、この解より大きくなることは無い。 （どれかを諦めなければならず、空いたスペースに代わりの品物を入れられるとしてもそれは重さあたりの価値効率がより低いため）
つまり上限となる。
ここで、元の問題の探索に戻る。
$\frac{v_i}{w_i}$ の高い方から取る/取らない場合に分割して探索していく。 1～3番目を取って4～6番目を取らなかった時に、価値が22となるという結果が得られたとする。これを暫定最大値とする。
ではここで、1番目を取り2番目を取らなかった場合の、3～6番目からなる部分問題を考える（いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする）。 緩和問題を計算すると、
W = 13-3 = 10 v 9 4 7 1 w 5 4 8 2 3,4番目と、5番目を"1/8個" 詰めるとちょうど一杯になり、価値は 9+4+7/8=13.875 これに、確定済みの1番目を合わせて 21.875
これが緩和問題の解で、現在の部分問題から達成できる価値の上限となる。
この時点でどうやっても今の暫定最大値22を超えられないので、 「3番目を取った場合/取らなかった場合」……などに更に分割しても無駄であり、 現在の部分問題は切り捨ててよいとわかる。
listで持つと、Wの上限が大きい場合とか、Vの上限が大きい場合とかで別の実装が必要となるので、dictで持つと楽（計算はほんの少し遅い？）
緩和問題では $\frac{v}{w}$ 順に連続した品物を選択するので、累積和+二分探索で1個丸ごと取れる品物の境界を得た後、端数を計算する。 重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。
$i$ 番目までのそれぞれ取る/取らないを仮定したケースの上限を考えるとき、ある仮定について合計重さ $w_t$、合計価値 $v_t$ とすると、
ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。 これを超えない最大のindexを二分探索などで $w_{acc}$ から得る。$j$ とする。これが1個丸ごと入れられる品物の境界。
その時の上限価値は、仮定済みの $v_t$ に $v_{i+1}～v_j$ の累積和を合わせたものなので、$v_t + v_{acc}[j] - v_{acc}[i]$、
これに $j+1$ 番目の品物（あれば）の端数分をあわせたものが、上限価値となる。
同じ $i$ の中では $w_t$ が大きい方から処理していくと、$j$ が戻ることは無いので、二分探索の部分は尺取りの方がいいかも。
from bisect import bisect
from collections import defaultdict
from itertools import accumulate
def knapsack(n, W, items):
"""
:param n: number of items
:param W: capacity of knapsack
:param items: list of items (value, weight)
:return:
"""
weights = defaultdict(lambda: 0)
weights[0] = 0
items.sort(key=lambda a: a[0] / a[1], reverse=True)
val_list, wei_list = map(list, zip(*items))
acc_val_list = [0] + list(accumulate(val_list))
acc_wei_list = [0] + list(accumulate(wei_list))
acc_val_list.append(acc_val_list[-1])
best = acc_val_list[bisect(acc_wei_list, W) - 1]
for i, (v, w) in enumerate(items):
search_weight = W + acc_wei_list[i]
ignore_values = acc_val_list[i]
for weight, value in list(weights.items()):
if weight + w > W:
continue
upi = bisect(acc_wei_list, search_weight - weight) - 1
full_best = value + acc_val_list[upi] - ignore_values
if upi < n - 1:
partial_best = val_list[upi] \
* (search_weight - weight - acc_wei_list[upi]) / wei_list[upi]
else:
partial_best = 0
if full_best + partial_best <= best:
weights.pop(weight)
continue
best = max(best, full_best)
weights[weight + w] = max(weights[weight + w], value + v)
return best
ナップサックの実装例では、品物毎に入れる/入れないに分割して、上から順番に探索していた。これは幅優先探索である。
○ 元の問題
入れる/ \入れない
○ ○ 1番目を仮定
/\ /\
○○ ○○ 2番目を仮定
/\/\ /\/\ ...
これは、動的計画法の実装を流用しやすかったためだが、一方でデメリットもある。
というのも、限定操作により切り捨てて良いかを判断するには、とりあえず1つ、基準となる暫定解が必要だが、 このように全ての枝の深さが均等なナップサック問題では、暫定解を得る（＝下まで降りきる）のに時間がかかる。
（実装例では、最後まで探索しなくてもとりあえずちょっと粗めの暫定解をすぐに得られるようにしているが）
部分問題の探索順序は他にもあって、