貪心算法習(xí)題

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

12345678910111213141516周二PPTTPTTPTTPTTTTP周四PPPPPPPPPPPPPP端午考試

T2第4章貪心算法會(huì)場(chǎng)安排問(wèn)題最優(yōu)合并問(wèn)題磁帶最優(yōu)存儲(chǔ)問(wèn)題磁盤(pán)文件最優(yōu)存儲(chǔ)問(wèn)題程序存儲(chǔ)問(wèn)題最優(yōu)服務(wù)次序問(wèn)題多處最優(yōu)服務(wù)次序問(wèn)題d森林問(wèn)題汽車(chē)加油問(wèn)題區(qū)間覆蓋問(wèn)題硬幣找錢(qián)問(wèn)題

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

套匯問(wèn)題信號(hào)增強(qiáng)裝置問(wèn)題磁帶最大利用率問(wèn)題非單位時(shí)間任務(wù)安排問(wèn)題多元Huffman編碼問(wèn)題多元Huffman編碼變形

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

i≤n。程序存儲(chǔ)問(wèn)題要求確定這n個(gè)程序在磁帶上的一個(gè)存儲(chǔ)方案，使得能夠在磁帶上存儲(chǔ)盡可能多的程序。編程任務(wù)：對(duì)于給定的n個(gè)程序存放在磁帶上的長(zhǎng)度，編程計(jì)算磁帶上最多可以存儲(chǔ)的程序數(shù)。6算法實(shí)現(xiàn)題4-5程序存儲(chǔ)問(wèn)題數(shù)據(jù)輸入：第一行是2個(gè)正整數(shù)，分別表示文件個(gè)數(shù)n和磁帶的長(zhǎng)度L。接下來(lái)的1行中，有n個(gè)正整數(shù)，表示程序存放在磁帶上的長(zhǎng)度。結(jié)果輸出:最多可以存儲(chǔ)的程序數(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;

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

56121991000234335599812輸出示例

532.0010算法實(shí)現(xiàn)題4-6最優(yōu)服務(wù)次序問(wèn)題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算法實(shí)現(xiàn)題4-7多處最優(yōu)服務(wù)次序問(wèn)題問(wèn)題描述：設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti,1<=i<=n。共有s處可以提供此項(xiàng)服務(wù)。應(yīng)如何安排n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最小?平均等待時(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。編程任務(wù)：對(duì)于給定的n個(gè)顧客需要的服務(wù)時(shí)間和s的值，編程計(jì)算最優(yōu)服務(wù)次序。12算法實(shí)現(xiàn)題4-7多處最優(yōu)服務(wù)次序問(wèn)題數(shù)據(jù)輸入：第一行有2個(gè)正整數(shù)n和s，表示有n個(gè)顧客且有s處可以提供顧客需要的服務(wù)。接下來(lái)的1行中，有n個(gè)正整數(shù)，表示n個(gè)顧客需要的服務(wù)時(shí)間。結(jié)果輸出:最小平均等待時(shí)間。輸入示例10256121991000234335599812輸出示例33613算法實(shí)現(xiàn)題4-7多處最優(yōu)服務(wù)次序問(wèn)題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服務(wù)數(shù)組01112su求和數(shù)組0111214算法實(shí)現(xiàn)題4-9汽車(chē)加油問(wèn)題問(wèn)題描述一輛汽車(chē)加滿(mǎn)油后可行駛nkm。旅途中有若干個(gè)加油站。設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使沿途加油次數(shù)最少。編程任務(wù)對(duì)于給定的n和k個(gè)加油站位置，編程計(jì)算最少加油次數(shù)。15算法實(shí)現(xiàn)題4-9汽車(chē)加油問(wèn)題數(shù)據(jù)輸入第1行有2個(gè)正整數(shù)n和k，表示汽車(chē)加滿(mǎn)油后可行駛nkm，且旅途有k個(gè)加油站。接下來(lái)的一行中，有k+1個(gè)整數(shù)，表示第k個(gè)加油站與第k-1個(gè)加油站之間的距離。第0個(gè)加油站表示出發(fā)地，汽車(chē)已加滿(mǎn)油。第k+1個(gè)加油站表示目的地。結(jié)果輸出計(jì)算出的最少加油次數(shù)。如果無(wú)法到達(dá)目的地，則輸出”NoSolution”。輸入示例

77

12345166輸出示例

4起點(diǎn)終點(diǎn)加油站數(shù)01234567812345166x16算法實(shí)現(xiàn)題4-9汽車(chē)加油問(wèn)題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起點(diǎn)終點(diǎn)加油站數(shù)01234567812345166x17算法實(shí)現(xiàn)題4-9汽車(chē)加油問(wèn)題讀取數(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);

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

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

30123456-2-1012345620算法實(shí)現(xiàn)題4-10區(qū)間覆蓋問(wèn)題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算法實(shí)現(xiàn)題4-12刪數(shù)問(wèn)題問(wèn)題描述：給定n位正整數(shù)a，去掉其中任意k≤n個(gè)數(shù)字后，剩下的數(shù)字按原次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a和正整數(shù)k，設(shè)計(jì)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。編程任務(wù)：對(duì)于給定的正整數(shù)a，編程計(jì)算刪去k個(gè)數(shù)字后得到的最小數(shù)。22算法實(shí)現(xiàn)題4-12刪數(shù)問(wèn)題數(shù)據(jù)輸入：文件的第1行是1個(gè)正整數(shù)a。第2行是正整數(shù)k。結(jié)果輸出:計(jì)算出的最小數(shù)。輸入示例1785434輸出文件示例

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

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

intm=a.size();

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

//全部刪除

while(k>0)

{

//尋找最近下降點(diǎn)

inti;

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

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

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

}

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

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

，rij

和cj

，表示貨幣ci

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

cin>>n;

if(n==0)break;

//輸入結(jié)束

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

//讀取貨幣名稱(chēng)

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的下標(biāo)

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

//確定b的下標(biāo)

r[j][k]=x;

}

……}01200.000.500.0010.000.0010.0020.210.000.0027算法實(shí)現(xiàn)題4-15套匯問(wèn)題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只要搜到一個(gè)贏利就行28算法實(shí)現(xiàn)題4-15套匯問(wèn)題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算法實(shí)現(xiàn)題4-21區(qū)間相交問(wèn)題問(wèn)題描述：給定x軸上n個(gè)閉區(qū)間。去掉盡可能少的閉區(qū)間，使剩下的閉區(qū)間都不相交。編程任務(wù)：給定n個(gè)閉區(qū)間，編程計(jì)算去掉的最少閉區(qū)間數(shù)。數(shù)據(jù)輸入：第一行是正整數(shù)n，表示閉區(qū)間數(shù)。接下來(lái)的n行中，每行有2個(gè)整數(shù)，分別表示閉區(qū)間的2個(gè)端點(diǎn)。結(jié)果輸出:計(jì)算出的去掉的最少閉區(qū)間數(shù)。輸入示例3102010152015輸出文件示例

2

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

intstart;

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

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

elsereturnfalse;}31算法實(shí)現(xiàn)題4-21區(qū)間相交問(wèn)題在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算法實(shí)現(xiàn)題4-21區(qū)間相交問(wèn)題貪心選擇：intGreedySelector(intn,intervalinte[]){

intcount=1;

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

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

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

count++;j=i;

}

}

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