No.626

分枝限定法を使う.

まずは $w_i \gt w$ となる荷物は使えないので取り除く.

残りは $v_i/w_i$ が大きいものを入れていくのが効率が良さそうなので, $v_i/w_i$ の降順でソートしておく.

最初の荷物から順に入れる/入れないを判別していく.

関数 $f(S, T)$ を考える. $S$ は入れる/入れないを仮定済みの荷物の状態, $T$ を未仮定の荷物の状態とする.

このときの $f$ の上界と下界を求める.

上界は線形緩和で求める. 線形緩和すれば貪欲法で求められるので, 計算量は $O(n)$ である.

下界は貪欲法で求める.

暫定解をそれまでに求めた最良の解とすれば, 上界が暫定解より小さければ $T$ はこれ以上仮定しても無駄なので計算を打ち切る.

下界が暫定解より大きければ暫定解を下界で更新し, さらに仮定を進めて再帰する.