algorithm - 动态规划算法的局限性

Question

在探索这个 question 之后我开始意识到动态规划算法不能用来解决knapsack problem或具有非整数约束 的类似问题。我对我的认识是否正确？动态规划算法还有其他限制吗？

Answer 1

基本上，您可以说可能得分的数量(解决方案质量)需要是有限的并且足够低以适合内存。非整数通常意味着非离散，这会导致无限可能的解决方案得分。

如果只有 N 个可能的解决方案分数，您知道您最多需要找到 N 个分数才能得到最好的分数，而不是找到它们的整个指数数量的方法。这就是动态规划背后的思想。