貪心算法習題

第4章貪心算法1課程安排

12345678910111213141516周二PPTTPTTPTTPTTTTP周四PPPPPPPPPPPPPP端午考試

T2第4章貪心算法會場安排問題最優(yōu)合并問題磁帶最優(yōu)存儲問題磁盤文件最優(yōu)存儲問題程序存儲問題最優(yōu)服務次序問題多處最優(yōu)服務次序問題d森林問題汽車加油問題區(qū)間覆蓋問題硬幣找錢問題

刪數(shù)問題數(shù)列極差問題嵌套箱問題

套匯問題信號增強裝置問題磁帶最大利用率問題非單位時間任務安排問題多元Huffman編碼問題多元Huffman編碼變形

區(qū)間相交問題任務時間表問題最優(yōu)分解問題可重復最優(yōu)分解問題可重復最優(yōu)組合分解問題旅行規(guī)劃問題登山機器人問題3算法實現(xiàn)題4-1會場安排問題問題描述：假設要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設計一個有效的貪心算法進行安排。(這個問題實際上是著名的圖著色問題。若將每一個活動作為圖的一個頂點，不相容活動間用邊相連。使相鄰頂點著有不同顏色的最小著色數(shù)，相應于要找的最小會場數(shù)。)編程任務：對于給定的k個待安排的活動，編程計算使用最少會場的時間表(必須都安排完成)。4算法實現(xiàn)題4-1會場安排問題數(shù)據(jù)輸入：第一行有1個正整數(shù)k，表示有k個待安排的活動。接下來的k行中，每行有2個正整數(shù)，分別表示k個待安排的活動開始時間和結束時間。時間以0點開始的分鐘計。結果輸出:最少會場數(shù)。輸入文件51231228253527803650輸出示例35算法實現(xiàn)題4-5程序存儲問題問題描述：設有n個程序{1,2,…,n}要存放在長度為L的磁帶上。程序i存放在磁帶上的長度是li，1≤

i≤n。程序存儲問題要求確定這n個程序在磁帶上的一個存儲方案，使得能夠在磁帶上存儲盡可能多的程序。編程任務：對于給定的n個程序存放在磁帶上的長度，編程計算磁帶上最多可以存儲的程序數(shù)。6算法實現(xiàn)題4-5程序存儲問題數(shù)據(jù)輸入：第一行是2個正整數(shù)，分別表示文件個數(shù)n和磁帶的長度L。接下來的1行中，有n個正整數(shù)，表示程序存放在磁帶上的長度。結果輸出:最多可以存儲的程序數(shù)。輸入示例

650

231388020輸出示例

