动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构（英语：Optimal substructure）性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。背包问题作为NP完全问题，暂时不存在多项式时间算法。动态规划属于背包问题求解最优解的可行方法之一。此外，求解背包问题最优解还有搜索法等，近似解还有贪心法等，分数背包问题有最优贪心解等。 背包问题具有最优子结构和重叠子问题。动态规划一般用于求解背包问题中的整数背包问题（即每种物品所选的个数必须是整数）。 解整数背包问题： 设有 n {displaystyle n} 件物品，每件价值记为 P i {displaystyle P_{i}} ，每件体积记为 V i {displaystyle V_{i}} ，用一个最大容积为 V max {displaystyle V_{text{max}}} 的背包，求装入物品的最大价值。 用一个数组 f [ i , v ] {displaystyle f} 表示取 i {displaystyle i} 件商品填充一个容积为v的背包的最大价值，显然问题的解就是 f [ n , V max ] {displaystyle f} 。f [ i , v ] = { f [ i − 1 , v ] , v < V i max { f [ i − 1 , v ] , f [ i − 1 , v − V i ] + P i } , v ≥ V i 0 , i v = 0 {displaystyle f={begin{cases}f,v<V_{i}\max{f,f+P_{i}},vgeq V_{i}\0,iv=0\end{cases}}}对于特例01背包问题（即每件物品最多放1件，否则不放入）的问题，状态转移方程：f [ i , v ] = { f [ i − 1 , v ] , v < V i max { f [ i − 1 , v ] , f [ i − 1 , v − V i ] + P i } , v ≥ V i 0 , i v = 0 {displaystyle f={begin{cases}f,v<V_{i}\max{f,f+P_{i}},vgeq V_{i}\0,iv=0\end{cases}}}参考Pascal代码参考C++代码（不含include和数组声明）