一、用动态规划方法手工求解下面的问题：
某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。
| 时期（月） | 需要量（产品单位） |
|---|---|
| 1 | 2 |
| 2 | 3 |
| 3 | 2 |
| 4 | 4 |
已知：对每个月来讲，生产一批产品的固定成本费为3 (千元)，若不生产，则为零。每生产单位产品的成本费为1 （千元)。同时，在任何一个月内，生产能力所允许的最大生产批量为不超过6 个单位。又知每单位产品的库存费用为每月0.5 （千元），同时要求在第一个月开始之初， 及在第四个月末，均无产品库存。
问：在满足上述条件下，该厂应如何安排各个时期的生产与库存，使所花的总成本费用最低？
要求：写出各种变量、状态转移方程、递推关系式、和详细计算步骤。
该题既可以顺推也可以逆推，但逆推的手工计算量较小。因此这里用逆推的方式求解。
-
变量描述：设\(n\) 为总月份，\(w_i\) 代表第\(i\)个月的需求量，\(u_i\) 代表第\(i\)个月的产量，生产固定成本\(c_1=3\) ，生产单位产品成本费\(c_2=1\) ，单位产品的库存费\(c_3=0.5\) ，单月最大生产量\(max_p=6\)
-
状态转移方程：
记\(s_i\)为第i个月的库存，则\(s_{i+1}=s_i + u_i - w_i\)，且\(s_i \geq 0\)，\(0 \leq u_i \leq max_p\)
\(v_i\)为第i个月的花费，则\(v_i = c_3s_i+\begin{cases}c_2u_i+c_1&,&u_i>0\\0&,&u_i=0\end{cases}\)
设\(f_i(s_i)\)为第i个月后，库存为\(s_i\)的最小成本，则
\[f_i(s_i)=min_{u_i}\{{v_i + f_{i + 1}(s_{i+1})}\} \]最终所求为\(f_1(0)\)
-
递推关系式：
\[\begin{cases} f_n(0)=0\\ f_i(s_j)=min_{u_i}\{v_i+f_{i+1}(s_k)\} \end{cases} \] -
计算步骤：
由题知，所求\(n = 4; w = \{2,3,2,4\}\)，所以有\(u_4=s_5-s_4+w_4=4-s_4\)，即\(0 \leq s_4 \leq 4\)，
\[f_4(s_4)=min_{u_4}\{v_4+f_{5}(0)\}=min_{u_4}\{0.5 * s_4+\begin{cases}1 * u_4+3&,&u_4>0\\0&,&u_4=0\end{cases}\} \implies \begin{cases} f_4(0)=7&,&u_4=4\\ f_4(1)=6.5&,&u_4=3\\ f_4(2)=6&,&u_4=2\\ f_4(3)=5.5&,&u_4=1\\ f_4(4)=2&,&u_4=0\\ \end{cases} \]所以有\(u_3=s_4-s_3+w_3\)，即\(0 \leq s_3 \leq 6\)
\[f_3(s_3)=min_{u_3}\{v_3+f_{4}(s_4)\}=min_{u_3}\{0.5 * s_3+\begin{cases}1 * u_3+3&,&u_3>0\\0&,&u_3=0\end{cases}\} \implies \begin{cases} f_3(0)=11&,&u_3=6\\ f_3(1)=10.5&,&u_3=6\\ f_3(2)=8&,&u_3=0\\ f_3(3)=8&,&u_3=0\\ f_3(4)=8&,&u_3=0\\ f_3(5)=8&,&u_3=0\\ f_3(6)=5&,&u_3=0\\ \end{cases} \]所以有\(u_2=s_3-s_2+w_2\)，即\(0 \leq s_2 \leq 9\)
\[f_2(s_2)=min_{u_2}\{v_2+f_{3}(s_3)\}=min_{u_2}\{0.5 * s_2+\begin{cases}1 * u_2+3&,&u_2>0\\0&,&u_2=0\end{cases}\} \implies \begin{cases} f_2(0)=16&,&u_2=5\\ f_2(1)=15.5&,&u_2=4\\ f_2(2)=15&,&u_2=3\\ f_2(3)=12.5&,&u_2=0\\ f_2(4)=12.5&,&u_2=0\\ f_2(5)=10.5&,&u_2=0\\ f_2(6)=11&,&u_2=0\\ f_2(7)=11.5&,&u_2=0\\ f_2(8)=12&,&u_2=0\\ f_2(9)=9.5&,&u_2=0\\ \end{cases} \]而\(s_1 = 0\)，\(u_1=s_2 - s_1 + w_1\)，
\[f_1(s_1)=min_{u_1}\{v_1+f_{2}(s_2)\}=min_{u_1}\{0.5s_1+\begin{cases}1 * u_1+3&,&u_1>0\\0&,&u_1=0\end{cases}\} \implies f_1(0)=20.5,u_1=5 \]故\(u=[5,0,6,0]\)，\(s = [0,3,0,4]\)，即4个月分别生产5、0、6、0单位产品，各月库存量分别为0、3、0、4，总成本最低为\(f_1(0)=20.5\)
二、用动态规划方法编程求解下面的问题：
某推销员要从城市\(v_1\) 出发，访问其它城市\(v_2，v_3，…，v_6\) 各一次且仅一次，最后返回\(v_1\)。D为各城市间的距离矩阵。
\[D= \begin{matrix} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \\ v_6 \end{matrix} \begin{bmatrix} 0 & 10 & 20 & 30 & 40 & 50\\ 12 & 0 & 18 & 30 & 25 & 21\\ 23 & 19 & 0 & 5 & 10 & 15 \\ 34 & 32 & 4 & 0 & 8 & 16 \\ 45 & 27 & 11 & 10 & 0 & 18 \\ 56 & 22 & 16 & 20 & 12 & 0 \end{bmatrix} \]问：该推销员应如何选择路线，才能使总的行程最短？
要求：写出递推关系式、伪代码和程序相关说明，并分析时间复杂性。 （请遵守第一节课提出的有关 assignment 的要求）
-
变量描述：记城市数量\(n=6\)，城市编号为\(0,1,2,\dots,n-1\)，距离矩阵为\(D\)；
-
状态转移方程：设\(f_{i,S}\)代表推销员走到第i个城市，已经访问过的城市集合为S，则
\[f_{i,S}=min\{f_{j,S-\{i\}}+D_{j,i}\} \] -
递推关系式：初始时S为空，\(f_{i,S}=0\)
\[\begin{cases} f_{i,S}=0\\ f_{i,S}=min\{f_{j,S-\{i\}}+D_{j,i}\} \end{cases} \] -
伪代码：
func TSP(n, D){ // Input: n城市数量，D为距离矩阵下标从0开始 // Output: 一个数，代表从v1=0出发，最后回到v1的最小距离 初始化f为INF 将v1添加进集合S，此时f[i][S]=0 从{v1}开始枚举集合S的状态 枚举第i个城市是否在集合内，如果在 枚举不在集合内的第j个城市 将j加入集合S记为S‘,此时花费为f[i][S] + D[i][j] 记f[j][S']=min{f[j][S'], f[i][S] + D[i][j]} 则得到f[i][S]为从0出发，最后集合状态为S的最小 最后加上从最后经过的城市返回v1的距离，输出答案 } -
时间复杂度：\(O(n^2*2^n)\)
-
附程序代码：
#include<iostream> #include<cstring> using namespace std; #define INF 0x3f3f3f3f const int n = 6; const int D[6][6]={ {0,10,20,30,40,50}, {12,0,18,30,25,21}, {23,19,0,5,10,15}, {34,32,4,0,8,16}, {45,27,11,10,0,18}, {56,22,16,20,12,0} }; int f[10][1024]; int main() { memset(f, INF, sizeof(f)); f[0][1] = 0; int tot = (1 << n) - 1; for (int s = 1; s <= tot; s++) { for (int i = 0; i < n; i++) { if ((s >> i & 1 == 0) || (f[i][s] == INF)) continue; for (int j = 0; j < n; j++) if ((s >> j & 1) == 0) f[j][s | 1 << j] = min(f[j][s | 1 << j], f[i][s] + D[i][j]); } } int ans = INF; for (int i = 0; i < n; i++) if (f[i][tot] < INF) ans = min(ans, f[i][tot] + D[i][0]); cout << ans << endl; }