江苏龙网

  1. 首页 > 生活 > >

动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢

比方说整数值的背包问题，表示状态的物品index-总容量对上有一个典范的良序（就是你枚举状态的顺序了）。假设这个算法在某个input下不对，取出最小的状态坐标，使得求解出的这个子问题答案错误。根据假设它的前继子问题都是求解正确的，带入bellman方程，它也应该被算对，矛盾。稍微一般一点的情况就是在状态的DAG上做归纳但是题主想问的应该不是这个问题，而是“怎么确认一种子问题划分和相应的状态转移方程是正确的”，这个问题就太meta了可能不太好回答。。在你设计出一个dp算法之前往往会考虑一些朴素的暴力方法，枚举原问题“完整的action序列”，优化目标是这个action序列上的可能比较复杂的某个函数。这个objective往往写成有限步的计算，所有的中间结果都是有序域\\mathbb{R}上的元素。有的时候你会发现action序列的某些部分在计算的某一部开始不再被用到了，被用到的只是这些action在之前参与的某（几）个中间计算结果。由于\\mathbb{R}上常见的操作在每个位置上都有良好的单调性，很可能能找到一组中间结果，使得我们能够枚举这种中间结果来完成原问题的优化
■网友

如何理解动态规划？基本上你可以理解为，在暴力搜索的基础上减掉了一些重复计算，从而加快速度，正确性和暴力搜索的结果是一样的，而后者由于枚举了所有可能情况，所以必然是得到最优结果的

■网友
先回顾下动态规划问题的求解过程：
（1）证明该问题具有最优子结构性质(局部最优解能决定全局最优解)；
（2）根据最优子结构，求递推方程；
（3）根据递推方程，说明该问题具有重叠子结构性质；
（4）自底向上写出求解最优值的非递归算法，同时构造最优解的解空间树；
（5）遍历解空间树，求得最优解。

贪心算法是求一个子问题的解，假设这个解是子问题的最优解，在此基础上再进一步推导更大问题的最优解。
这意味着，“贪心算法最后求出解是最优的”是基于“子问题的解的确是最优的”并且“全局最优 动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢
该局部最优解”。如果这一点不成立，那贪心最后的结果也并不可靠。

再回过头来看动态规划，由于在求解时，第一步就要求要证明最优子结构，所以保证了“全局最优 动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢
该局部最优解”。

综上，回答题主问题，是通过证明最优子结构来证明的。感觉题主有这个问题是因为很多时候大家都是说感觉这个可以dp解，然后就dp了，如果不是有必要，大家不会很严肃的推导，或者在推导递推方程的时候，很自然就承认了的确存在最优子结构这件事。

最后，随便找了个背包问题的最优子结构证明。

■网友
注意动态规划的思想核心 如果能使用动态规划解决 那么一般是将问题分解为子问题 解决子问题使用的肯定是最优策略 当所有子问题最优时可以类似递推模式 得到全局最优解
■网友
dp是遍历了一遍所有的可能路线，因此是最优解。这点是它优于贪心的地方。

so，这问题。。
【动态规划能得到一类问题的最优解，比如背包问题用动态规划来解决，怎样证明这个解就是相对应问题的最优解呢】 还是需要学习一个


    推荐阅读


    上一篇：为啥播放器及媒体相关类UI都采用深色系(黑色or灰色)，浅色系为啥不适合用于媒体类的UI

    下一篇：作为一个打码的，有没有一段时间特不想打码，后来是咋熬过来的