贪心思想的一点理解

根据acm训练计划，我被分配给大一新同学讲贪心专题，顺便看了几道经典的贪心例题，果然很多以前的东西都豁然开朗了，也有了一些新的理解，故随意记录一下。

一、定义

官方定义

  贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。   贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。   贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。   贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情况，选择最优的解，可能会导致辛普森悖论（Simpson’s Paradox），不一定出现最优的解。（摘自维基百科）

我的理解

  贪心的思想并不难理解 ——— 将一个问题分解成多个容易解决的子问题，让每一个子问题都最优，那么合起来得到的最终结果就是最优的，这样只要求出每个子问题的解，那么整个问题的解就不难得到了。但是这里有个问题：每个子问题最优，不一定最终结果就是最优的，这就是辛普森悖论。所以，贪心的最大难点就是如何证明贪心解就等于最优解，这也是贪心问题的上限很高的原因。   贪心的题不像其他大多数的题一样，要么有模板，要么有大致相同的解题步骤，贪心问题比较灵活，只能靠多刷题来培养“题感”。对于贪心问题，我一般的做法是，如果子问题的贪心策略显而易见（比如买东西选性价比最高的），那就大概推导一下证明。如果不容易找到贪心策略，则先随意地操作几次找找规律，而贪心问题大多数如果找不到策略可以尝试一下排序，当然这种思路只能算是一种“题感”，只能算是没有思路时的一种尝试。

二、例题

1.删数问题

题目链接

题目分析

自己尝试随意删去不同位置的数字然后比较一下，容易得出贪心策略是每一次应该删去当前数字的第一个上升序列的末尾数字。并且，在一个上升的序列中，删去最大的数肯定比删去其它的数要更好，如123456删去6肯定比删去12345任意一个数字使得数字更小（这个结论记住，后面有用。） 下面证明一下贪心解就是最优解： 假设某一时刻：

• 最优解为：S_1 = a_1 a_2…a_{i-1} a_{i+1} … a_{k+3}  即删去a_i
• 贪心解为：S_1 = a_1 a_2…a_{k-1} a_{k+1} a_{k+2} a_{k+3} 即删去a_k

若 i<ka_k前的数字是一个上升序列，则最优解删去的是上升序列中非末尾的一个数字，由上面的结论可知，最优解肯定大于贪心解，这与最优解的答案最小矛盾。 若 i>ka_k之前都一模一样，我们就看后面，假设最优解删去的是a_{k+1},则贪心解为a_{k+1} a_{k+2} a_{k+3},最优解为a_{k} a_{k+2} a_{k+3}，由于a_{k+1}<a_k

综上，只有最优解与贪心解相同时，策略才是最优的。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e3+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
char a[maxn];

int main(int argc, char const *argv[]) {
    int n, s;
    cin >> a >> s;
    n = strlen(a);
    while(s--) {
        int i = 0;
        while(i + 1 < n && a[i]<=a[i+1]) i++;
        for(int j = i+1; j < n; j++) a[j-1] = a[j];
        n--;
    }
    int i = 0;
    while(i < n && a[i] == '0') i++;
    if(i == n) puts("0");
    for(; i < n; i++) cout << a[i];
    return 0;
}

2.最少拦截系统

题目链接

题目分析

对于每个导弹，我们有两个拦截方式：用现有的导弹系统拦截或者用新的导弹系统拦截。在用现有的导弹系统拦截时，我们用贪心的思想，使用现有的可拦截高度大于导弹高度的最小的导弹系统。这就是此题的贪心策略，再次说明策略好找，最优性难证啊。

下面证明贪心策略的最优性，上一题我们用了矛盾法来证明最优性，这里我们用调整法来证明： 假设某一时刻前最优策略和贪心策略相同,如图所示

黑色表示现有每个导弹系统的所拦截的导弹序列（并不是越高代表当前系统可拦截高度越高，只是一种随意的画法），蓝色表示当前有一组序列在贪心和最优策略下接在了不同的位置（假设左边为贪心策略，右边为最优策略）。由贪心策略可知，a是大于x的最小的数，故 x<a<b 所以，我们可以将蓝色序列的贪心位置和最优位置互换使得当前状态下贪心转变成最优，以此类推，每当贪心和最优策略出现不同时，用这种调整的方法将贪心策略变成最优策略，最终，总体的贪心就是最优解。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int h[maxn];
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 0; i < n;i ++) {
        int x;
        cin >> x;
        int j = 0;
        while(j < cnt && h[j] < x) j++;
        if(j >= cnt) h[cnt++] = x;
        else h[j] = x;
    }
    cout << cnt << endl;
    return 0;
}

3.Puzzle From the Future（ CF #696 A题）

题目链接

题意

有两个01序列a b，先将a和b不进位相加得到c（例如010110 + 110101 = 120211）,再将c连续相同的数字用一个数字代替（例如1112200 = 120），将其表示成十进制数得到d，故（102>21 , 012<101, 021=21）,现在告诉你a，让你求b使得d尽量大。

题目分析

要d尽量大就要使得c尽量长，即a+b后保证没有连续的长度，其次要使得每位数字尽量大，且位数越高的地方数字要尽可能的高，所有从最高位开始向后遍历a，b的第一位一定为1，然后根据上一位确定当前应该是1还是0（如果当前是1不会使得当前位和上一位数字一样就为1，否则为0），依次确定每一位即可得到b。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
string a,b;
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        b.clear();
        int n;
        cin >> n >> a;
        int past = a[0] - '0' + 1;
        b += '1';
        for(int i = 1; i  <n; i++) {
            if(past == a[i] - '0' + 1) {
                b += '0';
                past = a[i] - '0';
            }
            else {
                b += '1';
                past = a[i] - '0' + 1;
            }
        }
        cout << b << endl;
    }
    return 0;
}