中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)學(xué)院計(jì)算機(jī)算法劉玉貴期末題庫(kù)習(xí)題答案-第四章貪心算法練習(xí)參考答案

第四章練習(xí)參考答案習(xí)題四1解：設(shè)調(diào)度f(wàn)為:i1,i2,…,in，作業(yè)ik需等待，即作業(yè)1等待0，作業(yè)2等待i1，作業(yè)3等待i1+i2….，總的等待時(shí)間為：T(f)=。使用貪心策略：服務(wù)時(shí)間短的作業(yè)先安排。算法描述略。正確性：交換論證。不妨假設(shè)t1≤t2≤t2≤…≤tn,算法的調(diào)度f(wàn)結(jié)果為1,2,..,n。設(shè)它不是最優(yōu)的，存在最優(yōu)調(diào)度f(wàn)*，設(shè)其最早第k項(xiàng)作業(yè)ik與f不同,即f*:1,2,..k-1,ik,ik+1…in，必有tik>=tk。今將f*中作業(yè)K與作業(yè)ik置換，得到調(diào)度f(wàn)**：1,2…k,ik+1,…ik…in。其中ik位置為j，則j>k,tik>=tk。則：T(f*)-T(f**)=(n-k)tik+(n-j)tk-(n-k)tk-(n-j)tik=(j-k)tik+(k-j)tk=(j-k)(tik-tk)>=0說(shuō)明f**也是最優(yōu)調(diào)度，但它與f不同的次序項(xiàng)后移了一位。重復(fù)此過(guò)程最多n步，可得f最優(yōu)。2.解：a-h的頻率為：1,1,2,3,5,8,13,21,按huffman規(guī)則，編碼為0000000,0000001,000001,00001,0001,001,01,1設(shè)前k個(gè)字符符合：f0+f1+..+fk-1<fk+1成立(1<k<8已成立),則F0+f1+…+fk-1+fk<fk+1+fk=fk+2,定義字符zk=f0+f1+..+fk-1，則對(duì)任意k，zk<fk+1經(jīng)huffman編碼k-1步后，得zk,fk,fk+1,….,據(jù)上，zk<fk+1,而顯然fk<fk+1Zk,fk是最小頻率的兩個(gè)數(shù)，合并，依次類推，每次都是新字符與下一個(gè)Fibonacci數(shù)合并，所以，f0-fn的編碼為000…0,000…1,..001,01,1。其中fk的編碼為000..01，共n-k個(gè)0（k>0），f0:n個(gè)0。3解：(1)反正法。設(shè)算法得到的程序集合為Q不是最優(yōu)的，Q*是一個(gè)最優(yōu)集合，則Q與Q*無(wú)包含關(guān)系。Q不能包含Q*是顯然的，如果Q*包含Q，那么對(duì)pQ*\Q，如果p不小于Q的成員，算法將會(huì)在接下來(lái)的判斷中將其選入(不超L)，否則，它先被檢查，早應(yīng)該是Q的成員。取Q*使得|QQ*|最大。令p是Q\Q*中最小的，則Q中比p更小的程序一定在Q*中(陰影部分)。則任給p*Q*\Q，必有p*>=P。否則，若p*<P，ｐ*在P前被算法檢查，此時(shí)磁帶裝入的程序均在QQ*即Q*中，P*不被選入，說(shuō)明此時(shí)磁帶已裝不下p*，但P*在Q*里，說(shuō)明P*在QQ*之外可以裝入，矛盾。將Q*中的P*換成P，顯然可以裝入，得到Q**，也是最優(yōu)的，但|Q**Q|>|Q*Q|，與Q*的選取矛盾。得證。(2)磁帶利用率為該是集合Q中所有程序的長(zhǎng)度之和/L，可以為0，如果一個(gè)也裝入不了。(3)反例，l=8,n=4,a1=1,a2=2,a3=3,a4=4,算法裝入p1,p2,p3,帶長(zhǎng)浪費(fèi)2，而裝入p1,p3,p4，帶長(zhǎng)浪費(fèi)0。4.見課件。二、1.解：使用貪心法：令a1,a2,…表示基站的位置。貪心策略：首先令a1=d1+4，對(duì)d2,d3,…dn依次檢查，找到下一個(gè)不能被該基站覆蓋的房子。如果dk<=a1+4但dk+1>a1+4,那么第k+1個(gè)房子不能被基站覆蓋，于是取a2=dk+1+4作為下一個(gè)基站的位置，照此下去，直到檢查完dn為止。算法偽碼：Location()輸入：距離d1,d2,…,dn的數(shù)組d[1..n]:滿足d[1]<d[2]<…<d[n]輸出：基站位置的數(shù)組a[..]a[1]:=d[1]+4K:=1forj:=2tonIfd[j]>a[k]+4Thenk:=k+1a[k]:=d[j]+4Returna算法的正確性證明使用歸納法：對(duì)任何正正整數(shù)k，存在最優(yōu)解包含算法前k步選擇的基站位置。證明：k=1，存在最優(yōu)解包含a[1]。若不然，有最優(yōu)解OPT，其第一個(gè)基站位置是b[1]，b[1]≠a[1]。那么d1-4≤b[1]<d1+4=a[1]。B[1]覆蓋的是距離在[d1,b[1]+4]之間的房子。A[1]覆蓋的是距離[d1,a[1]+4]的房子，因?yàn)閎[1]<a[1],b[1]覆蓋的房子都在a[1]覆蓋的區(qū)域內(nèi)，用a[1]替換b[1]，得到的仍舊是最優(yōu)解。假設(shè)對(duì)于k存在最優(yōu)解A包含算法前k步的選擇的基站，即A={a[1],a[2]…a[k]}∪B，其中a[1],a[2]…a[k]覆蓋了距離d1,d2,…,dj的房子，那么B是關(guān)于L={dj+1,dj+2,…,dn}的最優(yōu)解。否則，存在關(guān)于L的最優(yōu)解B*，那么用B*替換B得得到A*，且|A*|<|A|，與A是最優(yōu)解矛盾。根據(jù)歸納假設(shè)，L有一個(gè)最優(yōu)解B/={a[k+1],…,}，|B/|=|B|。于是，A/={a[1],a[2],…,a[k]}∪B/={a[1],a[2],…,a[k+1]…}也是最優(yōu)解，且|A|=|A/|，從而證明了結(jié)論對(duì)k+1也真。證畢。算法復(fù)雜度T(n)=O(n)。2.解：使用貪心法。貪心策略：把進(jìn)程按截止時(shí)間排序。取第一個(gè)進(jìn)程的截止時(shí)間作為第一個(gè)測(cè)試點(diǎn)，然后順序檢查后續(xù)能夠被這個(gè)測(cè)試點(diǎn)檢測(cè)的進(jìn)程(這些進(jìn)程的開始時(shí)間小于測(cè)試點(diǎn))，直到找到下一個(gè)不能夠被這個(gè)測(cè)試點(diǎn)測(cè)試到的進(jìn)程為止。取這個(gè)進(jìn)程的截止時(shí)間作為下一個(gè)測(cè)試點(diǎn)，……,知道檢查完所有的進(jìn)程為止。算法描述：Test()輸入：s[1..n]，d[1..n]；輸出：t[]，順序選定的測(cè)試點(diǎn)構(gòu)成的數(shù)組將進(jìn)程按d[i]遞增順序排序，使d[1]≤d[2]≤…≤d[n]i:=1,t[i]=d[i]j:=2do{whilej<nands[j]≤t[i]do{j:=j+1}ifj>nthenreturntelsei:=i+1t[i]:=d[j]j:=j+1endifuntilj>n用歸納法證明其正確性:任給k，存在最優(yōu)解包含算法前k步選擇的結(jié)果。證明：k=1，設(shè)s={t[i1],t[i2]，…}是最優(yōu)解，則一定t[i1]<t[1],否則t[i1]不能測(cè)試d[1]的進(jìn)程。設(shè)pu是在時(shí)刻t[i1]被檢測(cè)到的任意進(jìn)程，則s[u]≤t[i1]≤d[u]，從而s[u]≤t[i1]<t[1]=d[1]≤d[u]，因此，pu也可以在t[1]時(shí)刻被測(cè)試，在s中將t[i1]替換為t[1]也是最優(yōu)解。假設(shè)結(jié)論對(duì)k成立，則存在最優(yōu)解T={t[1],t[2],…,t[k]}∪T/。設(shè)算法前k步選擇的測(cè)試點(diǎn)不能測(cè)到的進(jìn)程構(gòu)成集合QP，P是全部進(jìn)程集合，那么T/是問(wèn)題Q的最優(yōu)解。根據(jù)歸納假設(shè)，存在Q的最優(yōu)解T*包含測(cè)試點(diǎn)t[k+1]，即T*={t[k+1]}∪T//，因此，{t[1],t[2],…,t[k]}∪T*={t[1],t[2],…,t[k],t[k+1]}∪T//也是原問(wèn)題的最優(yōu)解，得證。算法最壞時(shí)間復(fù)雜度：排序O(nlogn)，檢查O(n)，所以T(n)=O(nlogn)。３.解：使用貪心法。貪心規(guī)則：優(yōu)先安排前Ｄ個(gè)罰款最多的作業(yè)。正確性證明：交換論證。設(shè)算法選擇的作業(yè)調(diào)度ｆ的安排次序是<i1,i2,…,in>，那么罰款為F(f)=，任給k<=D<j，m(ik)>=m(ij)。顯然最優(yōu)調(diào)度沒有空閑時(shí)間，不妨設(shè)作業(yè)是連續(xù)安排的。每項(xiàng)作業(yè)的加工時(shí)間都是1，在D之前可完成D項(xiàng)作業(yè)，在D之后安排的n-D項(xiàng)作業(yè)iD+1,iD+2,…,in是被罰款的作業(yè)。設(shè)算法得到的安排不是最優(yōu)的，則存在一個(gè)最優(yōu)調(diào)度f(wàn)*，它的前D個(gè)作業(yè)包含了至少1個(gè)作業(yè)ij，j>D，從而至少有一個(gè)作業(yè)ik，k<=D被安排在了D之后。交換ik,ij得到新的調(diào)度f(wàn)**，則F(f*)-F(f**)=m(ik)-m(ij)≥0，說(shuō)明f**也是最優(yōu)調(diào)度，但f**與f的前D個(gè)相同作業(yè)多了1個(gè)，依次進(jìn)行，可得最優(yōu)作業(yè)與f相同，得證。算法描述：算法A:按m[i]非升排序，依次選擇作業(yè)即可。但T(n