私は、動的プログラミングと分岐とバインドを含むナップザックの最適化問題を行っています。問題の容量と項目が大きくなると、動的計画法アルゴリズムの 2D テーブルを埋めるのが指数関数的に遅くなることに気付きました。ある時点で、問題のサイズに応じてアルゴリズムを切り替えると仮定します (講義では 2 種類の最適化が行われたため)。
動的プログラミングからブランチ&バウンドに切り替えるべきポイント(サイズ)をググってみましたが、思うような結果が得られませんでした。
または、問題のサイズに応じてアルゴリズムを切り替えるのではなく、動的計画法と分岐限定を 1 つのアルゴリズムとして組み合わせることができるナップザック問題の別の見方はありますか?
ありがとう。