第4章贪心算法习题(免费阅读)

贪心算法求解问题问题分析：此问题为程序最优存储问题，问题要求最后存储的两个磁带上的长度差异就最小。

若在最优解中去掉i个程序段，显然在（n-i）个程序段的存储中应仍是最优解，因为此问题存在最优子结构。

另外，由于每个程序的长度不同，每将一个程序存储到A或者B（用A和B来表示两个磁带上存储程序的集合）后，显然还与后续怎么存储程序有关，即当前结果依赖子问题的结果。

这正是动态规划算法的基本特征，而贪心算法仅在当前状态下做出最好选择，然后再去做子问题的局部最优解最终就是问题的最优解，贪心算法不依赖于将来所做的子问题的解，显示，此问题是一个动态规划问题，是一个0-1背包问题。

虽然对有些问题，贪心算法并不能得到一个最优解，但往往能快速地得到一个近似最优解。

下面就来讨论如何用贪心算法得到近似最优解。

贪心算法思路为了使最后两个磁带的长度差异越小，就先将长度较大的程序优先放入到磁带（此处用A和B分别表示两个磁带）上。

因此排序选择递减排序。

用p[ ]数组来存放第i个程序长度为p[i-1]，首先将其按程序长度大小递减的顺序排序，将排好序的各程序下标记录到与与p[]等长的数组a[ ]中。

然后再根据a[]中记录的下标找到相应的程序p[a[i]]放到A或者B 中。

现在就接下就是如何存放来达到近似最优解的问题了开始A和B中没有任何元素（本程序中采用vector动态定义A，B），如果用sumA和sumB来标记A和B中已存入程序的总长度，在存入当前最优解时，先比较sumA和sumB 的大小，将最优解存入到程序总长度较短的那个程序集合，如果长度一样，则存入到A或者B中（本程序是存入到A集合中），可以看到这样存入的话，就会尽量减小A和B长度的差异，从而尽量接近最优存储得到近似最优解之前提交的贪心算法的思想是直接交叉存入到A和B中，那样得到的解在一定程度能得利近似最优解，那种思想只对程序段长度相差小的情况有比较好的结果，因为那种思想大概是将程序段平均到A和B中，在很多情况下不能得到近似最优解。

贪心算法1.喷水装置（一）描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入第一行m表示有m组测试数据每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出输出所用装置的个数样例输入252 3.2 4 4.5 6101 2 3 1 2 1.2 3 1.1 1 2样例输出25根据日常生活知道，选择半径越大的装置，所用的数目越少。

因此，可以先对半径排序，然后选择半径大的。

另外，当装置刚好喷到矩形的顶点时，数目最少。

此时只要装置的有效喷水距离的和不小于20时，输出此时的装置数目即可。

2.喷水装置（二）时间限制：3000 ms | 内存限制：65535 KB难度：4描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。

请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入对于每一组输入，输出最多能够安排的活动数量。

每组的输出占一行样例输入221 1010 1131 1010 1111 20样例输出12提示注意：如果上一个活动在T时间结束，下一个活动最早应该在T+1时间开始。

解题思路：这是一个贪心法中选择不相交区间的问题。

先对活动结束时间从小到大排序，排序的同时活动的起始时间也要跟着变化。

而且，结束时间最小的活动一定会安排，不然这段时间就白白浪费了。

后一个活动的起始时间如果比前一个活动的结束时间大，即两个活动没有相交时间，就把这个活动也安排上。

贪心算法经典例题引言贪心算法是一种常见的算法策略，它在求解问题时每一步都选择当前状态下的最优解，从而最终得到全局最优解。

本文将介绍一些经典的贪心算法例题，帮助读者更好地理解贪心算法的思想和应用。

背景知识在讨论贪心算法之前，我们先了解一些背景知识。

1. 贪心算法的特点贪心算法具有以下特点： - 每一步都选择当前状态下的最优解； - 不进行回溯；- 不保证能得到全局最优解，但通常能得到较优解； - 算法运行效率高。

