贪心算法介绍

贪心算法总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。贪心算法正是“活在当下，看清楚眼前”的算法，从问题的初始解开始，一步歩地做出当前最好的选择，逐步逼近问题的目标，尽可能得到最优解；即使得不到最优解，也可以得到最优解的近似解。

当然，贪心算法在解决问题的策略上看似“目光短浅”，只根据当前已有的信息做出选择，而且一旦做出了选择，则不管将来有什么结果，都不会改变。换而言之，贪心算法并不是从整体最优来考虑的，它所做出的选择只是某种意义上的局部最优。对许多问题都可以使用贪心算法得到整体最优解或整体最优解的近似解。因此贪心算法在生活、生产中得到大量应用。

贪心本质

我们在遇到具体问题时，往往分不清对哪些问题可以用贪心算法，对哪些问题不可以用贪心算法。实际上，如果问题具有两个特性：贪心选择性质和最优子结构性质，则可以用贪心算法。

（1）贪心选择性质。贪心选择性质指原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的、但规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心算法解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后面贪心算法图解中得到深刻的体会。

（2）最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键。例如原问题S={a1,a2,…,ai,…,an}，通过贪心选择选出一个当前最优解{ai}之后，转化为求解子问题S-{ai}，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。

image.png

贪心算法的求解步骤如下。

（1）贪心策略。指确定贪心策略，选择当前看上去最好的一个。比如挑选苹果，如果你认为个头大的是最好的，那么每次都从苹果堆中拿一个最大的作为局部最优解，贪心策略就是选择当前最大的苹果。如果你认为最红的苹果是最好的，那么每次都从苹果堆中拿一个最红的，贪心策略就是选择当前最红的苹果。因此根据求解目标的不同，贪心策略也会不同。

（2）局部最优解。指根据贪心策略，一步步地得到局部最优解。比如第1次选一个最大的苹果放起来，记为a1；第2次再从剩下的苹果中选择一个最大的苹果放起来，记为a2，以此类推。

（3）全局最优解。指把所有的局部最优解都合成原问题的一个最优解{a1,a2……}。

最优装载问题

有一天，海盗们截获了一艘装满各种各样古董的货船，每件古董都价值连城，一旦打碎就失去了价值。虽然海盗船足够大，但载重为c，每件古董的重量为wi，海盗们绞尽脑汁要把尽可能多的宝贝装上海盗船，该怎么办呢？

  1. 问题分析
    根据问题描述可知，这是一个可以用贪心算法求解的最优装载问题，要求装载的物品尽可能多，而船的容量是固定的，那么优先把重量小的物品放进去，在容量固定的情况下，装的物品最多。可以采用重量最轻者先装的贪心选择策略，从局部最优达到全局最优，从而得到最优装载问题的最优解。

  2. 算法设计
    （1）当载重为定值c时，wi越小，可装载的古董数量n越大。依次选择最小重量的古董，直到不能装入为止。
    （2）把n个古董的重量从小到大（非递减）排序，然后根据贪心策略尽可能多地选出前i个古董，直到不能继续装入为止。此时装入的古董数量就达到全局最优解。

  3. 完美图解
    每个古董的重量都如下表所示，海盗船的载重c为30，那么在不打碎古董又不超过载重的情况下，怎样装入最多的古董？

image.png
因为贪心策略是每次都选择重量最小的古董装入海盗船，因此可以按照古董的重量非递减排序，排序后如下表所示。
image.png
按照贪心策略，每次都选择重量最小的古董装入。
• i=0：选择排序后的第1个古董装入，装入重量tmp=2，不超过载重30，ans=1。
• i=1：选择排序后的第2个古董装入，装入重量tmp=2+3=5，不超过载重30，ans=2。
• i=2：选择排序后的第3个古董装入，装入重量tmp=5+4=9，不超过载重30，ans=3。
• i=3：选择排序后的第4个古董装入，装入重量tmp=9+5=14，不超过载重30，ans=4。
• i=4：选择排序后的第5个古董装入，装入重量tmp=14+7=21，不超过载重30，ans=5。
• i=5：选择排序后的第6个古董装入，装入重量tmp=21+10=31，超过载重30，算法结束。
即装入古董的个数为5（ans=5）个。

算法实现

根据算法设计描述，可以用一维数组w[]存储古董的重量。
（1）按重量排序。可以利用C++中的排序函数sort，对古董的重量从小到大（非递减）排序。要使用此函数，只需引入头文件：

  1. #include <algorithm>

排序函数如下：
image.png
在本例中，只需要调用sort函数对古董的重量从小到大排序即可：sort(w,w+n)。

（2）按照贪心策略找最优解。首先用变量ans记录已经装载的古董个数，tmp代表装载到船上的古董的重量，将两个变量都初始化为0；然后在按照重量从小到大排序的基础上，依次检查每个古董，使tmp加上该古董的重量，如果其结果小于或等于载重c，则令ans++；否则退出。
image.png

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. #define DEBUG true
  6. /**
  7.  * 有一天，海盗们截获了一艘装满各种各样古董的货船，每件古董都价值连城，一旦打碎就失去了价值。
  8.  * 虽然海盗船足够大，但载重为c，每件古董的重量为wi，海盗们绞尽脑汁要把尽可能多的宝贝装上海盗船，
  9.  * 该怎么办呢？
  10.  */
  12. void solution()
  13. {
  14.     double tmp = 0.0;
  15.     int ans = 0;
  16.     int c = 30;
  17.     int w[] = {4, 10, 7, 11, 3, 5, 15, 2};
  18.     int n = sizeof(w) / sizeof(*w);
  19.     sort(w, w + n);
  20.     for (int i = 0; i < n; i++)
  21.     {
  22.         tmp += w[i];
  23.         if (tmp < c)
  24.         {
  25.             ans++;
  26.         }
  27.         else
  28.         {
  29.             break;
  30.         }
  31.     }
  32.     cout << ans << endl;
  33. }
  35. void solution1()
  36. {
  37.     const int N = 1000;
  38.     double w[N], c; //古董的重量数组
  39.     int n, m;
  40.     cin >> m;
  41.     while (m--)
  42.     { //m个测试用例
  43.         if (DEBUG)
  44.         {
  45.             cout << "please input Volume of ship:" << endl;
  46.             cin >> c;
  47.             cout << "please input Number of antiques:" << endl;
  48.             cin >> n;
  49.         } else {
  50.             cin >> c >> n;
  51.         }
  53.         for (int i = 0; i < n; i++)
  54.         {
  55.             cin >> w[i]; //输入每个物品重量
  56.         }
  57.         sort(w, w + n); //按古董重量升序排序
  58.         double tmp = 0.0;
  59.         int ans = 0; // tmp为已装载到船上的古董重量，ans为已装载的古董个数
  60.         for (int i = 0; i < n; i++)
  61.         {
  62.             tmp += w[i];
  63.             if (tmp <= c)
  64.                 ans++;
  65.             else
  66.                 break;
  67.         }
  68.         cout << ans << endl;
  69.     }
  70. }
  72. int main(int argc, char const *argv[])
  73. {
  75.     (void)argc;
  76.     (void)argv;
  77.     // solution();
  78.     solution1();
  79.     return 0;
  80. }

算法分析时间复杂度：

按古董重量排序并调用sort函数，其平均时间复杂度为O(nlogn)，输入和贪心策略求解的两个for语句的时间复杂度均为O(n)，因此总时间复杂度为O(nlogn)。空间复杂度：在程序中使用了tmp、ans等辅助变量，空间复杂度为O(1)。

引用

[引用]算法训练营：海量图解+竞赛刷题（入门篇）
[代码地址]代码地址