动态规划第七章

本章共五个问题：

• 最短路问题
• 资源分配问题
• 背包问题
• 多阶段生产问题
• 生产与库存问题

个人认为，动态规划的特点在于多阶段性，分步骤解决，上一阶段的问题解决后，上一阶段即为最优。

最短路问题

例题

特点

十分若置：
同阶段的节点之间，彼此无联系
不存在跨阶段节点

思路

按照步骤算，第i步找到所有i步能够到达的节点，算出他们的最短路径，作为该节点的价值
从后往前推，从前往后推，都可以

资源分配问题

例题

思路

$x_i$ 分配给第$i$个工厂的资金数(万元)
$g_i(x_i)$ 第$i$个工厂得到数量为$x_i$(万元)的资金后的利润值(万元)【已知】
$f_k(x)$ 以数量为x(万元)的资金分配给前k个工厂所得到的最大总利润值。
然后按顺序分别求出仅1、2、3、4个工厂时，怎么分配$x_i$能达到最佳。，即求$f_4(60)$【这个时候，所有$k\le 4x\le 60$都能求出】
f k ( x ) = max ⁡ y = 0 , 1 , 2 , ⋯ x { g k ( y ) + f k − 1 ( x − y ) } f_{k}(x)=\max _{y=0,1,2, \cdots x}\left\{g_{k}(y)+f_{k-1}(x-y)\right\} fk​(x)=y=0,1,2,⋯xmax​{gk​(y)+fk−1​(x−y)}

具体步骤

step 1

step 2

逐个计算$f_2(0)\sim f_2(60)$

同理，算出剩下的阶段

step 3

最后一个阶段，只用算$f_k(x_{m}ax)$即可。

背包问题

例题【二维】

思路

$f_k(W,V)$ 总重量不超过$W$公斤,总体积不超过$V$，背包中只装前$k$种物品时的最大使用价值。
$x_i$ 第$i$件物品取几个【经典背包限制了$x_i\le 1$】
只分析前$k$个物品，此时前$k-1$个物品在所有重量$w\le W$和体积$v\le V$下的最优解均为已知。
第$k$个物品只需要判断：取或不取【有的题目需要判断取不取，取几个，其实同理】

具体步骤

一维可参考

from
一维背包问题求解

多阶段规划问题

例题

思路

应当明确：原料总数不影响方案分配比
无论多少个生产方式，某个阶段都是梭哈某方式的决策为最优
按照从后往前的方法，先求出最后一步的最优策略，并列出该步骤最优策略的函数表达式$f_k(x)$。

生产与库存

例题

思路

$u_k$ $k$阶段产量
$f_k(x_k)$ 阶段$k$的初始库存量为$x_k$时，阶段$k$到计划期末的最小费用。
约束条件：

动态规划基本方程：

倒序枚举，求出每个阶段的每个$x_i$需要的最小费用【每个阶段的每个$x_i$内也可能有多个$u_k$供选择】