何時從動態編程（二維表格）切換到分支定界算法？

Question

我正在做一個涉及動態規劃和分支&約束的揹包優化問題。我注意到當問題的容量和項目變大時，爲動態編程算法填充2D表格將呈指數級變慢。在某些時候，我會假設我想根據問題的大小切換算法（因爲講座提供了兩種類型的優化）？

我試過在什麼點（什麼大小）谷歌應該從動態編程切換到分支&約束，但我不能得到我想要的結果。

或者，有沒有另一種方法來看待揹包問題，我可以將動態編程和分支綁定爲一個算法，而不是切換算法，這取決於問題的大小？

謝謝。

Answer 1

通常，當您有幾種解決問題但其運行時間具有不同特性的算法時，您可以確定（在經驗上而不是理論上）何時一個算法變得比另一個更快。這是高度實現和機器相關的。因此，測量DP算法和B算法，並找出哪一個更好。

一對夫婦的提示：

• 你知道DP的運行時間是成正比的對象倍揹包的大小數量。
• 你知道B的運行時間可能和2 ^＃對象一樣差，但它通常要好很多。試圖找出最壞的情況。
• 緩存和內容對DP來說很重要，所以你需要估計它的運行時間分段。找出斷點的位置。
• DP佔用過多的內存。如果它將佔用太多，您在DP和B之間確實沒有選擇& B.