動態規劃算法的侷限性

Question

在研究了這個question之後，我開始意識到動態規劃算法不能用於解決knapsack problem或與非整數約束的類似的問題。我對我的認識是否正確？動態編程算法還有其他限制嗎？

Answer 1

基本上你可以說可能的分數（溶液質量）的需求數量是有限的，並足夠低，以適應在內存中。非整數通常意指非離散和通向無限可能的解決方案的分數。

如果有，你知道，你會在最需要找到他們的N到也得到了最好的一個，沒有辦法得到他們整個指數僅量N個可能的解決方案的分數。這是動態編程背後的想法。

Answer 2

我想另一個限制是，它是不是如果動態規劃是最好的技術，因爲它的性能是不知道匹配理論信息下界聞名。

這裏是an example problem from David Eppstein：

給定n個實數的排序列表，發現1和n之間的最小間隔 正好含有k個元素，對於k的所有的值。 有一個簡單的動態規劃算法，可以在二次時間內解決這個問題，但最知名的下限只有 線性。無論是描述一個更快的算法，或者證明在計算一些合理的模型更大的低 約束。 （「動態規劃」 不是comptuation的一個合理的模型！）