2. 贪心算法的适用情况贪心算法适用于满足以下条件的问题： - 具有最优子结构性质：问题的最优解包含子问题的最优解； - 贪心选择性质：局部最优解能导致全局最优解； - 没有后效性：当前的选择不会影响后续的选择。

经典例题1：找零钱问题问题描述假设有1元、5元、10元、20元、50元、100元面值的纸币，如何用最少的纸币数量找零给顾客？对于找零问题，贪心算法可以得到最优解。

具体步骤如下： 1. 首先，我们选择最大面额的纸币进行找零。

2. 然后，将选择的纸币数量减去顾客需找的金额，得到剩余金额。

3. 重复步骤1和步骤2，直到剩余金额为0。

实现代码int[] denominations = {100, 50, 20, 10, 5, 1};int[] counts = new int[denominations.length];int amount = 168;for (int i = 0; i < denominations.length; i++) {counts[i] = amount / denominations[i];amount %= denominations[i];}System.out.println("找零纸币面额及数量：");for (int i = 0; i < denominations.length; i++) {if (counts[i] > 0) {System.out.println(denominations[i] + "元：" + counts[i] + "张");}}分析与总结通过贪心算法，我们可以得到找零纸币的最优解。

江西科学技术版小学信息技术五年级下册《主题活动：贪心算法》同步练习题附知识点归纳一、课文知识点归纳：1. 贪心算法的基本概念：（1）贪心算法是一种求解最优解问题的更简单、更迅速的设计技术。

（2）它以当前情况为基础，根据某个优化测度做出最优选择，而不考虑所有可能的整体情况。

（3）贪心算法通过自顶向下、迭代的方法做出相继的贪心选择，每做一次选择，问题就简化为一个规模更小的子问题。

2. 贪心算法的基本要素：（1）贪心选择性质：整体最优解可通过一系列局部最优解的选择达到，且每次选择不依赖于后续选择。

（2）最优子结构性质：问题的最优解包含其子问题的最优解。

3.贪心算法的步骤：（1）建立数学模型来描述问题。

（2）把求解的问题分成若干个子问题。

（3）对每个子问题求解，得到子问题的局部最优解。

（4）将子问题的局部最优解合成原问题的解。

4.贪心算法的特点：（1）简单易实现，计算效率高。

（2）适用于具有贪心选择性质和最优子结构性质的问题。

（3）得到的解通常是某种意义上的局部最优解，但不一定是全局最优解。

5.贪心算法的应用场景：（1）货币兑换问题（如找零钱问题）。

（2）背包问题（在限制条件下选择最大价值的物品）。

（3）活动选择问题（安排一系列活动使得尽可能多的活动被安排）。

二、同步练习题。

（一）、填空题。

1. 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优__________的选择，从而希望导致结果是全局最好或最优的算法。

2. 在解决背包问题时，如果背包容量为20千克，物品A重5千克价值100元，物品B重10千克价值150元，为了价值最大化，应先放入____________千克的物品。

3. 在活动选择问题中，若有多个活动的时间区间存在冲突，我们通常使用____________算法进行筛选。

（二）、选择题。

1. 下列关于贪心算法的说法，正确的是（）。

A. 贪心算法总是能得到全局最优解B. 贪心算法是一种启发式搜索算法C. 贪心算法只适用于特定类型的问题D. 贪心算法不需要考虑问题的整体结构2. 在教室调度问题中，若某间教室在某天的课程安排如下：课程A 9:00-10:00，课程B 9:30-10:30，课程C 10:30-11:30，则能在这间教室连续进行的课程是（）。

贪心法3.1 排队接水有n 个人在一个水龙头前排队接水，假如每个人接水的时间为T i ，请编程找出这n 个人排队的一种顺序，使得n 个人的平均等待时间最小。

【输入】输入文件共两行，第一行为n ；第二行分别表示第1个人到第n 个人每人的接水时间T 1，T 2，…，T n ，每个数据之间有1个空格。

