Ｄynamic Ｐrogramming

动态规划在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

1、动态规划的基本思想：动态规划是和过程最优化概念紧密联系的.在过程进行中,在客观条件允许范围内选择最好的措施控制过程的发展,以期最好的完成任务. 动态规划用于多阶段的决策过程,每个阶段都有可供选择的多种决策,各个阶段的决策构成一个决策序列.动态规划的目标是选取一个最优的决策序列

2、解题步骤：动态规划法设计步骤
① 找出最优解的性质,并刻画其结构 (最优子结 构) 特征.
② 递归地定义最优值, 导出递推公式.
③ 以自底向上的方式计算最优值.
④ 根据计算最优值时得到的信息,构造最优解.
形式：如：
1 )问题的解: 边的序列, 每一步决策选择一条边 
      { <A C>,<C F>,<F I>,<I J> ,<J L> }
2) 约束条件: 两个顶点之间有边存在
3) 可行解: 满足约束条件的解
4) 目标函数: 解中边的权值和达到最小 
5) 最优解:  使目标函数取极值的可行解

【1、投资分配问题】：总资源数为a，工程个数为n。给每个工程投资不同，所获得的利润也不同。现给定各个工程的资源利润表和资源总数，问:如何分配资源，才能获得最大利润。

记Fn(a)为给n个工程投资资源数为a时可获得的最大利润,则有： 
Fn(a)=max{G1(x1)+G2(x2)+…Gn(xn)}
              x1+x2+…xn=a
如果给第n项工程投资x，给前n-1项工程投资a-x，则
Fn(a)=max {Fn-1(a-x)+ Gn(x)}
              X∈(0,1,…,a)
记  Fk(z)为给k个工程投资总资源数为z时可以获得的最大利润，则有递推公式：
        Fk(z)= max {Fk-1(z-x)+ Gk(x)}   Z∈(0,1,…,a)
               X∈(0,1,…,z)
          F1(z)= G1(z)
利用这一递推公式，我们可以得出该问题的算法。
投资问题算法
Investing( m,n,g[i][j])
{  for(j=0; j<=m; j=j+1) {f[1][j]=g[1][j] ;  d[1][j]=j}
   for (i=2; i<=n; i=i+1) 
     for(j=0; j<=m; j=j+1)
          {  f[i][j]=0 ; 
                for( k=0; k<=j; k=k+1)
                   {  s=f[i-1][j-k]+g[i][k]
                       if(s>f[i][j])   {  f[i][j]=s;  d[i][j]=k }
                   }
           }
    构造最优解
}  
   m 总投资数额。n 工程总项数。
   g[I][J] 存放资源利润表，I为工程号，J为投资数额
构造最优解
{  s=m
   x[n]=d[n][m]
   for (k=n-1; k>0; k=k-1)
     {   s=s-x[k+1] ; x[k]=d[k][s]; }
    for(k=1; k<=n; k=k+1)  output x[k] 
    output f[n][m]
}
d[I][J] 给前I项工程投资额为J,获最大利润时第I项的投资额