【算法设计与分析】实验二：动态规划 - TSP问题和0-1背包问题

一、实验目的与要求

1. 实验目的

理解并掌握动态规划的基本原理，能将其应用于解决实际问题。

2. 实验要求

1. 了解TSP问题和0-1背包问题的基本概念和实际应用。
2. 掌握动态规划的基本原理，能灵活运用在这两个问题中。
3. 能编写出正确实现动态规划解决这两个问题的代码。
4. 分析程序的运行结果，并从动态规划的角度解释。

二、实验内容

了解TSP问题和0-1背包问题的含义，应用动态规划解决这两个问题，并能编写出实现该算法的编程代码。

三、实验方法

1. 学习并深入理解TSP问题和0-1背包问题的基本概念和应用背景。
2. 学习并理解动态规划的基本理论，掌握如何利用动态规划来求解这两个问题。
3. 按照动态规划的理论，用编程语言（C或C++）编写实现动态规划解决这两个问题的代码。
4. 运行程序，记录程序的运行结果，并反思是否每一步的前提条件都得到了满足。

四、详细的算法设计及运行结果

1. TSP问题算法设计及结果

动态规划方程推导

① 当V为空集，那么表示直接从i回到s了，此时dp[i][∅] = dist(i, s)；

② 如果V不为空，那么就是对子问题的最优求解。必须在V这个城市集合中，尝试每一个，并求出最优解。

综上所述，TSP问题的动态规划方程就出来了：

dp[i][S]=min⁡k∈S{g[i][k]+dp[k][S∖{k}]}dp[i][S] = \min_{k \in S} \{ g[i][k] + dp[k][S \setminus \{k\}] \}dp[i][S]=k∈Smin​{g[i][k]+dp[k][S∖{k}]}

状态压缩思想

用代码实现，通过判断元素是否在集合中，可以用二进制表示。同样通过规律发现，当有n个城市时，共有2^(n-1)个情况。比如n=4时，有7种情况，我们可以利用7的二进制0111来表示集合{a1, a2, a3}，以此类推。

这里以{1，{2，3}}为例向下分解

可以得到dp数组

实验源码

#include<bits/stdc++.h>usingnamespacestd;#defineN4#defineINF10e7staticconstintM=1<<(N-1);intg[N][N]={{INF,3,6,7},{5,INF,2,3},{6,4,INF,2},{3,7,5,INF}};intdp[N][M];vector<int>path;// 用动态数组表示voidTSP(){for(inti=0;i<N;i++){dp[i][0]=g[i][0];}for(intj=1;j<M;j++){for(inti=0;i<N;i++){dp[i][j]=INF;// 初始化if(((j>>(i-1))&1)==1){continue;}for(intk=1;k<N;k++){if(((j>>(k-1))&1)==0){continue;// 如果在集合里边直接跳过}if(dp[i][j]>g[i][k]+dp[k][j^(1<<(k-1))]){dp[i][j]=g[i][k]+dp[k][j^(1<<(k-1))];}}}}}intmain(){TSP();cout<<"最小值为："<<dp[0][M-1]<<endl;return0;}

TSP求解过程

以{1, {2, 3}}为例向下分解：

dp[0][{1,2,3}] ├── g[0][1] + dp[1][{2,3}] ├── g[0][2] + dp[2][{1,3}] └── g[0][3] + dp[3][{1,2}]

由底向上求解问题，得到dp表。

2. 算法的特色

1. 采用状态压缩动态规划求解旅行商问题，通过二进制位表示城市访问状态，满足问题最优子结构特性，相对于蛮力法求解更高效。

2. 使用位运算实现状态判断与转移，执行效率高，利用动态规划思想，时间复杂度为O(N² × 2ⁿ)，相对于蛮力法求解所有子集求解的方法O(n!)大大降低。

3. 0-1背包问题算法设计及结果

根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出0-1背包问题的最优解以及解组成，然后编写代码实现。

建立模型

即求max(V₁X₁ + V₂X₂ + … + VₙXₙ)

寻找约束条件

W₁X₁ + W₂X₂ + … + WₙXₙ < C

寻找递推关系式

面对当前商品有两种可能性：

1. 背包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j) = V(i-1,j)；

2. 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j) = max{V(i-1,j), V(i-1,j-w(i)) + v(i)}。

其中V(i-1,j)表示不装，V(i-1,j-w(i)) + v(i)表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)。

由此可以得出递推关系式：

j < w(i) V(i,j) = V(i-1,j) j >= w(i) V(i,j) = max{V(i-1,j), V(i-1,j-w(i)) + v(i)}

得到状态转移方程后就可以开始求解了，下面是动态规划表，一行一行的填表。

实验源代码

#include<bits/stdc++.h>usingnamespacestd;constintN=5;constintM=10;intdp[N+1][M+1];intgood[N][2]={{2,6},{2,3},{6,5},{5,4},{4,6}};intmain(){for(inti=1;i<=N;i++){intw=good[i-1][0];intv=good[i-1][1];for(intj=0;j<=M;j++){if(j>=w)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);elsedp[i][j]=dp[i-1][j];}}for(inti=1;i<=N;i++){for(intj=0;j<=M;j++){printf("%-4d",dp[i][j]);}cout<<'\n';}return0;}

4. 算法的特色

1. 采用二维数组动态规划实现01背包，状态方程较清晰、代码简洁易懂，可以快速修改物品数和背包容量。

2. 利用动态规划法求解0-1背包问题时间复杂度为O(N×M)，而蛮力法求解需要求问题所有的解，时间复杂度为O(2ⁿ)。

五、实验感想

0-1背包问题具有最优子结构性质，所以可以用动态规划方法求解。根据这种性质定义递归关系并建立递归方程，以自底向上的方式计算最优值。而且以后编程时要彻底理解问题后再构造算法。