《算法分析與設(shè)計(jì)》期末考試復(fù)習(xí)題綱(完整版)

第3步 第5步 第8步.回溯：沿E回溯到左孩子D,生成相應(yīng)右孩子 G,得到部分解(1,1,0,1，此時(shí)b=93.1b>bestp,可以生成右子樹(shù) (第4步在第5步的基礎(chǔ)上沒(méi)有 H和I的圖形).繼續(xù)生成結(jié)點(diǎn)H,I,得到可行解(1,1,0,1,0，價(jià)值為88,更新bestp=88(如圖第5步).回溯H生成J,得到部分解(1,1,0,0工估計(jì)部分解b=92>88(第6步在第8步的基礎(chǔ)上沒(méi)有K和L的圖形).繼續(xù)生成結(jié)點(diǎn)K,得到可行解(1,1,0,0,1),價(jià)值為92,更新bestp=92(第7步在第8步的基礎(chǔ)上沒(méi)有 L的圖形).K是左孩子，生成其對(duì)應(yīng)的右孩子 L,得到可行解(1,1,0,0,0)(如圖第8步).回溯,沿結(jié)點(diǎn)L向上回溯到結(jié)點(diǎn)B,生成結(jié)點(diǎn)M,得到部分解(1,0),估計(jì)部分解b=90<92,回溯(第9步在第10步的基礎(chǔ)上沒(méi)有 N的圖形).向上繼續(xù)回溯生成結(jié)點(diǎn) N，得到部分解 (0)，此時(shí)得到的 b=74+10*(46/27)=91.03<92,回溯，此時(shí)已回到根結(jié)點(diǎn)，結(jié)束。最優(yōu)解 (1,1,0,0,1),價(jià)值為92.(如圖第 10步)練習(xí)n=8,M=110，W=(1,11,21,23,33,43,45,55)P=(11,21,31,33,43,53,55,65)用回溯法求此 0-1背包問(wèn)題的最優(yōu)解。最優(yōu)裝載問(wèn)題 P119課件第P37-P54頁(yè)假定n=4，w=[8,6,2,3]，c1=c2=12.試根據(jù)改進(jìn)后的最優(yōu)裝載算法找出最優(yōu)裝載量及相應(yīng)的最優(yōu)裝載方案。要求：列出問(wèn)題的解空間。構(gòu)造解空間樹(shù)。根據(jù)遞歸回溯算法求出最優(yōu)解和最優(yōu)值。六、算法設(shè)計(jì)題使用貪心算法求解。題型一：開(kāi)會(huì)問(wèn)題：某公司的會(huì)議很多，以至于全公司唯一的會(huì)議室不夠用?，F(xiàn)在給出這段時(shí)期的會(huì)議時(shí)間表，要求你適當(dāng)刪除一些會(huì)議，使得剩余的會(huì)議在時(shí)間上互不沖突，要求刪除的會(huì)議數(shù)最少。解題算法 :template<classType>voidGS(intn,Types[],Typef[],boolA[]){A[1]=false;intj=1;intsum=0;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=false;j=i;}else{A[i]=true;sum++;}}}題型二：試用貪心算法求解下列問(wèn)題： 將正整數(shù) n分解為若干個(gè)互不相同的自然數(shù)之和， 使這些自然數(shù)的乘積最大，寫出該算法。先看看幾個(gè) n比較小的例子，看能否從中找出規(guī)律：算法分析：猜想一下是不是將n拆成盡量多的數(shù)乘積最大？(拆出的數(shù)中最小為 2)。為了使因數(shù)個(gè)數(shù)盡可能多，我們用 n減2、3-i,直到n<i。若此時(shí)n和i相等，則先將i+1,同時(shí)n-1。若此時(shí)n>0,則均勻地分給前面各項(xiàng)。因此我們可以得到一個(gè)貪心策略，即將 n不停地拆分開(kāi)來(lái)，使得所有的數(shù)都不同且不能再拆。解題算法：voiddicomp(a[])(k=l;if(n<3){a[l]=0;retum;};if(n<5){a[k]=l;a[++k]=n-1;retum;};a[l]=2;n-=2;while(n>aLk]){k++;a[k]=a[k-l]+l;n-=a[k];);if(n==a[k]){a[k]++;n—;};for(inti=0;i<n;i++)a[k_i]++;}題型三：田忌賽馬：如果3匹馬變成n匹，齊王仍然讓他的馬按從優(yōu)到劣的順序出賽，田忌可以按任意順序選擇他的賽馬出賽。贏一局，田忌可以得到 200兩銀子，輸一局，田忌就要輸?shù)?00兩銀子。已知國(guó)王和田忌的所有馬的奔跑速度，并且所有馬奔跑的速度均不相同，現(xiàn)已經(jīng)對(duì)兩人的馬分別從快到慢排好序，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，幫助田忌贏得最多的銀子。解題思路：先對(duì)兩組馬按速度排序。如果田忌(A)最快的馬比齊王(B)最快的馬快，直接贏；如果A最快的馬比B慢，用A最慢的馬拼