动态规划

无论过程的初始状态和初始决策是什么，其他决策都必须相对于初始决策所产生的状态构成一个最优决策序列。

一般不可能在每一阶段直接选出最优决策序列中属于此阶段的决策值，可以从最后阶段开始，逐步向前递推方式求解前一阶段决策值的递推关系。 根据x_i+1..x_n的那些决策序列求取xi的决策值的关系式——动态规划的向前处理法。

列出关系式后，由最后阶段开始回溯求解这些关系式，得最优决策序列。

例 0/1背包问题 g(x)为KNAP（j+1,n,x）最优解

g(x)= max{ g_j+1(x),  g_j+1(x-w_j+1)+P_j+1} . 先将  n>=0时，g_n(x)=0;n<0时，g_n(x)=负无穷大 

由前向后递推的方式求解所得列出的关系式，得出最优决策序列——向后处理法

例0/1背包问题 f(x)为KNAP(1,i,x) 最优解

f(x)=max{ f_j-1(x),  f_j-1(x-w_i)+pi }      先将 x>=0,f₀(x)=0;  x<0, f₀(x)=负无穷大 

例1： 多段图，资源分配 图

例2：每对结点之间的最短路径

动态规划

原文：http://www.cnblogs.com/dan-cnblogs/p/4733837.html