差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [ナップサック問題] ikatakos | programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [ナップサック問題] ikatakos | ||
|---|---|---|---|
| 行 91: | 行 91: | ||
| 重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。 | 重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。 | ||
| - | $i$ 番目までをそれぞれ取る/ | + | $i$ 番目までをそれぞれ取る/ |
| ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。 | ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。 | ||
