四貪心算法習題參考答案

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

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

3、()()2()1(1221???????????????nnjiiiiiiitttjntintntnT???2)()()2()1(~1221???????????????nnijiiiiiitttjntintntnT???則有.0))((~?????ijiittijTT同理可證其它次序，都可以由經(jīng)過有限次兩兩調換順序后得到，而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設是準備存放到長為L的磁帶上的n個程序，程序需要nppp21?ip的帶長為。設，要求選取一個能放在帶上的程序的最大子集合（即iaLanii???1其中含有最多個數(shù)的程序）。構造的一種貪心策略是按的非降次序將程QQia序計入集合。1)證明這一策略總能找到最大子集，

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