5i012345x2313880207intgreedy(vector<int>x,intm){

inti=0,sum=0,n=x.size();

sort(x.begin(),x.end());

while(i<n){

sum+=x[i];

if(sum<=m)i++;

elsereturni;

}

returnn;

//所有的程序都沒有磁帶長}算法實現(xiàn)題4-5程序存儲問題i012345x238132080貪心策略：最短程序優(yōu)先排序后的數(shù)據(jù)8算法實現(xiàn)題4-6最優(yōu)服務次序問題問題描述：設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti,1<=i<=n。應如何安排n個顧客的服務次序才能使平均等待時間達到最小?平均等待時間是n個顧客等待服務時間的總和除以n。編程任務：對于給定的n個顧客需要的服務時間，編程計算最優(yōu)服務次序。9算法實現(xiàn)題4-6最優(yōu)服務次序問題數(shù)據(jù)輸入：第一行是正整數(shù)n，表示有n個顧客。接下來的1行中，有n個正整數(shù)，表示n個顧客需要的服務時間。結果輸出:計算出的最小平均等待時間。輸入示例10

56121991000234335599812輸出示例

532.0010算法實現(xiàn)題4-6最優(yōu)服務次序問題doublegreedy(vector<int>x){

inti,n=x.size();

sort(x.begin(),x.end());

for(i=1;i<n;++i)

x[i]+=x[i-1];

doublet=0;

for(i=0;i<n;++i)t+=x[i];

t/=n;

returnt;}i0123456789x11233555699992348121000加1134610115725635558914012401定義：vector<int>x;讀取數(shù)據(jù)：intn;scanf(“%d”,&n);inttemp;for(inti=0;i<n;i++){

scanf(“%d”,&temp);

x.push_back(temp);}11算法實現(xiàn)題4-7多處最優(yōu)服務次序問題問題描述：設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti,1<=i<=n。共有s處可以提供此項服務。應如何安排n個顧客的服務次序才能使平均等待時間達到最小?平均等待時間是n個顧客等待服務時間的總和除以n。編程任務：對于給定的n個顧客需要的服務時間和s的值，編程計算最優(yōu)服務次序。12算法實現(xiàn)題4-7多處最優(yōu)服務次序問題數(shù)據(jù)輸入：第一行有2個正整數(shù)n和s，表示有n個顧客且有s處可以提供顧客需要的服務。接下來的1行中，有n個正整數(shù)，表示n個顧客需要的服務時間。結果輸出:最小平均等待時間。輸入示例10256121991000234335599812輸出示例33613算法實現(xiàn)題4-7多處最優(yōu)服務次序問題doublegreed(vector<int>x,ints){

vector<int>st(s+1,0);

vector<int>su(s+1,0);

intn=x.size();

sort(x.begin(),x.end());

inti=0,j=0;

while(i<n){

st[j]+=x[i];

su[j]+=st[j];

++i,++j;

if(j==s)j=0;

}

doublet=0;

for(i=0;i<s;++i)t+=su[i];

t/=n;

returnt;}i0123456789x11233555699992348121000排序后的數(shù)據(jù)st服務數(shù)組01112su求和數(shù)組0111214算法實現(xiàn)題4-9汽車加油問題問題描述一輛汽車加滿油后可行駛nkm。旅途中有若干個加油站。設計一個有效算法，指出應在哪些加油站?？考佑?，使沿途加油次數(shù)最少。編程任務對于給定的n和k個加油站位置，編程計算最少加油次數(shù)。15算法實現(xiàn)題4-9汽車加油問題數(shù)據(jù)輸入第1行有2個正整數(shù)n和k，表示汽車加滿油后可行駛nkm，且旅途有k個加油站。接下來的一行中，有k+1個整數(shù)，表示第k個加油站與第k-1個加油站之間的距離。第0個加油站表示出發(fā)地，汽車已加滿油。第k+1個加油站表示目的地。結果輸出計算出的最少加油次數(shù)。如果無法到達目的地，則輸出”NoSolution”。輸入示例

77

12345166輸出示例

4起點終點加油站數(shù)01234567812345166x16算法實現(xiàn)題4-9汽車加油問題intgreedy(vector<int>x,intn){

intj,i,s,sum=0,k=x.size();

for(j=0;j<k;++j)

if(x[j]>n)

{

cout<<"NoSoultion"<<endl;

return-1;

}

for(i=0,s=0;i<k;++i)

{

s+=x[i];

if(s>n)sum++,s=x[i];

}

returnsum;}k01234567x12345166i=310i=49i=612i=712起點終點加油站數(shù)01234567812345166x17算法實現(xiàn)題4-9汽車加油問題讀取數(shù)據(jù)：intt,n,k;scanf("%d%d",&n,&k);vector<int>x;for(inti=0;i<=k;i++){

scanf("%d",&t);

x.push_back(t);

}調用和輸出：inttemp=greedy(x,n);if(temp>=0)printf("%d\n",temp);18算法實現(xiàn)題4-10區(qū)間覆蓋問題問題描述：設x1,x2,...,xn

是實直線上的n個點。用固定長度的閉區(qū)間覆蓋這n個點，至少需要多少個這樣的固定長度閉區(qū)間?設計解此問題的有效算法。編程任務：對于給定的實直線上的n個點和閉區(qū)間的長度k，編程計算覆蓋點集的最少區(qū)間數(shù)。19算法實現(xiàn)題4-10區(qū)間覆蓋問題數(shù)據(jù)輸入：第一行有2個正整數(shù)n和k，表示有n個點，且固定長度閉區(qū)間的長度為k。接下來的1行中，有n個整數(shù)，表示n個點在實直線上的坐標（可能相同）。結果輸出:最少區(qū)間數(shù)。輸入示例7312345-26輸出文件示例

30123456-2-1012345620算法實現(xiàn)題4-10區(qū)間覆蓋問題intgreedy(vector<int>x,intk){

inti,sum=1,n=x.size();

sort(x.begin(),x.end());

inttemp=x[0]; //區(qū)間的起始位置

for(i=1;i<n;++i)

if(x[i]-temp>k)

{sum++,temp=x[i]};

returnsum;}0123456-2-1012345621算法實現(xiàn)題4-12刪數(shù)問題問題描述：給定n位正整數(shù)a，去掉其中任意k≤n個數(shù)字后，剩下的數(shù)字按原次序排列組成一個新的正整數(shù)。對于給定的n位正整數(shù)a和正整數(shù)k，設計一個算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。編程任務：對于給定的正整數(shù)a，編程計算刪去k個數(shù)字后得到的最小數(shù)。22算法實現(xiàn)題4-12刪數(shù)問題數(shù)據(jù)輸入：文件的第1行是1個正整數(shù)a。第2行是正整數(shù)k。結果輸出:計算出的最小數(shù)。輸入示例1785434輸出文件示例

1323算法實現(xiàn)題4-12刪數(shù)問題voiddelek(stringa,intk)

{ //在整數(shù)a中刪除k個數(shù)字

intm=a.size();

if(k>=m){a.erase();return;}

//全部刪除

while(k>0)

{

//尋找最近下降點

inti;

for(i=0;(i<a.size()-1)&&(a[i]<=a[i+1]);++i);

a.erase(i,1),k--;

//每次刪除1個，最近下降點優(yōu)先

}

while(a.size()>1&&a[0]=='0')a.erase(0,1);}

//刪除前導0能使用m嗎？24算法實現(xiàn)題4-15套匯問題問題描述：套匯是指利用貨幣匯兌率的差異將一個單位的某種貨幣轉換為大于一個單位的同種貨幣。例如，假定1美元可以買0.7英鎊，1英鎊可以買9.5法郎，且1法郎可以買到0.16美元。通過貨幣兌換，一個商人可以從1美元開始買入，得到0.7×9.5×0.16=1.064美元，從而獲得6.4%的利潤。編程任務：給定n種貨幣c1,c2,c3,...,cn的有關兌換率，試設計一個有效算法，用以確定是否存在套匯的可能性。25輸入示例3USDollarBritishPoundFrenchFranc3USDollar0.5BritishPoundBritishPound10.0FrenchFrancFrenchFranc0.21USDollar0輸出示例Case1yes算法實現(xiàn)題4-15套匯問題數(shù)據(jù)輸入：本題有多個測試數(shù)據(jù)項。每個測試數(shù)據(jù)項的第一行中只有1個整數(shù)n(1≤n≤30)，表示貨幣總數(shù)。其后n行給出n種貨幣的名稱。接下來的一行中有1個整數(shù)m，表示有m種不同的貨幣兌換率。其后m行給出m種不同的貨幣兌換率，每行有3個數(shù)據(jù)項ci

，rij

和cj

，表示貨幣ci

和cj的兌換率為rij。文件最后以數(shù)字0結束。結果輸出:對每個測試數(shù)據(jù)項j，如果存在套匯的可能性則輸出“Casejyes”，否則輸出“Casejno”。26算法實現(xiàn)題4-15套匯問題while(1){

cin>>n;

if(n==0)break;

//輸入結束

for(i=0;i<n;++i)cin>>name[i];

//讀取貨幣名稱

for(i=0;i<n;++i)

for(j=0;j<n;++j)r[i][j]=0.0;

//清0

cin>>edges;

//兌換率數(shù)目

for(i=0;i<edges;++i)

{

cin>>a>>x>>b;

for(j=0;strcmp(a,name[j]);++j);

//確定a的下標

for(k=0;strcmp(b,name[k]);++k);

//確定b的下標

r[j][k]=x;

}

……}01200.000.500.0010.000.0010.0020.210.000.0027算法實現(xiàn)題4-15套匯問題while(1){

……

for(i=0;i<n;++i)r[i][i]=max(1.0,r[i][i]);

//自身至少為1

for(k=0;k<n;++k)

//Floyd算法

for(i=0;i<n;++i)

for(j=0;j<n;++j)

r[i][j]=max(r[i][j],r[i][k]*r[k][j]);

for(i=0;i<n;++i)if(r[i][i]>1.0)break;

//搜索贏利情況

if(i<n)cout<<"case"<<(cases)<<"yes"<<endl;

elsecout<<"case"<<(cases)<<"no"<<endl;}01200.000.500.0010.000.0010.0020.210.000.0001201.050.535.2512.101.0510.5020.220.111.10只要搜到一個贏利就行28算法實現(xiàn)題4-15套匯問題3USDollarBritishPoundFrenchFranc6USDollar0.5BritishPoundUSDollar4.9FrenchFrancBritishPound10.0FrenchFrancBritishPound1.99USDollarFrenchFranc0.09BritishPoundFrenchFranc0.19USDollarAnswer:no01200.000.504.911.990.0010.0020.190.090.0001201.000.505.0011.991.0010.0020.190.101.0029算法實現(xiàn)題4-21區(qū)間相交問題問題描述：給定x軸上n個閉區(qū)間。去掉盡可能少的閉區(qū)間，使剩下的閉區(qū)間都不相交。編程任務：給定n個閉區(qū)間，編程計算去掉的最少閉區(qū)間數(shù)。數(shù)據(jù)輸入：第一行是正整數(shù)n，表示閉區(qū)間數(shù)。接下來的n行中，每行有2個整數(shù)，分別表示閉區(qū)間的2個端點。結果輸出:計算出的去掉的最少閉區(qū)間數(shù)。輸入示例3102010152015輸出文件示例

2

//與活動安排類似if(a>b)swap(a,b);按右端點從小到大排序;依左端點超過右端點進行選擇.30算法實現(xiàn)題4-21區(qū)間相交問題數(shù)據(jù)結構：structinterval{

intstart;

intend;};比較函數(shù)：boolcmp(intervala,intervalb){

if(a.end<b.end)returntrue;

elsereturnfalse;}31算法實現(xiàn)題4-21區(qū)間相交問題在intmain()中：

intn;

inta,b;

cin>>n;

intervalinte[100];

for(inti=0;i<n;i++){

cin>>a>>b;

if(a>b)swap(a,b);

inte[i].start=a;

inte[i].end=b;

}

sort(inte,inte+n,cmp);

cout<<n-GreedySelector(n,inte)<<endl;start1520767070991019end100621087100991001021832算法實現(xiàn)題4-21區(qū)間相交問題貪心選擇：intGreedySelector(intn,intervalinte[]){

intcount=1;

intj=0; //區(qū)間的起點

for(inti=1;i<n;i++){

if(inte[i].start>inte[j].end){

count++;j=i;

}

}

returncount;}start5679701709910120end678189910010010010221033算法實現(xiàn)題4-23最優(yōu)分解問題問題描述：設n是一個正整數(shù)?，F(xiàn)在要求將n分解為若干個互不相同的自然數(shù)的和，且使這些自然數(shù)的乘積最大。編程任務：對于給定的正整數(shù)n，編程計算最優(yōu)分解方案。數(shù)據(jù)輸入：第