差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [ナップサック問題] ikatakos | programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [ナップサック問題] ikatakos | ||
|---|---|---|---|
| 行 67: | 行 67: | ||
| 1～3番目を取って4～6番目を取らなかった時に、価値が22となるという暫定解が得られたとする。これを暫定最大値とする。 | 1～3番目を取って4～6番目を取らなかった時に、価値が22となるという暫定解が得られたとする。これを暫定最大値とする。 | ||
| - | ではここで、1番目を取り、2番目を取らなかった部分問題を考える。（いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする） | + | ではここで、1番目を取り2番目を取らなかった場合の、3～6番目からなる部分問題を考える（いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする）。 |
| 上限を計算すると、 | 上限を計算すると、 | ||
| 行 92: | 行 91: | ||
| 重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。 | 重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。 | ||
| - | $i$ 番目までをそれぞれ取る/ | + | $i$ 番目までをそれぞれ取る/ |
| ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。 | ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。 | ||
