贪心算法简介

​ 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心算法的基本介绍

贪心算法的一般流程

Greedy(C)  //C是问题的输入集合即候选集合
{
    S={ };  //初始解集合为空集
    while (not solution(S))  //集合S没有构成问题的一个解
    {
       x=select(C);    //在候选集合C中做贪心选择
       if feasible(S, x)  //判断集合S中加入x后的解是否可行
          S=S+{x};
          C=C-{x};
    }
   return S;

贪心算法其实没有一个固定的流程，这点和KMP算法不一样，KMP算法是解决那种特定的问题，但是这个贪心算法是解决那一种问题，适合做出贪心选择的问题：

贪心选择的性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

对于那些不满足贪心选择的问题，我们不可以使用贪心算法来解决。

贪心算法存在的问题

  1. 不能保证求得的最后解是最佳的；

  2. 不能用来求最大或最小解问题；

  3. 只能求满足某些约束条件的可行解的范围。

贪心算法的例题

找零钱问题

假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。

思路分析

这个题目其实非常的简单，估计不学这个贪心算法都是非常容易搞定的，我们想要最少的硬币数，这里存不存在贪心选择呢？其实是很容易看出来的，我们的贪心选择就是尽量找大面额的硬币，能有多少找多少，毕竟有1元的硬币无需担心有早不开这种情况。

代码实现

#include <iostream>
#include <vector>
using std::vector;

vector<int> giveMoney(vector<int> m, int target) {
    int size = m.size();
    vector<int> num(size, 0);
    for (size_t i = 0; i < size; i++) {
        num[i] = target / m[i];
        target = target % m[i];
    }
    return num;
}

int main(int argc, char const *argv[]) {
    vector<int> num = {25, 10, 5, 1};
    int target = 99;
    vector<int> result = giveMoney(num, target);
    std::cout << target << "的找钱方案为：" << std::endl;
    for (size_t i = 0; i < result.size(); i++) {
        std::cout << result[i] << "枚面值为" << num[i] << "的硬币" << std::endl;
    }

    system("pause");
    return 0;
}

运行结果

99的找钱方案为：
3枚面值为25的硬币
2枚面值为10的硬币
0枚面值为 5的硬币
4枚面值为 1的硬币

这个是贪心算法的一个简单的例子，也无需做什么代码说明啦。

活动安排问题

设有n个活动的集合e={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si< fi。如果选择了活动i，则它在半开时间区间[si，fi]内占用资源。若区间[si，fi]与区间[sj，fj]不相交，则称活动i与活动j是相容的。也就是说，当si≥fi或sj≥fj时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

思路分析

其实我有点儿不想认为这个是贪心算法，但是你非要说这个是，我也没办法啦~

代码实现

#include <iostream>
#include <vector>
using std::vector;

vector<int> arrangeActivity(vector<int> start, vector<int> end) {
    int total = start.size();
    int endFlag = end[0];

    vector<int> result;
    result.push_back(0);
    for (size_t i = 0; i < total; i++) {
        if (start[i] > endFlag) {
            result.push_back(i);
            endFlag = end[i];
        }
    }

    return result;
}

int main(int argc, char const *argv[]) {
    vector<int> start = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
    // end数组是有序的
    vector<int> end = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};

    vector<int> result = arrangeActivity(start, end);

    for (size_t i = 0; i < result.size(); i++) {
        int index = result[i];
        std::cout << "开始时间：" << start[index] << " 结束时间：" << end[index]
                  << std::endl;
    }

    system("pause");
    return 0;
}

我简直不忍心说这个是。。。贪心算法啦~

背包问题

这个问题之前在动态规划的时候说过好像，不过那篇文章中好像没有谈及这个问题，不过我已经写完了好几道背包问题的例题了，下次可以再次写一个动态规划的文章。这里就使用动态规划里面的那个背包问题的题目吧。

0/1背包问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。

那么问题来了，这个题目可以使用贪心算法来做吗？也就是说这个题目存在贪心选择吗？

  • 贪心选择1 ： 和找零钱一样，选择最贵的往里面放。

    但是这个得到的是最优解吗？很容易得到反例，放入了贵的东西之后，剩余的空间可以会得不到利用。

  • 贪心选择2： 选择轻的往背包里面放。

    和上面的选择一样，这个也不能确保是最优解。

由此可见，使用贪心算法无法解决这个问题，还是安心的去选择动态规划吧。。。蛤蛤蛤

均分纸牌

有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4，4堆纸牌分别为：① 9 ② 8 ③ 17 ④ 6 移动三次可以达到目的：从③取4张牌放到④ 再从③区3张放到②然后从②去1张放到①。

思路分析

设a[i]为第I堆纸牌的张数（0<=I<=n），v为均分后每堆纸牌的张数，s为最小移动次数。
我们用贪心算法，按照从左到右的顺序移动纸牌。如第I堆的纸牌数不等于平均值，则移动一次（即s加1），分两种情况移动：

  • 若a[i]>v，则将a[i]-v张从第I堆移动到第I+1堆；
  • 若a[i]< v，则将v-a[i]张从第I+1堆移动到第I堆。为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第I堆移动到第I+1堆，移动后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.
  • 在从第I+1堆取出纸牌补充第I堆的过程中可能回出现第I+1堆的纸牌小于零的情况。
    如n=3，三堆指派数为1 2 27 ，这时v=10，为了使第一堆为10，要从第二堆移9张到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢？

我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数不变，因此此题使用贪心法可行的。

代码实现

#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;

int moveCards(vector<int>& cards) {
    int sum = 0;
    int count = 0;
    for (size_t i = 0; i < cards.size(); i++) {
        sum += cards[i];
    }
    int average = sum / cards.size();

    for (size_t i = 0; i < cards.size(); i++) {
        if (cards[i] != average) {
            cards[i] += average - cards[i];
            cards[i + 1] -= average - cards[i];
            count++;
        }
    }

    return count;
}

int main(int argc, char const* argv[]) {
    vector<int> cards = {2, 10, 18};
    int count = moveCards(cards);
    cout << "移动次数：" << count << endl;
    for (size_t i = 0; i < cards.size(); i++) {
        cout << "第" << i + 1 << "堆牌：" << cards[i] << endl;
    }

    system("pause");
    return 0;
}

代码说明：

乍一看以为这个题目是很难的题目，但是定睛一看，这不是一个沙雕题目吗？特别是有个这个贪心算法的思路之后，这个题目就变得尤为的弱智。

不过，关于这个题目，以及贪心算法还有特别多要注意的地方

  • 一是问题是否适合用贪心法求解。我们看一个找币的例子，如果一个货币系统有三种币值，面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，目前还没有一个通用的方法，在信息学竞赛中，需要凭个人的经验来判断。

  • 二是确定了可以用贪心算法之后，如何选择一个贪心标准，才能保证得到问题的最优解。在选择贪心标准时，我们要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的贪心标准所迷惑，如下面的例子。

这个题目找到了合理的贪心选择：如果不等于平均值的话就利用右面的牌堆变成平均值，即使出现了负数问题也不是很大。这个选择很好像，不过要说明这个就可以得到最优解，还是有一点难度的。

加入说这个移动不是限制在相邻的牌堆之间了，这个选择就肯定是一个错误的选择了。所以说贪心算法难，但是代码不是特别的难写，主要就贪心选择有没有选择正确。

最大整数

设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。

思路分析

这个题目我们想要使用贪心算法来做，那么我们就要选择一个正确的贪心选择，那么关于这个题目怎么做贪心选择呢？把大的数放在前面？ 78 123 -> 12378明显不对，把小的数放在前面？这同样都是不对的。对于两个整数 a和b我们要是ab > ba(这里不是乘法)，这样做其实有一个很简单的实现方式，就是利用字符串。和求整数的最大的位数相似(将整数转为字符串然后求得字符串的长度就是整数的长度)我们可以将整数a和b转为字符串然后比较a+b和b+a的大小。

代码实现

/**
 * 设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
 * 例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
 * 又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
 */

#include <iostream>
#include <string>
#include <vector>
using std::string;
using std::to_string;
using std::vector;
#include <sstream>
using std::stringstream;
// 也可以使用stringstream来将nums转为string
// 将int转为string可以使用stoi， long转为string可以使用stol 转为char*
// 就以atoi和atol吧

string maxNum(vector<int>& nums) {
    // string result = to_string(nums[0]);
    string result = "";
    stringstream ss;
    ss << nums[0];
    ss >> result;
    for (size_t i = 1; i < nums.size(); i++) {
        string plusNum = to_string(nums[i]);
        if (result + plusNum > plusNum + result) {
            result += plusNum;
        } else {
            result = plusNum + result;
        }
    }
    return result;
}

int main(int argc, char const* argv[]) {
    vector<int> nums = {78, 123, 93};
    for (auto val : nums) {
        std::cout << val << " ";
    }
    std::cout << "可以组成的最大的整数为：";
    std::cout << maxNum(nums) << std::endl;
    system("pause");
    return 0;
}

也是非常简单的代码不用做什么说明了。

总结

贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，(动态规划依赖于子问题的解) 因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。但是不是所有的问题都可以使用贪心算法来解决的，要注意贪心选择是否是正确的，不然太贪心了之后搞得自己人莫得了。贪心算法学了感觉还是有点儿懵，这个算法拓展性真的是太强了，完全就只是一个思路，怎么搞都依赖于你自己的想法。嘤嘤嘤~~

赏

一枚小菜鸡