贪心算法习题

第4章贪心算法1课程安排

12345678910111213141516周二PPTTPTTPTTPTTTTP周四PPPPPPPPPPPPPP端午考试

T2第4章贪心算法会场安排问题最优合并问题磁带最优存储问题磁盘文件最优存储问题程序存储问题最优服务次序问题多处最优服务次序问题d森林问题汽车加油问题区间覆盖问题硬币找钱问题

删数问题数列极差问题嵌套箱问题

套汇问题信号增强装置问题磁带最大利用率问题非单位时间任务安排问题多元Huffman编码问题多元Huffman编码变形

区间相交问题任务时间表问题最优分解问题可重复最优分解问题可重复最优组合分解问题旅行规划问题登山机器人问题3算法实现题4-1会场安排问题问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)编程任务：对于给定的k个待安排的活动，编程计算使用最少会场的时间表(必须都安排完成)。4算法实现题4-1会场安排问题数据输入：第一行有1个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。结果输出:最少会场数。输入文件51231228253527803650输出示例35算法实现题4-5程序存储问题问题描述：设有n个程序{1,2,…,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤

i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。6算法实现题4-5程序存储问题数据输入：第一行是2个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。结果输出:最多可以存储的程序数。输入示例

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;

//所有的程序都没有磁带长}算法实现题4-5程序存储问题i012345x238132080贪心策略：最短程序优先排序后的数据8算法实现题4-6最优服务次序问题问题描述：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1<=i<=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。编程任务：对于给定的n个顾客需要的服务时间，编程计算最优服务次序。9算法实现题4-6最优服务次序问题数据输入：第一行是正整数n，表示有n个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。结果输出:计算出的最小平均等待时间。输入示例10

56121991000234335599812输出示例

532.0010算法实现题4-6最优服务次序问题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;读取数据：intn;scanf(“%d”,&n);inttemp;for(inti=0;i<n;i++){

scanf(“%d”,&temp);

x.push_back(temp);}11算法实现题4-7多处最优服务次序问题问题描述：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1<=i<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。编程任务：对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。12算法实现题4-7多处最优服务次序问题数据输入：第一行有2个正整数n和s，表示有n个顾客且有s处可以提供顾客需要的服务。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。结果输出:最小平均等待时间。输入示例10256121991000234335599812输出示例33613算法实现题4-7多处最优服务次序问题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排序后的数据st服务数组01112su求和数组0111214算法实现题4-9汽车加油问题问题描述一辆汽车加满油后可行驶nkm。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。编程任务对于给定的n和k个加油站位置，编程计算最少加油次数。15算法实现题4-9汽车加油问题数据输入第1行有2个正整数n和k，表示汽车加满油后可行驶nkm，且旅途有k个加油站。接下来的一行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。结果输出计算出的最少加油次数。如果无法到达目的地，则输出”NoSolution”。输入示例

77

12345166输出示例

4起点终点加油站数01234567812345166x16算法实现题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起点终点加油站数01234567812345166x17算法实现题4-9汽车加油问题读取数据：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算法实现题4-10区间覆盖问题问题描述：设x1,x2,...,xn

是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计解此问题的有效算法。编程任务：对于给定的实直线上的n个点和闭区间的长度k，编程计算覆盖点集的最少区间数。19算法实现题4-10区间覆盖问题数据输入：第一行有2个正整数n和k，表示有n个点，且固定长度闭区间的长度为k。接下来的1行中，有n个整数，表示n个点在实直线上的坐标（可能相同）。结果输出:最少区间数。输入示例7312345-26输出文件示例

30123456-2-1012345620算法实现题4-10区间覆盖问题intgreedy(vector<int>x,intk){

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

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

inttemp=x[0]; //区间的起始位置

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

if(x[i]-temp>k)

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

returnsum;}0123456-2-1012345621算法实现题4-12删数问题问题描述：给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。编程任务：对于给定的正整数a，编程计算删去k个数字后得到的最小数。22算法实现题4-12删数问题数据输入：文件的第1行是1个正整数a。第2行是正整数k。结果输出:计算出的最小数。输入示例1785434输出文件示例

1323算法实现题4-12删数问题voiddelek(stringa,intk)

{ //在整数a中删除k个数字

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个，最近下降点优先

}

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

//删除前导0能使用m吗？24算法实现题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算法实现题4-15套汇问题数据输入：本题有多个测试数据项。每个测试数据项的第一行中只有1个整数n(1≤n≤30)，表示货币总数。其后n行给出n种货币的名称。接下来的一行中有1个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每行有3个数据项ci

，rij

和cj

，表示货币ci

和cj的兑换率为rij。文件最后以数字0结束。结果输出:对每个测试数据项j，如果存在套汇的可能性则输出“Casejyes”，否则输出“Casejno”。26算法实现题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;

//兑换率数目

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算法实现题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算法实现题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算法实现题4-21区间相交问题问题描述：给定x轴上n个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。编程任务：给定n个闭区间，编程计算去掉的最少闭区间数。数据输入：第一行是正整数n，表示闭区间数。接下来的n行中，每行有2个整数，分别表示闭区间的2个端点。结果输出:计算出的去掉的最少闭区间数。输入示例3102010152015输出文件示例

2

//与活动安排类似if(a>b)swap(a,b);按右端点从小到大排序;依左端点超过右端点进行选择.30算法实现题4-21区间相交问题数据结构：structinterval{

intstart;

intend;};比较函数：boolcmp(intervala,intervalb){

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

elsereturnfalse;}31算法实现题4-21区间相交问题在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算法实现题4-21区间相交问题贪心选择：intGreedySelector(intn,intervalinte[]){

intcount=1;

intj=0; //区间的起点

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

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

count++;j=i;

}

}

returncount;}start5679701709910120end678189910010010010221033算法实现题4-23最优分解问题问题描述：设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。编程任务：对于给定的正整数n，编程计算最优分解方案。数据输入：第