四貪心算法習(xí)題參考答案

1、第四章作業(yè)部分參考答案1設(shè)有個顧客同時等待一項服務(wù)。顧客需要的服務(wù)時間為niniti??1。應(yīng)該如何安排個顧客的服務(wù)次序才能使總的等待時間達到最??？總的等待n時間是各顧客等待服務(wù)的時間的總和。試給出你的做法的理由（證明）。策略：對進行排序，然后按照遞增順序依次服務(wù)1itin??21niiittt????即可。12...niii解析：設(shè)得到服務(wù)的顧客的順序為，則總等待時間為12...njjj則在總等待時間T中的權(quán)重最大，2)2()1(12

2、21?????????nnjjjjtttntnT?1jtjnt的權(quán)重最小。故讓所需時間少的顧客先得到服務(wù)可以減少總等待時間。證明：設(shè)，下證明當按照不減順序依次服務(wù)時，為最優(yōu)策略。21niiittt????記按照次序服務(wù)時，等待時間為，下證明任意互換兩者的次序，niii?21T都不減。即假設(shè)互換兩位顧客的次序，互換后等待總時間為，則Tji)(ji?T~有.~TT?由于2)2()1(1221?????????nniiiitttntnT?2)

3、()()2()1(1221???????????????nnjiiiiiiitttjntintntnT???2)()()2()1(~1221???????????????nnijiiiiiitttjntintntnT???則有.0))((~?????ijiittijTT同理可證其它次序，都可以由經(jīng)過有限次兩兩調(diào)換順序后得到，而niii?21每次交換，總時間不減，從而為最優(yōu)策略。niii?21推廣到n個字符：第1個字符：n1個1，????

4、1111?n第2個字符：n2個1，1個0，01112?????n第3個字符：n3個1，1個0，01113?????n……第n1個字符：1個1，1個0，10第n個字符：1個0，03設(shè)是準備存放到長為L的磁帶上的n個程序，程序需要nppp21?ip的帶長為。設(shè)，要求選取一個能放在帶上的程序的最大子集合（即iaLanii???1其中含有最多個數(shù)的程序）。構(gòu)造的一種貪心策略是按的非降次序?qū)⒊蘍Qia序計入集合。1)證明這一策略總能找到最大子集，

5、使得。Q???QpiiLa2)設(shè)是使用上述貪心算法得到的子集合，磁帶的利用率可以小到何種程度？Q3)試說明1)中提到的設(shè)計策略不一定得到使取最大值的子集合。??QpiiLa1）證明：不妨設(shè)，若該貪心策略構(gòu)造的子集合為12...naaa???Q21saaa?，則滿足。s????????sisssiiLaaLa111、要證明能找到最大子集，只需說明s為可包含的最多程序段數(shù)即可。即證不存在多于s個的程序集合，使得。)(~21skaaaQkii