第4章 贪心算法-2.

6
算法实现题4-5 程序存储问题
数据输入：
第一行是2 个正整数，分别表示文件个数n和磁带的长 度L。接下来的1 行中，有n个正整数，表示程序存放在磁 带上的长度。
结果输出: 最多可以存储的程序数。
输入示例
6 50
2 3 13 8 80 20 输出示例
5
i 012345
x 2 3 13 8 80 20 7
3
算法实现题4-5 程序存储问题
问题描述： 设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。
程序i存放在磁带上的长度是 li，1 ≤ i ≤ n。 程序存储问题要求确定这n 个程序在磁带上的一个
存储方案，使得能够在磁带上存储尽可能多的程序。 编程任务：
对于给定的n个程序存放在磁带上的长度，编程计 算磁带上最多可以存储的程序数。
532.00
10
算法实现题4-6 最优服务次序问题
double greedy( vector<int> x) {
int i,n=x.size(); sort(x.begin(),x.end()); for(i=1;i<n;++i)
x[i] += x[i-1]; double t=0; for(i=0;i<n;++i) t+=x[i]; t /= n;
算法实现题4-5 程序存储问题
int greedy( vector<int> x, int m){
int i=0, sum=0, n=x.size();
sort(x.begin(),x.end());
while(i
if(sum <= m) i++;

1算法设计与分析第4章贪心算法2学习要点理解贪心算法的概念掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异 理解贪心算法的一般理论3学习要点通过应用范例学习贪心设计策略（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；44背景Similar to dynamic programming. Used for optimization problems .Optimization problems typically go through a sequence of steps, with a set of choices at each step.For many optimization problems, usingdynamic programming to determine the best choices is overkill (过度的杀伤威力). 贪心算法: Simpler, more efficient5背景应用找钱四种硬币：1分，5分，1角，2角5分找六角3分，怎么给？排队时出现拥挤情况，如何做才能节省时间？6背景研究程卫芳,廖湘科,沈昌祥.有向传感器网络最大覆盖调度算法.软件学报,2009,20(4):975-984崔鹏,刘红静.测试集问题的集合覆盖贪心算法的深入近似.软件学报,2006,17(7):1494-1500刘勇,高宏,李建中.基于联合意义度量的Top-K 图模式挖掘.计算机学报,2010,2期:215-230 张海英,温玄,张田文.低信噪比多目标检测的贪心算法.计算机学报,2008,1期:142-1507贪心算法的基本要素贪心(Greedy)算法总是作出在当前看来最好的选择。

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

希望贪心算法得到的最终结果也是整体最优的。

11
4.2 贪心算法的基本要素 --贪心选择性质
贪心选择性质:指所求问题的整体最优解可以通过 一系列局部最优的选择，即贪心选择来达到。
与动态规划算法的区别： （1）是否依赖子问题 的解；（2）求解过程（自下向上还是自上向下）
判断问题是否所具此性质：对于一个具体问题， 要确定它是否具有贪心选择性质，必须证明每一步所作 的贪心选择最终导致问题的整体最优解。
12
4.2 贪心算法的基本要素 --最优子结构性质
当一个问题的最优解包含其子问题 的最优解时，称此问题具有最优子结构 性质。
13
4.2 贪心算法的基本要素
贪心算法与动态规划算法的差异
相同点：最优子结构性质 不同点：通过组合优化问题实例说明二者
差别。
14
4.2 贪心算法的基本要素
0-1背包问题：
第4章 贪心算法
1
• 学习要点 • 理解贪心算法的概念。 • 掌握贪心算法的基本要素 • （1）最优子结构性质 • （2）贪心选择性质 • 理解贪心算法与动态规划算法的差异 • 通过应用范例学习贪心设计策略。 • （1）活动安排问题； • （2）最优装载问题； • （3）单源最短路径； • （4）多机调度问题。
问题：要在所给的活动集合中选出最大的相容活动 子集合。
5
4.1 活动安排问题
下面给出解活动安排问题的贪心算法:
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[])
{ A[1]=true;
各活动的起始时间和结 束时间存储于数组s和f
问题描述
给定n种物品和一个背包。物品i的重量是Wi，其价值 为Vi，背包的容量为C。应如何选择装入背包的物品，使 得装入背包中物品的总价值最大?

最后加入2个1美分的硬币。
贪婪算法有种直觉的倾向，在找零钱时，应使找出 的硬币数目最少（至少是接近最少） 。
段旭良@四川农业大学 5025968@
引言

机器调度

现有n件任务和多台的机器，任务可在机器上处理。 每任务开始时间为si，完成时间fi ，si<fi 。

[si,fi]为处理任务i的时间范围。 任务i、j重叠指两个任务的时间范围区间重叠
段旭良@四川农业大学 5025968@
4.1 活动安排问题
/// <summary> 贪心算法活动安排</summary> /// <param name="s">开始时间</param> /// <param name="f">结束时间(非降序排列)</param> /// <param name="A">所选择的活动[true]</param> public static void GreedySelector(int[] s, int[] f, bool[] A) { A[0] = true; 各活动的起始时间和 int j = 0; 结束时间存储于数组s for (int i = 1; i < s.Length; i++) 和f中且按结束时间的 { if (s[i] >= f[j]) 非减序排列。 { A[i] = true; j = i; } else A[i] = false; } }

找到一组实数xi (1≤i≤n) ，使
x
i 1

n
s x
i 1
n