【算法设计与分析】实验二动态规划 - TSP问题和0-1背包问题一、实验目的与要求1. 实验目的理解并掌握动态规划的基本原理能将其应用于解决实际问题。2. 实验要求了解TSP问题和0-1背包问题的基本概念和实际应用。掌握动态规划的基本原理能灵活运用在这两个问题中。能编写出正确实现动态规划解决这两个问题的代码。分析程序的运行结果并从动态规划的角度解释。二、实验内容了解TSP问题和0-1背包问题的含义应用动态规划解决这两个问题并能编写出实现该算法的编程代码。三、实验方法学习并深入理解TSP问题和0-1背包问题的基本概念和应用背景。学习并理解动态规划的基本理论掌握如何利用动态规划来求解这两个问题。按照动态规划的理论用编程语言C或C编写实现动态规划解决这两个问题的代码。运行程序记录程序的运行结果并反思是否每一步的前提条件都得到了满足。四、详细的算法设计及运行结果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)个情况。比如n4时有7种情况我们可以利用7的二进制0111来表示集合{a1, a2, a3}以此类推。这里以{1{23}}为例向下分解可以得到dp数组实验源码#includebits/stdc.husingnamespacestd;#defineN4#defineINF10e7staticconstintM1(N-1);intg[N][N]{{INF,3,6,7},{5,INF,2,3},{6,4,INF,2},{3,7,5,INF}};intdp[N][M];vectorintpath;// 用动态数组表示voidTSP(){for(inti0;iN;i){dp[i][0]g[i][0];}for(intj1;jM;j){for(inti0;iN;i){dp[i][j]INF;// 初始化if(((j(i-1))1)1){continue;}for(intk1;kN;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. 算法的特色采用状态压缩动态规划求解旅行商问题通过二进制位表示城市访问状态满足问题最优子结构特性相对于蛮力法求解更高效。使用位运算实现状态判断与转移执行效率高利用动态规划思想时间复杂度为O(N² × 2ⁿ)相对于蛮力法求解所有子集求解的方法O(n!)大大降低。3. 0-1背包问题算法设计及结果根据动态规划解题步骤问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成找出0-1背包问题的最优解以及解组成然后编写代码实现。建立模型即求max(V₁X₁ V₂X₂ … VₙXₙ)寻找约束条件W₁X₁ W₂X₂ … WₙXₙ C寻找递推关系式面对当前商品有两种可能性背包的容量比该商品体积小装不下此时的价值与前i-1个的价值是一样的即V(i,j) V(i-1,j)还有足够的容量可以装该商品但装了也不一定达到当前最优价值所以在装与不装之间选择最优的一个即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)}得到状态转移方程后就可以开始求解了下面是动态规划表一行一行的填表。实验源代码#includebits/stdc.husingnamespacestd;constintN5;constintM10;intdp[N1][M1];intgood[N][2]{{2,6},{2,3},{6,5},{5,4},{4,6}};intmain(){for(inti1;iN;i){intwgood[i-1][0];intvgood[i-1][1];for(intj0;jM;j){if(jw)dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v);elsedp[i][j]dp[i-1][j];}}for(inti1;iN;i){for(intj0;jM;j){printf(%-4d,dp[i][j]);}cout\n;}return0;}4. 算法的特色采用二维数组动态规划实现01背包状态方程较清晰、代码简洁易懂可以快速修改物品数和背包容量。利用动态规划法求解0-1背包问题时间复杂度为O(N×M)而蛮力法求解需要求问题所有的解时间复杂度为O(2ⁿ)。五、实验感想0-1背包问题具有最优子结构性质所以可以用动态规划方法求解。根据这种性质定义递归关系并建立递归方程以自底向上的方式计算最优值。而且以后编程时要彻底理解问题后再构造算法。