贪心算法-最优合并问题

《贪心算法-最优合并问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上机04实验名称一、问题11、问题描述一、最优合并问题给定k个有序序列s1,s2,...,sk,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少，编程实现该算法并证明算法的正确性。2、算法设计思想贪心算法3、算法过程描述原问题S={S1，S2，S3，S4..Sn}，（合并顺序）设最优解为Ck(最少合并次数)设Si,Sj为最短的两个序列反证法证明贪心选择性质：设有另一个最优解Ck

2、1（没有使用贪心选择性质，即没有先合并Si,Sj）构造一课二叉合并树SiSk为任意序列，Sk>si,sjSjSkSSkSiSj由图可知，Ck-Ck1=(Sk+Sj-1)+(Si+Sj+si-1)-(Si+sj-1)+(Si+Sj+Sk-1)=Sk-Si>0因此Ck1不是最优解，因此具有贪心选择性质最优子结构证明：S={S1，S2，S3，S4….Sn}记Si和Sj的合并为（Si,Sj）->Si+jS=S-{S1,S2}∪Si+j∴Ck=Ck`+(Si+Sj-1)4、算法实现及运行结果#include

3、>#includeusingnamespacestd;//计算最优值intminSum(int*a,intm){intb[m];intsum=0;for(inti=0;i1){sort(b,b+m);b[0]=b[1]+b[0];sum+=b[0]-1;for(inti=1;i

4、",&n);inta[n+1];printf("请输入各个序列长度:");for(inti=0;i