部分問題から、制約条件を緩めて最適解の上限を簡単に計算できるようにしたもの緩和問題の最適解は、必ず元の問題の最適解より大きい緩和問題から得られる上限見積もりが、現在の暫定ベストより悪ければ、そこで打ち切る(※「上限」「大きい」というのは最大化問題の場合で、最小化問題なら「下限」「小さい」となる)近い概念に動的計画法があるが、動的計画法は、分枝操作が可能で同じ部分問題を何回も要求される問題に対して、記録して同じ問題を解かないようにする。分枝限定法は、同じ部分問題が要求されるかは重要ではなく、最適解が得られないことがわかった問題を切り捨てて調べる空間を減らす、というような理解。部分問題に分割できること緩和問題が高速に解けること緩和問題は適切な唯一の方法があるわけでは無い。前提が誤っている(緩和問題の解より実際の解が大きくなるなど)でない限り、正しい解は求まる。実際の解に近い上限を推定できる緩和問題を採用すれば、より効率的に無駄な探索空間を除外できる。緩和問題は部分問題毎に毎回計算するので、これに時間がかかるようでは本末転倒。削減できる探索空間とのトレードオフとなる。緩和問題もし品物が1個単位でなく、「3/5個入れる」ようなことができる場合、解くのは簡単である。高い方から順に、貪欲に詰めていけばよい。3/4)=25そして、1個単位でしか詰められない元の問題は、この解より大きくなることは無い。(どれかを諦めなければならず、空いたスペースに代わりの品物を入れられるとしてもそれは重さあたりの価値効率がより低いため)つまり上限となる。限定操作ここで、元の問題の探索に戻る。高い方から取る/取らない場合に分割して探索していく。1~3番目を取って4~6番目を取らなかった時に、価値が22となるという結果が得られたとする。これを暫定最大値とする。ここで、1番目を取り2番目を取らなかった場合の、3~6番目からなる部分問題を考える(いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする)。21.875これが緩和問題の解で、現在の部分問題から達成できる価値の上限となる。順に連続した品物を選択するので、累積和+二分探索で1個丸ごと取れる品物の境界を得た後、端数を計算する。