贪心算法

概念：把整个问题分为多个步骤，在每个步骤都选取当前步骤的最优方案，直到这个步骤结束，每一步都不考虑对后续步骤的影响，在后续步骤中不再改变前面的选择。

例题：最少硬币问题

题目描述：某人带着3种面值的硬币去购物，有1元、2元、5元的，硬币数量不限；他需要支付M元，问怎么支付，才能使硬币数量最少？

第一步应该先拿出面值最大的 5 元硬币，第二步拿出面值第二大的 2 元硬币，最后才拿出面值最小的 1 元硬币。在这个解决方案中，硬币数量总数是最少的

#include

using namespace std;

const int n = 3;

int coin[] = {1,2,5};

int main(){

int i, money;

int ans[n] = {0}; //记录每种硬币的数量

cin >> money; //输入钱数

for(i= n-1; i>=0; i--){ //求每种硬币的数量

ans[i] = money/coin[i];

money = money - ans[i]*coin[i];

}

for(i= n-1; i>=0; i--)

cout << coin[i]<<": "<

return 0;

}

能使用贪心法求解的问题，需要满足以下特征：

最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。也就是说，从局部最优能扩展到全局最优。贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。

贪心算法的几个题型：

1.区间调度问题：

题目描述：有很多电视节目，给出它们的起止时间。有的节目时间冲突。问能完整看完的电视节目最多有多少？

输入：输入数据包含多个测试实例，每个测试实例的第一行只有一个整数 n*(*n<=100)，表示节目总数，然后是 n 行数据，每行包括两个数据 s, e，分别表示第 i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

输出：对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

这里可以想到三种贪心策略

1.最早开始时间

2.最早结束时间

3.用时最少

第 2种策略是合理的，尽快终止一个活动，可以容纳更多的后续活动。

下面的图是例子，最优活动是 1、3、5，活动 2、4 与其它节目有冲突。

为什么它对呢 它符合最优子结构性质。选中的第 1个活动，它一定在某个最优解中；同理，选中的第 2 个活动、第 3 个活动……也同样在这个最优解中。 它符合贪心选择性质。算法的每一步都使用了相同的贪心策略

#include

using namespace std;

#define MAXN 100

struct record {

int s, e; //定义活动的起止时间： start, end

} r[MAXN];

bool cmp(const record& a, const record& b)

{ return a.e < b.e; }

int main(){

int n;

while(1){

cin >> n; //输入n个活动

if(n == 0) break; // n==0时结束

for(int i=0; i

cin >> r[i].s >> r[i].e;

sort(r, r + n, cmp); // 排序：按结束时间排序

int count = 0; //统计活动个数

int lastend = -1;

for(int i=0; i

if(r[i].s >= lastend) {//后一个起始时间 >= 前一个终止时间

count++;

lastend = r[i].e; //记录前一个活动终止时间

}

cout << count << endl; //输出活动个数

}

return 0;

}

区间覆盖问题

题目描述：给定一个长度为 n 的区间，再给出 m 条线段的左端点（起点）和右端点（终点）。问最少用多少条线段可以将整个区间完全覆盖

把每个线段按照左端点递增排序。设已经覆盖的区间是 [L, R][L,R] ，在剩下的线段中，找所有左端点小于等于 R，且右端点最大的线段，把这个线段加入到已覆盖区间里，并更新已覆盖区间的 [L, R][L,R] 值。重复步骤 2，直到区间全部覆盖。

图2 区间覆盖

大佬：图 2 中，所有线段已按左端点进行排序。于是首先选中线段 1，然后在 2 和 3 中，选中更长的 3 。而 4 和 5 由于不合要求，被跳过。最后的最优解是 1、3。

最优装载问题（普通背包问题）

题目描述：有 n 种药水，体积都是 V ，浓度不同。把它们混合起来，得到浓度不大于 w% 的药水。问怎么混合，才能得到最大体积的药水？注意一种药水要么全用，要么都不用，不能只取一部分。

解题思路：先对药水按浓度从小到大排序，药水的浓度不大于 w% 就加入，如果药水的浓度大于 w%，计算混合后总浓度，不大于 w% 就加入，否则结束判断。

多机调度问题

题目描述：设有 n 个独立的作业，由 m 台相同的机器进行加工。作业 i 的处理时间为 ti，每个作业可在任何一台机器上加工处理，但不能间断、拆分。要求给出一种作业调度方案，在尽可能短的时间内，由 m 台机器加工处理完成这 n 个作业。

求解多机调度问题的贪心策略是：最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器。让处理时间长的作业得到优先处理，从而在整体上获得尽可能短的处理时间。

如果 n<=m，需要的时间就是 n 个作业当中最长处理时间 t。如果 n>m，首先将 n 个作业按处理时间从大到小排序，然后按顺序把作业分配给空闲的机器。

推荐链接

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。