差分
このページの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番目からなる部分問題を考える（いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする）。 |
| 上限を計算すると、 | 上限を計算すると、 | ||
