ACM课件!!(lecture_06)贪心算法

今年暑假不AC（2037）
• • Input 输入数据包含多个测试实 例，每个测试实例的第一 行只有一个整数 n(n<=100)，表示你喜欢 看的节目的总数，然后是n 行数据，每行包括两个数 据Ti_s,Ti_e (1<=i<=n)， 分别表示第i个节目的开始 和结束时间，为了简化问 题，每个时间都用一个正 整数表示。n=0表示输入 结束，不做处理。 Output 对于每个测试实例，输出 能完整看到的电视节目的 个数，每个测试实例的输 出占一行。 Sample Input 12 13 34 07 38 15 19 15 20 10 15 8 18 6 12 5 10 4 14 29 0 Sample Output 5
附:参考源码(HDOJ-1050)
#include <iostream> using namespace std; int main() { int t,i,j,N,P[200]; int s,d,temp,k,min; cin>>t; for(i=0;i<t;i++) { for(j=0;j<200;j++) P[j]=0; cin>>N; for(j=0;j<N;j++) { cin>>s>>d; s=(s-1)/2; d=(d-1)/2; } if(s>d) { temp=s; s=d; d=temp; } for(k=s;k<=d;k++) P[k]++; } min=-1; for(j=0;j<200;j++) if(P[j]>min) min=P[j]; cout<<min*10<<endl; } return 0;

– 从全局看来，运用贪心策略解决的问题在 程序的运行过程中无回溯过程
教学进度
背包问题
计算机科学与工程系
• 给定n种物品和一个背包。物品i的重量是 Wi，其价值为Vi，背包的容量为C。在选 择物品i装入背包时，可以选择物品i的一部 分，而不一定要全部装入背包，1≤i≤n。 应如何选择装入背包的物品，使得装入背包 中物品的总价值最大?
教学进度
计算机科学与工程系
• 贪心算法并不总能求得问题的整体最优 解。但对于活动安排问题，贪心算法 GreedySelector却总能求得的整体最 优解，即它最终所确定的相容活动集合 A的规模最大。
教学进度
贪心算法的基本要素
• 最优子结构性质 • 贪心选择性质
计算机科学与工程系
教学进度
最优子结构性质
教学进度
计算机科学与工程系
• 怎样对这n个活动进行安排才能 令最多的活动可以使用资源？
教学进度
计算机科学与工程系
• 活动安排问题也就是要在所给 的活动集合中选出最大的相容 活动子集合
教学进度
计算机科学与工程系
教学进度
计算机科学与工程系
• 思路：按照结束时间递增序列将活动排 序，使得f1<=f2<=…<=fn
• void GreedySelector(int n, Type s[], Type f[], bool A[])
•{
•
A[1]=true;
•
int j=1;
•
for (int i=2;i<=n;i++) {
各活动的起始时间和结 束时间存储于数组s和f 中且按结束时间的非减 序排列
•
if (s[i]>=f[j]) { A[i]=true; j=i; }

5
例8.2 一个买糖的孩子用1元钱买了不到1元钱的糖,售货 员找硬币时希望用最少个数的硬币。 售货员每增加一个硬币,使用的贪心规则是: 每次希望增加尽可能多的币值,又不能超出总数。 例如要找66c(分)。
● 假设硬币面值分别为：25c, 10c, 5c, 1c。
● 假设硬币面值分别为：20c, 16c, 10c, 1c。
3. MAKESET({v})
4. End for
5. T={}
6. While |T|<n-1
7. 令(x,y)为E中的下一条边
8. If FIND(x)≠FIND(y) then
heyichao@
26
9.
将(x,y)加入T
10.
UNION(x,y)
11. End if
12. End while
● 函数H-1(w)返回w在H中的位置 (注意堆由一个 数组H(1…n)来实现)。
heyichao@
18
● 运行时间主要取决于堆运算，这里共有n-1 个DELETEMIN运算，n-1个INSERT运算，最 多m-n+1个SIFTUP运算，每个堆运算用O(logn) 时间，得到总共需要O(mlogn)时间。
1. 对G的边以非降序权重排列。
2. 对于排序表中的每条边，如果现在把它放入T 不会形成回路的话，则把它加入到生成树T中；否 则将它丢弃。
见例8.3
heyichao@
24
Kruskal算法的实现
为有效地实现此算法，我们需要某种机制来检 测加入边后是否构成回路。为此需要确定一种数 据结构，让它在算法的每个时刻来表示森林，并 且在向T中添加边时动态检测是否有回路生成。
7
● 假设V={1,2,…,n}并且s=1。这个问题可以用一 种称为Dijkstra算法的贪心技术来解决。初始时， 将顶点分为两个集合X={1}和Y={2,3,…,n}。X包 含的顶点集合：从源点到这些顶点的距离已经确 定。

int s,d,temp,k,min; cin>>t; for(i=0;i<t;i++)
{ for(j=0;j<200;j++) P[j]=0; cin>>N; for(j=0;j<N;j++) { cin>>s>>d; s=(s-1)/2; d=(d-1)/2;
if(s>d) { temp=s; s=d; d=temp; }
开（从哪儿断开呢？）。 如果N=k呢？
16 2020/12/3
三、HDOJ_1050 Moving Tables
题目链接 Sample Input
3 4 10 20 30 40 50 60 70 80 2 13 2 200 3 10 100 20 80 30 50
Sample Output
10 20 30
7 2020/12/3
特别说明：
若要用贪心算法求解某问题的整 体最优解，必须首先证明贪心思 想在该问题的应用结果就是最优 解！！
8 2020/12/3
用事实说话——
9 2020/12/3
实例分析
10 2020/12/3
一、事件序列问题
已知N个事件的发生时刻和结束时刻（见下表， 表中事件已按结束时刻升序排序）。一些在时间上 没有重叠的事件，可以构成一个事件序列，如事件 {2，8，10}。事件序列包含的事件数目，称为该事 件序列的长度。请编程找出一个最长的事件序列。
例如：M=5个整数1、3、4、8和11表示区间，要求 所用线段不超过N=3条 0 1 2 3 4 5 6 7 8 9 10 11
15 2020/12/3
算法分析：
如果N>=M，那么显然用M条长度为1的 线段可以覆盖住所有的区间，所求的线 段总长为M。