貪心算法-最優(yōu)合并問(wèn)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上上機(jī)04 實(shí)驗(yàn)名稱一、 問(wèn)題11、 問(wèn)題描述一、最優(yōu)合并問(wèn)題給定k個(gè)有序序列s1 , s2,. , sk , 用2路合并算法將這k個(gè)序列合并成一個(gè)序列。假設(shè)所采用的2路合并算法合并2個(gè)長(zhǎng)度分別為m和n的序列需要m + n -1次比較。試設(shè)計(jì)一個(gè)算法確定合并這個(gè)序列的最優(yōu)合并順序，使所需的總比較次數(shù)最少，編程實(shí)現(xiàn)該算法并證明算法的正確性。2、 算法設(shè)計(jì)思想貪心算法3、 算法過(guò)程描述原問(wèn)題S=S1，S2，S3，S4.Sn，（合并順序）設(shè)最優(yōu)解為Ck(最少合并次數(shù))設(shè)Si,Sj為最短的兩個(gè)序列反證法證明貪心選擇性質(zhì)：設(shè)有另一個(gè)最優(yōu)解Ck1（沒(méi)有使用貪心選擇性質(zhì)，即沒(méi)有先合并

2、Si,Sj）構(gòu)造一課二叉合并樹(shù)Si Sk為任意序列，Sk>si,sjSjSkSSk SiSj由圖可知，Ck-Ck1=(Sk+Sj-1)+(Si+Sj+si-1)-(Si+sj-1)+(Si+Sj+Sk-1)=Sk-Si>0因此Ck1不是最優(yōu)解，因此具有貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)證明：S=S1，S2，S3，S4.Sn記Si和Sj的合并為（Si,Sj）->Si+jS=S-S1,S2Si+jCk=Ck+(Si+Sj-1)4、 算法實(shí)現(xiàn)及運(yùn)行結(jié)果 #include<stdio.h>#include<algorithm>using namespace std;/計(jì)算

3、最優(yōu)值int minSum(int *a,int m) int bm; int sum=0; for(int i=0;i<m;i+) bi=ai; while(m>1) sort(b,b+m); b0=b1+b0; sum+=b0-1; for(int i=1;i<m-1;i+) bi=bi+1; m-; return sum;int main () int n; printf("請(qǐng)輸入序列個(gè)數(shù):n"); scanf("%d",&n); int an+1; printf("請(qǐng)輸入各個(gè)序列長(zhǎng)度:n"); for(int i=0;i<n;i+) scanf("%d",&ai); printf("最少比較次數(shù)為：%dn",minSum(a,n);return 0;5、 算法復(fù)雜度分析及算法改進(jìn)時(shí)間復(fù)雜度：排序：O(nlogn)，合并(n-1)(2*O(1)+O