【算法设计与分析】动态规划解决石子合并问题 摘要
动态规划算法是计算机算法设计中的一个重要算法，通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决，石子合并问题作为典型算例，能够彰显动态规划算法特征
针对石子合并问题，本文利用动态规划算法寻求石子合并时的最大,最小得分，选择相邻的两堆石子堆进行合并，其最终花费的代价与石子堆的排列顺序有关 。根据其重叠子问题建立状态转移方程，利用程序进行求解 。算例结果显示：将4堆石子合并成一堆，每堆的石子个数分别是4,4,5,9，合并的代价最小得分为43，最大得分为54
1、问题描述
在一个圆形操场的四周摆放着N堆石子，每堆石子有一定的数量 。现要将N堆石子并成为一堆 。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆 。计算出将n堆石子合并成一堆的代价最大得分和最小得分 。
2、问题分析
首先分析本题 。题目输入的数据是石子堆的个数n，以及每堆石子堆的数量ai 。合并的过程中，只能选择相邻的两堆石子堆进行合并 。所以最终花费的代价，与石子堆的排列顺序也有关 。
【课程设计【算法设计与分析】动态规划解决石子合并问题】此问题具有重叠子结构 。首先肯定是两两相邻的石子堆进行合并 。最初我们不知道要从哪里开始合并，则遍历所有的石子堆，进行两两合并 。比如序列 {1,2,3,4} ，1号和2号合并：sum[1][2]=3，2号和3号合并：sum[2][3]=5 ，3号和4号合并：sum[3][4]=7 ，这里我们用 sum[i][j] 表示当前合并步骤从 i 合并到 j 花费的代价，用 dp[i][j] 表示从 i 和并到 j 的累计代价，第1步的累计代价等于当前步骤的代价 。
文章插图
接下来再进行3个长度的合并，则只有2种合并方案：1号、2号、3号合并或者是2号、3号、4号合并 。在1号、2号、3号合并的过程中，则又有两种方案：{{1,2},3} 还是 {1,{2,3}} 。对于前者，当前步骤花费代价 sum[1][3] = sum[1][2] + sum[3][3] = 3+3 = 6 ，加上第一步已经花费的代价 sum[1][2]=3 ，总代价为 dp[1][3] = sum[1][2] + sum[1][3] = 9 ；对于后者，花费代价 sum[1][3] = sum[1][1] + sum[2][3] = 1+5 = 6 ，加上第一步已经花费的代价 sum[2][3]=5 ，总代价为 dp[1][3] = sum[1][3] + sum[2][3] = 9。所以第二轮的最少代价应该在第一种方案中 。
通过上面这个简单的示例，可以归纳总结出，实际的从 i 到 j 的最小合并代价，应该是选择：从已有的 i 到 j 的最小合并代价，与从 i 到 k 的最小代价、从 k+1 到 j 的最小代价、当前步骤从 i 到 j 的合并代价的和的最小值 。
即状态转移方程为：
3.算法设计
通过状态转移方程我们可以看出dp[ i ][ t ]表示从 第i堆开始之后合并t堆石子(包括第i堆石子)合并花费，k是i~t之间的一个数，因为是环形,所以要将一维数组收尾相连,所以计算第i+k堆应该表示成: (i+k-1)%n+1,这里不能想当然的以为-1%n可以和外面的1约掉就变成(k+1)%n， 这里是因为数组的下标是从1开始的，前者可以保证不去到0，用sum表示最后两队合并时候的花费，sum一定等于所有石子的个数 。
4.程序代码
文章插图
#include#include#define Ma_x 99999#define Mi_x 0 #define min(a,b) ab?a:b int n,w[200],dp[200][200],dq[200][200];//n表示堆数，w表示每队的数量，dp[i][j]表示从第i堆开始合并j堆（包括第i堆）后的最小花费 ,dq表示最大 int sum(int i,int t){//从第i堆开始,t个石堆合，最后一次的合并的花费 int k,s=0,k1;for(k=i;k
- 柑橘苗移栽后管理技术
- 微生物实验室设备清单 微生物实验室设计要求
- 附源码 spring boot网络空间安全实验教学示范中心网站 毕业设计 1
- 手机镜头的设计
- s31254是什么材质 s31254是什么材料
- 举重妖精金福珠是什么韩剧
- 个税税率是指什么
- 生地生长需要什么条件
- 附源码 springboot网络空间安全实验教学示范中心网站 毕业设计 111
- 《云计算框架与应用课程论文》