算法-贪心

贪心算法
1
信息学竞赛课堂
贪心算法
2
贪心法
实际生活中，经常需要求一些问题的“可行解”和“最优解”，这就是所谓
的“最优化”问题。
一般来说，每个最优化问题都包含一组“限制条件”和一个“目标函数”，
符合限制条件的问题求解方案称为可行解，使目标函数取得最佳值（最大或最小）
的可行解称为最优解。
求解最优化问题的算法很多，例如穷举、搜索、动态规划等。贪心法也是求
解这类问题的一种常用方法。
信息学竞赛课堂
贪心算法
3
1. 贪心法的基本思想
贪心法是从问题的某个初始解出发，采用逐步构造最优解的方法，向给定的
目标前进。在每一个局部阶段，都做一个“看上去”最优的决策，并期望通过每
一次所做的局部最优选择产生出一个全局最优解。做出贪心决策的依据称为“贪
心策略”。要注意的是，贪心策略一旦做出，就不可再更改。
与递推不同的是，贪心严格意义上说只是一种策略或方法，而不是算法。推
进的每一步不是依据某一个固定的递推式，而是做一个“当时看似最佳”的贪心
选择（操作），不断将问题归纳为更小的相似子问题。所以，归纳、分析、选择
正确合适的贪心策略，是解决贪心问题的关键。
信息学竞赛课堂
贪心算法
4
贪心算法在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优解
出发来考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能
得到整体最优解，但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似
解。
贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每个子问题求解，得到每个子问题的局部最优解。
4.把每个子问题的局部最优解合成为原来问题的一个解。
实现该算法的过程：
从问题的某一初始状态出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
信息学竞赛课堂
贪心算法
5
问题描述：
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C 应如
何选择装入背包的物品 使得装入背包中物品的总价值最大? 这里，在选择物品i装
入背包时，可以选择物品i的一部分，而不一定要全部装入背包，不能重复装载。
小数背包问题
信息学竞赛课堂
贪心算法
6
现在有三种贪心策略：
1)按照价值最大贪心，是目标函数增长最快的，但是背包容量却可能消耗的太快，使得装
入背包的物品个数减少，从而不能保证目标函数达到最大值。
2)按照重量最小贪心，使得背包增长最慢，很显然，重量和价值没有关系，这也无法保证
目标函数达到最大值。
3)按照价值率（价值除以质量），使得单位重量价值增长最快。保证了价值和重量，是最
优解。
信息学竞赛课堂
贪心算法
7
假定n=3, C=20, v=(25, 24, 15), w= (18, 15, 10)，列举4个可行解：
也就是说，如果我们按照价值最大贪心，得到的解就是2；如果按照重量最小贪心，得
到解则是3，而最优解是4；
x1 x2 x3 Σwixi Σvixi
1 1/2 1/3 1/4 16.50 24.50 
2 1 2/15 0 20.00 28.20 
3 0 2/3 1 20.00 31.00 
4 0 1 1/2 20.00 31.50 
信息学竞赛课堂
贪心算法
8
问题描述：
有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。
现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最
小。输出这个最小值。
输入格式：
第一行共一个整数 V，表示箱子容量。
第二行共一个整数 n，表示物品总数。
接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。
输出格式：
共一行一个整数，表示箱子最小剩余空间。
说明/提示：
对于 100% 数据，满足 0<n≤30，1≤V≤20000。
装箱问题
输入样例：
24
6
8
3
12
7
9
7
输出样例：
0
#include<iostream>
using namespace std;
int n,m,f[20005],w[35];
int main(){ 
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>w[i]; 
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){ 
if(f[j]<f[j-w[i]]+w[i]){
f[j]=f[j-w[i]]+w[i];
}
}
}
cout<<m-f[m];
return 0; 
}
9
信息学竞赛课堂
贪心算法
10
问题描述：
有若干个体积为V（V<=10000）的箱子，有n(n<=1000)个物品，v0
,v1
,v2… …vn ，
（ vi <= V） 。要求将所有的物品都装入箱子里，使打开的箱子尽可能的少，输
出打开的箱子数。
输入格式：
第一行共2个整数n和 V，表示物品的个数和箱子容量。
第二行共n个整数 ，表示每个物品的体积。
输出格式：
输出一个整数，表示打开的箱子总个数。
新装箱问题
输入样例：
3 100
10 20 80
输出样例：
2
设置贪心准则
1、将所有的物品按照体积降序排列
2、每次取出一个物品（为当前未装箱的体积最大的），遍历所有已经打开的箱子，尝试
将该物品装入其中一个箱子
3、如果都装不下，就打开一个新箱子装入物品
11
12
#include<iostream>
#include<algorithm>
using namespace std;
int n,V,v[1005],r[1005],ans;
bool cmp(int a, int b) {
return a>b;
}
int main() {
cin>>n>>V; 
for(int i=1; i<=n; i++) {
cin>>v[i];
r[i]=V; 
}
sort(v+1, v+n+1, cmp); 
for(int i=1; i<=n; i++) { 
for(int j=1; j<=n; j++) { 
if(v[i]<=r[j]){ 
r[j]-=v[i];
break;
}
}
}
for(int i=1; i<=n; i++){ 
if(r[i]<V) ans++;
}
cout<<ans;
return 0; 
}
13
经典硬币问题
某人带着3种面值的硬币去购物，有1元、2元、5元的，硬币数量不限；
他需要支付M元，问怎么支付，才能使硬币数量最少？
#include <iostream>
using namespace std;
#define NUM 3
const int Value[NUM] = {5, 2, 1};
int main(){ 
int i, money;
int ans[NUM]={0};
cin >> money;
for(i= 0; i < NUM; i++){ //求每种硬币的数量
ans[i] = money/Value[i];
money = money - ans[i]*Value[i];
}
for(i= 0; i < NUM; i++)
cout<<Value[i]<<"元硬币数："<<ans[i]<<endl;
return 0;
}
经典硬币问题
虽然每一步选硬币的操作，并没有从整体最优来考虑，而是只在当前步骤选取了局部最优，
但是结果是全局最优的。然而，局部最优并不总是能导致全局最优。
硬币问题用贪心法，一定能得到最优解吗？
14
经典硬币问题
在硬币问题中，如果改换一下参数，就不一定能得到最优解。
例如：硬币面值比较奇怪，是1、2、4、5、6元，支付9元，如果用贪心法，答案是6 + 2 + 
1，需要3个硬币，而最优的5 + 4只需要2个硬币。
所以，在硬币问题中，用贪心法是否能得到最优，跟硬币的面值有关。如果是1、2、5这
样的面值，贪心是有效的，而对于1、2、4、5、6这样的面值，贪心是无效的。
任意面值硬币问题的求解：动态规划
15
信息学竞赛课堂
贪心算法
16
矩阵内取数问题
两个例子：
1、可以贪心
在N行M列的正整数矩阵中，要求从每一行各选出一个数，使得选出的N个数的和最大。
2、不可以贪心
在一个N*M的矩阵中，每一个格子赋予一个数，规定每次移动只能向上或向右。现试找出
一条路径，使其从左下角至右上角所经过的权值之和最大。
3 4 6
1 2 10
信息学竞赛课堂
贪心算法
17
贪心算法的特点：
1、贪心选择
所谓贪心选择是指应用统一规则，将原问题变为一个相似的但规模更小的子问题，而
后的每一步都是当前看似最佳的选择，且这种选择只依赖于已作出的选择，不依赖于未作
出的选择。
2、最优子结构
执行算法时，每一次得到的结果虽然都是当前问题的最优解（即局部最优解），但只有满
足全局最优解包含局部最优解时，才能保证最终得到的结果是最优解。
信息学竞赛课堂
贪心算法
18
独木舟
【问题描述】
旅行社计划组织一个独木舟旅行。租用的独木舟都是一样的，最多乘两人，而且载重有一
个限度。现在要节约费用，所以要尽可能地租用最少的舟。本题的任务是读入独木舟的载
重量，参加旅行的人数以及每个人的体重，计算出所需要的独木舟数目。
【输入格式】
第 1 行是 w（100≤w≤200），表示每条独木舟最大的载重量。
第 2 行是正整数 n（1≤n≤30000），表示参加旅行的人数。
接下来的一行 n 个正整数 t i （5≤t i ≤w），表示每个人的重量。
【输出格式】
输出一行一个数，表示最少的独木舟数目。
【输入样例】
100
9
90
20
20
30
50
60
70
80
90
【输出样例】
6
信息学竞赛课堂
贪心算法
19
【分析1】
先将 n 个人按照体重 t[i] 从大到小排序。对于每个人 j，j 从 1 开始，如果前面已
租的独木舟无法承载他，那么就重新租一个。只要设置一个数组 ship，ship[i] 表
示第 i个独木舟还可以承载多重，初始值全部设置为 w，ship[i] 减去 t[j] ；如果
前面有多个独木舟可以承载他（某个 ship[k]，1≤k≤i，t[j]≤ship[k]），那么选择
第一个能承载的去载他就可以了，并且把 ship[k] 设置成 0。最后，只要输出 i 即
可。
信息学竞赛课堂
贪心算法
20
【分析2】
先按照人的体重排序。
先让最重的人上船——如果最重的人和最轻的人体重总和不超过船的承重，则他
们两个占用一条船。否则（因为假设最重的人的体重也不超过船的承重了），最
重的人单独占一条船。转变为(n – 1)或者(n – 2)的问题了。
关键在于这种贪心策略是不是正确的？
我们可以证明，这种策略可以得到最优解。
（1） 假设最重的人和最轻的人的体重和超过了船的承重，那么最优解中，显然
也是最重的人单独占一条船，所以这种情况下最优解和贪心策略是相同的。
信息学竞赛课堂
贪心算法
21
（2） 假设最重的人和最轻的人的体重和没超过船的承重。
2.1 如果最优解中，最重的人单独占用一条船，则可以把最轻的人也放上去，
这样最优解用的船数不增加。如果最轻的人占用一条船，同样我们可以把最重的
人放上去，最优解船数不增。
2.2 如果最优解中最重的人x和x’占用一只船(x, x’)，而最轻的人y和y’占用一只
船(y, y’)，我们换成(x, y) (x’,y’) 。(x, y)显然没超过船的承重——因为我们假设就
是如此。关键看(x’, y’)。x’ + y’<= x’ + x 因为(x’, x)没超重，所以(x’,y’)也合法。
所以换一下，最优解船数也不增。这样我们就证明了如果可能把最重的人和最轻
的人放在一条船上，不会影响最优解。反复应用这个策略，就可以把n降低为(n –
1)或者(n – 2)个人的规模，从而解决这个问题。
信息学竞赛课堂
贪心算法
22
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m, a[30005];
int main(){
scanf(“%d%d”,&m,&n); //m:每条船最大载重量 n:总共n个人
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int j=0,k=n-1,ans=0;
while(j<=k){
if(a[j]+a[k]<=m) {
j++;
}
k--,ans++;
}
printf("%d\n",ans);
return 0;
}
信息学竞赛课堂
贪心算法
23
#include<iostream>
#include<algorithm>
using namespace std;
long people[10000];
int main(){
int n,i,j,ans=0;
long weight;
cin>>weight; //这个表示船的重量
cin>>n; //这个表示人数
for(i=0;i<n;i++) cin>>people[i];
sort(people,people+n); 
for(i=0,j = n-1;i<=j;j--){ //从上往下遍历
if(people[i]+people[j]>weight){
ans++;
}else{
i++; ans++;
}
}
printf("%d",ans);
return 0;
}
思想：按从小到大先排序，然后第一个和最
后一个相加，如果结果比船的载重大，那么
就把指向最后一个的指针往前移动一个，第
一个不动，船数加一，然后第一个和倒数第
二个相加，如果比载重小，那么指向第一个
的指针往后移动一个，倒数第二个指针往前
移动，船数加一，以此类推。
信息学竞赛课堂
贪心算法
24
不相交的区间选择问题：
数轴上有n条开区间(ai
, bi
)，选择尽量多个区间，使这些 区间两两没有公共点。
首先明确一个问题：如果有两个区间x, y，区间x完全包含y。那么显然选x是不划
算的，因为x和y最多只能选一个，选x还不如选y，这样不仅区间数目不会减少，
而且给其他区间留出了更多的位置。这样，我们按照bi从小到大的顺序给区间排
序。
贪心策略：
一定要选第一个区间，也就是一定要选bi最小的那一个区间。选择了第一个区间
之后，可以排除所有与第一个区间相交的区间，然后在剩下的区间中再选择bi最
小的区间，因为这样可以给后面留下更大的空间，以此类推。
区间上的问题1
信息学竞赛课堂
贪心算法
25
约翰有N(1≤N≤50000)头牛，约翰的草地可以认为是一条直线．每只牛只喜欢在某
个特定的范围内吃草．第i头牛喜欢在区间(Si，Ei)吃草，1≤Si<Ei≤1,000,000,00.
奶牛们都很自私，他们不喜欢和其他奶牛共享自己喜欢吃草的领域，因此约翰要
保证任意两头牛都不会共享他们喜欢吃草的领域．如果奶牛i和奶牛j想要同时吃
草，那么要满足：Si>=Ej或者Ei≤Sj．约翰想知道在同一时刻，最多可以有多少
头奶牛同时吃草？
【输入格式】
第 1 行 1 个整数 n。
第 2 行到第 n 行每行两个数，表示Si和Ei，
之间用一个空格隔开。
【输出格式】
一行一个数，同时吃草的奶牛数。
自私的放牧
【输入样例】
5 
2 4 
1 12 
4 5 
7 10 
7 8 
【输出样例】
3
信息学竞赛课堂
贪心算法
26
选点问题：
数轴上有n个闭区间[ai
,bi
]。取尽量少的点，使得每个区间内都至少有一 个点（不
同区间内含的点可以是同一个）
先讨论区间包含的情况，由于小区间被满足时大区间一定也被满足。所以在 区间
包含的情况下，大区间不需要考虑。
把所有区间按b从小到大排序（b相同时可以根据题目决定是否需要取a大的）
贪心策略：在第一个区间最右边选点，然后排除被该点标志过的所有区间，然后
再在剩下的区间的第一个区间最右边选点，重复之前操作。
区间上的问题2
信息学竞赛课堂
贪心算法
27
种树
题目描述：一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地
区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每
个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间
最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以
T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少
的树的数量。
输入格式：第一行包含数据N，区域的个数(0<N≤30000)；第二行包含H，房子的数目
(0<H≤5000)；
下面的H行描述居民们的需要：
B E T，0<B≤E≤30000，T≤E-B+1。
输出格式：输出文件只有一行写有树的数目
输入样例：
9
4
1 4 2
4 6 2
8 9 2
3 5 2
输出样例：
5
信息学竞赛课堂
贪心算法
28
区间覆盖问题：
数轴上有n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定线 段[s,t]。
本题的突破口仍然是区间包含和排序扫描，不过可以进行一次预处理。每个区间
在[s,t]外的部分都可以预先被切掉，因为它们的存在是毫无意义的。在预处理后，
在相互包含的情况下，小区间显然不应该考虑。
按照左端点ai从小到大排序。如果区间1的起点不是<=s，无解（因为其他区间的
起点更大， 不可能覆盖到s点），否则选择起点在s左边的最长区间。选择该区间
[ai,bi]后，新的起点应该设置为bi，并且忽略所有区间在bi之前的部分，就像预处
理一样，然后选择起点在bi左边的最长区间，以此类推。
区间上的问题3
信息学竞赛课堂
贪心算法
29
喷水装置
题目描述：有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有
n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆
都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。
输入格式：第一行输入一个正整数N表示共有N次测试数据。每一组测试数据的第一行有
三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示
该喷水装置能覆盖的圆的半径。
输出格式：每组测试数据输出一个正整数，
表示共需要多少个喷水装置，每个输出单独
占一行。如果不存在一种能够把整个草坪湿
润的方案，请输出0。
输入样例：
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
输出样例：
1
2
信息学竞赛课堂
贪心算法
31
5、带限期和罚款的单位时间任务调度
【问题描述】
用n个任务，每个任务都需要1个时间单位执行，任务i的截止时间d[i](1<=di<=n)表示要求
任务i在时间d[i]结束时必须完成，误时惩罚w[i]表示若任务i未在时间d[i]结束之前完成，
将导致w[i]的罚款。确定所有任务的执行顺序，使得惩罚最少。
【思路点拨】
要使罚款最少，我们显然应尽量完成w[i]值较大的任务。
此时，我们可以将任务按w[i]从大到小排序，然后按照排好的顺序依次对任务进行安排。
安排的规则是：使处理任务i的时间既在d[i]之内，又尽量靠后；如果d[i]之内的时间都已
经排满，就放弃处理此项任务。
信息学竞赛课堂
贪心算法
32
题目描述：
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为
了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是
你的，接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规
定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣
去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都
很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只
是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，
当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!
信息学竞赛课堂
贪心算法
33
输入格式：
输入共4行。第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
输出格式：
输出仅1行。表示小伟能赢取最多的钱。
输入样例：
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出样例：
9950
信息学竞赛课堂
贪心算法
34
Poker Hands
【问题描述】
奶牛贝蒂和她的朋友们正在玩一种打牌游戏，一共有n堆牌，第i堆牌有ai张。贝
蒂可以从第i堆到第j堆里的每一堆中各抽取一张牌（要求从i到j之间没有空堆），
这算作出一次牌，问至少需要出多少次才能把所有堆都清空。
【输入格式】
第 1 行 1 个整数 n。
第 2 行为 n 个正整数，每两个数
之间用一个空格隔开。
【输出格式】
一行一个数，最少出牌次数。
【输入样例】
5 
2 4 1 2 3 
【输出样例】
6
信息学竞赛课堂
贪心算法
35
高低卡
【问题描述】
有 2N 张牌，它们的点数分别为 1到 2N 。Bessie 拿了其中的 N 张，Elsie 拿了剩
下的 N 张。Bessie 和 Elsie 会进行 K 轮游戏，在每轮游戏中，Bessie 和 Elsie 各
出一张牌。出了的牌不能收回。在前 N/2 轮中，谁的牌点数大谁就赢；在后 N/2 
轮中，谁的牌点数小谁就赢。已知 Elsie 每一轮会出什么牌，试求 Bessie 最多能
赢多少轮。 2≤N≤50000, 保证 N 是偶数。。
【输入格式】
第 1 行 1 个整数 n。
第 2 行为 n 个正整数，表示Elsie每一轮出的牌，
【输出格式】
一行一个数，表示Bessie赢的次数。
【输入样例】
4 
1 8 4 3
【输出样例】
2
THANKS