一、何为贪心算法
初识： 一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优解选择，从而得到全局最优的解决方案。 ——《算法导论》
理解： 说白了，贪心算法，顾名思义，它是一个“活在当下，只顾眼前”的算法。
问题特征： 贪心选择性质+最优子结构
①贪心选择：原问题局部最优解，可以通过整体最优解得到。应用同一规则，将原问题，变成一个相似但是问题规模更小的子问题。选择时候，都依赖于前一步已经做出的选择。
②最优子结构：原问题的最优解，包含子问题的最优解，称此问题具有最优子结构性质。如下图：
原问题S中选择出一个最优解ai,转化为求S-{ai}的问题了，原问题的S的最优解包含了S-{ai}的最优解，则说明该问题满足最优子结构性质。通俗的说：你儿子苦恼，你也跟着苦恼，如果他的问题解决了，那么你的问题也跟着解决了。
解决方案： 贪心策略+局部最优=全局最优
①贪心策略：根据问题不同，贪心策略也不同。例如：选苹果，“选最大的苹果？还是选最红的苹果？”
②局部最优：接上例子，选完最大的苹果后，下次又从剩下的堆里选“最大的苹果”。
⚠注意：
①一旦做出选择，不可以反悔。
②有可能得到的不是最优解，而是最优解的近似值。
③选择什么贪心策略，直接决定算法的好坏。
常见的贪心算法：
会议问题、最优装载问题、背包问题、最短路径问题、哈夫曼编码问题、最小生成树问题.....
二、最优装载问题
背景： 你是一名海盗，一天你开着你的海盗船，发现一艘载有大量古董的运输船。你肯定要去“搜集”古董。但是你海盗船只能载“30单位”的物件，并且你只能运输一次，那么你要“搜集”哪些古董，才能保证利益最大化呢？下面我们来看有那些物件：
古董：（假设每个物品价值相近）
| 古董|青花瓷 |玉盘 | 玉石|手镯 |金条 |丝绸 | 大鼎|琉璃盏|
|--|--|--|--|--|--|--|--|--|--|--|
| 重量（单位）| 5|3 | 10| 2| 7| 4| 14 |11 |
分析问题： “如何使得利益最大化”这个问题很明显满足贪心算法特征：贪心选择+最优子结构，贪心选择：选择一个最轻的以后，再在剩下的古董中选择最轻的。最优子结构：原问题的最优解，包含了子问题的最优解。
解决问题： 每次选择最轻的古董，直到海盗船装不下为止。
①排序：把古董由轻到重给排序好。
函数：sort(begin,end，comparison)
参数：（begin,end） 待排数组的首地址和尾地址comparison自己编写的函数，以适应不同的数据结构。
头文件 #include<algorithm>
| 古董|手镯 |玉盘 | 丝绸|青花瓷 |金条 |玉石 |琉璃盏 |大鼎|
|--|--|--|--|--|--|--|--|--|--|--|
| 重量（单位）| 2|3 | 4 | 5| 7| 10| 11 |14 |20|
②代码如下：
#include<iostream>
#include<algorithm>//sort的头文件
#include<string.h>
using namespace std;
#define NUM 8 //古董数量
#define MaxWeight 30//海盗船最大容量
typedef struct Antique
{
char name[10];
int weight;
}antique;
bool Comparison(antique a,antique b)
{
return a.weight < b.weight;
}
void ShowAntique(antique* objects,int len)
{
cout << "\n古董：\t";
for (int i = 0; i < len; ++i)
{
cout << (objects + i)->name << "\t";
}
cout << "\n重量：\t";
for (int i = 0; i < len; ++i)
{
cout << (objects + i)->weight << "\t";
}
}
int main()
{
antique objects[NUM] = {
{
"青花瓷",5} ,{
"玉盘",3}, {
"玉石",10} ,{
"手镯",2}, {
"金条",7} ,{
"丝绸",4},{
"大鼎",14} ,{
"琉璃盏",11}};
cout << "\n初始古董";
ShowAntique(objects,NUM);
cout << "\n排序后古董：";
sort(objects, objects + NUM, Comparison);
ShowAntique(objects,NUM);
antique MyBoat[NUM] ;//海盗船
int Myweight = 0;//海盗船的初始重量
int count = 0; //物件数量
while (Myweight<MaxWeight)
{
strcpy_s(MyBoat[count].name, objects[count].name);
MyBoat[count].weight = objects[count].weight;
Myweight += objects[count].weight;
if (Myweight > MaxWeight)
break;
count++;
}
cout << "\n拿上海盗船的古董：";
ShowAntique(MyBoat,count);
return 0;
}
③运行截图
