贪心思想及例题

贪心（greedy)思想：一个问题拆解成多个步骤，每个步骤采用最优的解法（叫局部最优），不考虑对别的步骤的影响。

最少硬币问题：

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

思路：根据生活常识，第一步应该先拿出面值最大的 5​ 元硬币，第二步拿出面值第二大的 2​ 元硬币，最后才拿出面值最小的 1​ 元硬币。在这个解决方案中，硬币数量总数是最少的。

#include<bits/stdc++.h>
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]<<": "<<ans[i]<<endl; //输出每种面值硬币的数量
    return 0;
}

 上面这个例子，每一步都采用局部最优，其结果也是全局最优。但局部最优并不总是能导致全局最优。如这个硬币问题，局部最优并不总会是全局最优。

1. 不能得到最优解的情形。例如，硬币面值比较奇怪，是 1、2、4、5、6元 。现在来支付 9 元，如果用贪心法，答案是 6 + 2 + 1，需要 3 个硬币，而最优的 5 + 4 只需要 2个硬币。
2. 算不出答案的情形。例如，如果有面值 1 元的硬币，能保证用贪心能得到一个解，如果没有 1 元硬币，常常得不到解。例如只有面值 2、3、5 元的硬币，支付 9 元，用贪心法无法得到解，但解是存在的：9 = 5 + 2 + 2。

在最少硬币问题中，是否能使用贪心法，跟硬币的面值有关。如果是 1、2​​​​​、5 这样的面值，贪心是有效的，而对于 1、2​​​​​​、4​​​​​、5​​​​、6​​​ 或者 2​​、3​、5 这样的面值，贪心是无效的。

一个题目如果用贪心无法求最优解，往往能用动态规划求最优解。这种题型的固定解法就是用动态规划。这里只说说贪心。如果一个题目可以用贪心求解，那么尽量用贪心。

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

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

贪心算法的关键在于如何 选择贪心策略。

所谓贪心策略，必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。另外，把贪心法用在“虽然不是最好，但是还不错，我表示满意！”的某些难解问题上，例如旅行商问题，是很难得到最优解的。但是用贪心法常常能得到不错的近似解。如果不一定非要求得最优解，那么贪心的结果，也是很不错的方案。 

活动安排问题（区间调度问题）

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

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

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

贪心策略有：

1. 最早开始时间
2. 最早结束时间
3. 用时最少  

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

算法步骤：

1. 把 n 个活动按结束时间排序。
2. 选择第一个结束的活动，并删除（或跳过）与它时间相冲突的活动。
3. 重复步骤 2​，直到活动为空。每次选择剩下的活动中最早结束的那个活动，并删除与它时间冲突的活动。