【输出】输出文件有两行，第一行为一种排队顺序，即1到n 的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

【样例】 water.in water.out 10 3 2 7 8 1 4 9 6 10 5 56 12 1 99 1000 234 33 55 99 812 291.90 【算法分析】 平均等待时间是每个人的等待时间之和再除以n ，因为n 是一个常数，所以等待时间之和最小，也就是平均等待时间最小。

假设是按照1~n 的自然顺序排列的，则这个问题就是求以下公式的最小值：∑∑==⎪⎪⎭⎫⎝⎛=+⋯⋯+++⋯⋯++++++=ni i j j n T T T T T T T T T T total 1121321211)()()(如果用穷举的方法求解，就需要我们产生n 个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！ 其实，我们认真研究一下上面的公式，发现可以改写成如下形式：∑=--+=++⋯⋯+-+-+=ni i n n T i n T T T n T n nT total 11321)1(2)2()1(这个公式何时取最小值呢？对于任意一种排列k 1, k 2, k 3, …, k n ，当1k T ≤2k T ≤3k T ≤…≤n k T 时，total取到最小值。

如何证明呢？方法如下： 因为n j i k k k k k T T j n T i n T n nT total +⋯++-+⋯++-+⋯+-+=)1()1()1(21假设i <j ，而i k T <j k T ，这是的和为total 1，而把k i 和kj 互换位置，设新的和为total 2，则：))(())(1())(1())1()1(()1()1(12i j i j i j j i i j k k k k k k k k k k T T i j T T j n T T i n T j n T i n T j n T i n total total total --=-+---+-=+-++--+-++-=-=∆我们发现上述△total 恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。

贪⼼算法例题简单说明
1.选择不相交区间问题
贪⼼思路：按照结束时间的顺序排序，结束时间越早，后⾯就能放越多的事。

2.区间选点问题
贪⼼思路：从前往后扫每个区间的树⽊，数⽬的那个区间，从后往前种树。

3.区间覆盖问题
贪⼼思路：预处理完了之后，要找到右端点坐标最⼤的⼀个，直到到边。

这⾥我就要说⼀下了⼀定要注意上下的边界问题：
1.两个圆相切肯定不对，覆盖不全
2.覆盖圆与边相切也不对，覆盖不全
4.流⽔作业调度问题
贪⼼思路：
5.带期限和带罚款的单位时间任务调度
贪⼼思路：罚款越⼤，越要完成，所以罚款⼤的要先处理，将罚款⼤的放在能放区间的最后。

第四章作业 部分参考答案1． 设有n 个顾客同时等待一项服务。

顾客i 需要的服务时间为n i t i ≤≤1,。

应该如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。

试给出你的做法的理由（证明）。

策略：对 1i t i n ≤≤进行排序，,21n i i i t t t ≤≤≤ 然后按照递增顺序依次服务12,,...,ni i i 即可。

解析：设得到服务的顾客的顺序为12,,...,n j j j ，则总等待时间为,2)1(121n n j j j j t t t n nt T +++-+=- 则在总等待时间T 中1j t 的权重最大，jn t 的权重最小。

故让所需时间少的顾客先得到服务可以减少总等待时间。

证明：设,21n i i i t t t ≤≤≤ ，下证明当按照不减顺序依次服务时，为最优策略。

记按照n i i i 21次序服务时，等待时间为T ，下证明任意互换两者的次序，T都不减。

即假设互换j i ,)(j i <两位顾客的次序，互换后等待总时间为T ~，则有.~T T ≥由于,))(())(()2)(2()1)(1(21n j i i i i i i t j t j n i t i n t n t n T +--++--++--+--=,))(())(()2)(2()1)(1(~21n i j i i i i i t j t j n i t i n t n t n T +--++--++--+--=则有.0))((~≥--=-i j i i t t i j T T同理可证其它次序，都可以由n i i i 21经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而n i i i 21为最优策略。

2． 字符h a ~出现的频率分布恰好是前8个Fibonacci 数，它们的Huffman 编码是什么？将结果推广到n 个字符的频率分布恰好是前n 个Fibonacci 数的情形。

贪心算法练习题贪心算法1.喷水装置（一）描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入第一行m表示有m组测试数据每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出输出所用装置的个数样例输入252 3.2 4 4.5 6101 2 3 1 2 1.2 3 1.1 1 2样例输出25根据日常生活知道，选择半径越大的装置，所用的数目越少。

因此，可以先对半径排序，然后选择半径大的。

另外，当装置刚好喷到矩形的顶点时，数目最少。

此时只要装置的有效喷水距离的和不小于20时，输出此时的装置数目即可。

2.喷水装置（二）时间限制：3000 ms | 内存限制：65535 KB难度：4描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。

请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入第一行输入一个正整数N表示共有n次测试数据。

每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。

随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。

如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入22 8 61 14 52 10 64 56 5样例输出123.会场安排问题描述学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。

贪⼼算法（4）：作业排序问题上⼀堂课程，我们学习了如何选择活动，使得在不发⽣冲突的前提下，能参与尽可能多的活动，这⾥没有考虑到不同的活动是否会带来不同的收益，假设它们的收益是⼀样的。

现在我们把问题修改下：有⼀系列作业，每个作业必须在各⾃的截⽌时间点之前完成，并且已知完成每个⼯作需要花费的时间以及带来的收益。

为了简单起见，假设完成每个⼯作都需要相等的单位时间，这样作业的截⾄时间点也就是单位时间的倍数。

再假设⼀次只能安排⼀个作业，完成⼀个作业后才能继续下⼀个作业。

问：如何选择作业并安排次序使它们能带来的总收益为最⼤？我们⽤例⼦A来说明。

【输⼊】有4个作业a,b,c,d。

它们各⾃的截⽌时间和能带来的收益如下：【输出】请找出⼀种能带来最⼤收益的作业执⾏次序。

在例⼦中，下列作业次序能带来最⼤的收益：｛c, a｝完成作业c，能带来的收益是40；因为做作业c，截⽌时间为1，它必须安排在0-1之间执⾏。

这样已经错过了b或d的截⽌时间点（1），因此⽆法再选择b或d，只能选择作业a，a的截⾄时间点为4，来得及完成。

做作业a的收益是20，因此完成作业c和a能带来的总收益是 40+20=60。

⽽选择其他次序的作业，都⽆法超过收益60。

参见下⾯的动图：我们再看⼀个例⼦B【输⼊】有5个作业a,b,c,d,e。

它们各⾃的截⽌时间和能带来的收益如下：请你选择和安排能获取最⼤收益的作业次序，先不给出答案，请你先思考，如何解答，然后再继续阅读。

算法分析⼀个简单粗暴的算法就是⽣成给定作业集合的所有⼦集，并检查每⼀个⼦集以确定该⼦集中作业的可⾏性，然后找出哪个可⾏⼦集可以产⽣最⼤收益。

这是⼀个典型的贪⼼算法。

算法思路如下：1）根据收益递减顺序对所有作业进⾏排序。

2）将结果序列初始化，并把已排序作业中的第⼀个作业加⼊3）依次按下⾯的规则处理剩余的n-1个作业如果把当前作业加⼊结果序列，不会错过它的截⽌时间，那么把它加⼊结果序列；否则忽略当前的作业。

算法作业——第4章贪⼼算法第4章 贪⼼算法 习题贪⼼算法 习题第4章【+】阅读、掌握课本经典范例代码的实现：（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最⼩⽣成树；（6）多机调度问题。

【第1题】单项选择题（1）下⾯是贪⼼算法的基本要素的是（ ）。

A.重叠⼦问题B.构造最优解C.贪⼼选择性质D.定义最优解（2）下⾯问题（ ）不能使⽤贪⼼法解决。

A.单源最短路径问题B. n皇后问题C.最⼩花费⽣成树问题D.背包问题（3）采⽤贪⼼算法的最优装载问题的主要计算量在于将集装箱依其重量从⼩到⼤排序，故算法的时间复杂度为（ ）。

A.O(n)B.O(n2)C.O(n3)D.O(nlog2n)（4）关于0-1背包问题以下描述正确的是（ ）。

A.可以使⽤贪⼼算法找到最优解B.能找到多项式时间的有效算法C.使⽤教材介绍的动态规划⽅法可求解任意0-1背包问题D.对于同⼀背包与相同的物品，做背包问题取得的总价值⼀定⼤于等于做0-1背包问题（5）⼀棵哈夫曼树共有215个结点，对其进⾏哈夫曼编码，共能得到（ ）个不同的码字。

A.107B.108C.214D.215【第2题】求解哈夫曼编码中如何体现贪⼼思路？【第3题】举反例证明0-1背包问题若使⽤的算法是按照vi/wi的⾮递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装⼊背包，则此⽅法不⼀定能得到最优解（此题说明0-1背包问题与背包问题的不同）。

*【第4题】给定数轴X上n个不同点的集合，{x1,x2,...,xn}，其中，x1<x2<...<xn。

现在⽤若⼲个长度为1的闭区间来覆盖这些点。

设计⼀个算法找到最少的闭区间个数和位置。

证明算法的正确性并估计算法的时间复杂度。

【第5题】（编程）求解硬币问题。

有1分、2分、5分、10分、50分和100分的硬币各若⼲枚，现在要⽤这些硬币来⽀付W元，最少需要多少枚硬币。

说明：⽤结构体数组A存放硬币数据，A[i].v存放硬币i的⾯额，A[i].c存放硬币i的枚数。

第四章-贪⼼算法（模拟试题）计算机与信息科学学院2010-2011学年第2学期模拟试卷计算机算法设计与分析—第四章.贪⼼算法本卷满分100分完卷时间120分钟⼀. 简答题（每⼩题2分，共20分）1. 当⼀个问题具有且具有时可⽤贪⼼算法，如最⼩⽣成树问题（背包问题，活动安排问题等）。

2. 在动态规划可⾏的基础上满⾜才能⽤贪⼼。

3. 贪⼼算法总是作出在当前看来最好的选择。

也就是说贪⼼算法并不从整体最优考虑，它所作出的选择只是在某种意义上的选择。

4. 动态规划算法通常以的⽅式解各⼦问题，⽽贪⼼算法则通常以的⽅式进⾏，以迭代的⽅式作出相继的贪⼼选择，每作⼀次贪⼼选择就将所求问题简化为规模更⼩的⼦问题5. 贪⼼算法和动态规划算法都要求问题具有性质，这是2类算法的⼀个共同点。

6. 当⼀个问题的最优解包含其⼦问题的最优解时，称此问题具有。

7. 对于具有n 个顶点和e 条边的带权有向图，如果⽤带权邻接矩阵表⽰这个图，那么Dijkstra 算法的主循环体需要时间。

这个循环需要执⾏n-1次，所以完成循环需要时间。

算法的其余部分所需要时间不超过。

8. 0-1背包问题指：给定n 种物品和⼀个背包。

物品i 的重量是Wi ，其价值为Vi ，背包的容量为C 。

应如何选择装⼊背包的物品，使得装⼊背包中物品的最⼤。

9. 有⼀批集装箱要装上⼀艘载重量为c 的轮船。

其中集装箱i 的重量为Wi 。

最优装载问题要求确定在不受限制的情况下，将装上轮船。

10. 多机调度问题要求给出⼀种作业调度⽅案，使所给的n 个作业在由m 台机器加⼯处理完成。

⼆. 综合题（1-6题每题7分，7-8题每题9分，共60分）1. 有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25,12)，背包容量为10。

试设计3种贪⼼策略,并给出在每种贪⼼策略下背包问题的解。

)(n O2. 使⽤prim算法构造出如下图G的⼀棵最⼩⽣成树。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=63. 设有n项独⽴的作业{1,2,…, n},由m台相同的机器加⼯处理。