Algorithm assignment 1

2020-12-10

一、用动态规划方法手工求解下面的问题：

某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。

已知：对每个月来讲，生产一批产品的固定成本费为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为各城市间的距离矩阵。

问：该推销员应如何选择路线，才能使总的行程最短？

要求：写出递推关系式、伪代码和程序相关说明，并分析时间复杂性。 （请遵守第一节课提出的有关 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; 
  }