分枝限定法を使う.

荷物は \(v_i/w_i\) の降順でソートしておく.

\(i\) 番目の荷物まで見たときに価値が \(v\), 重さが \(w\) だったとする.

ここから貪欲法で詰められるだけ詰めたときの価値が最低限取得できる価値となる. これを暫定解と比べて暫定解を更新する.

また, さらに荷物は分割できるものとして貪欲法で詰めたときの価値が最高で取得できる価値となる. これが暫定解より小さければそれ以上調べる必要はないので枝刈りする.