记得刚开始学算法的时候，以为这个贪心算法是个固定一套的有模板算法，其实这个变化还是很灵活的
贪心算法在思想上简单、操作高效，省去了为找到最优解可能需要的穷举操作，但是不会求出问题的最优解，从而错过真正答案，比如：
找零钱：25分，20分，5分，1分 凑出41分，怎样搭配硬币个数最少
贪心算法的思路无非是对每一步或者每一个子问题取最优：
第一步： 取25分
第二步：25<41,取5
第三步：25+5<41,取5
第四步：25+5+5<41,取5
第五步：25+5+5+5<41,取1
第六步：41==41
所以取五个硬币，但由于每一步都局限与每一个子问题的最优解，所以，并不能保证整体有最优解（贪心算法是没有回溯的），最优解应该是3个硬币，即：
2个20加1个1分。
但是如果把20分改成10分，那么用贪心算法求解出来的就是最优解
贪心算法主要由三个步骤：
1.建立对问题精确描述的数学模型，包括定义最优解模型
2.将问题分解为一系列子问题，同时定义子问题的最优解结构
3.应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用字问题的局部最优解堆叠出全局的最优解
0-1背包问题：贪心算法
记得前面写过一篇动态规划的0-1背包问题，记得当时啃了挺久的，现在又要写贪心版的0-1背包问题，估计又要啃挺久了，本来脑子就不太适合搞算法，还是出于兴趣。但这篇可能没有具体代码，因为时间紧迫，毕设加考研 简单整理一下给自己看看
0-1背包问题：
有N件物品和一个承重为C的背包，每件物品的重量是wi，价值是pi，求解 将哪几件物品装入背包可这些物品在总重量总和不超过C的情况下价值总和最大。
背包问题（Knapsack Problem）是组合优化的NP完全问题的总称，如货箱装载问题，货船载物问题等，这个问题隐含了一个条件：每个物品只有一件，也就是限定每件物品只能选择1个或0个，因此又被称为0-1背包问题。
有一个背包，最多能承载C=150的物品，现在有编号为1-7的7个物品，重量分别是wi=[35,30,60,50,40,10,25]，价值分别是pi=[10,40,30,50,35,40,30]。
现在从这7个物品中选择一个或者多个装入背包，要求在物品总重量不超过C的前提下，所装入的物品总价值最高。
1.初步分析：两个条件：
1）wi和pi
2）C和N
2.进一步分析：
对于第一 个条件：
每个物品还需要一个状态用于标记是否已经被选择（贪心算法没有回溯，所以拿了就不能再考虑放回或者怎么样）
对于第二个条件：
背包问题包括两个属性，一个是可选物品列表，另一个是背包总的承重量
3.构建数学模型：
typedef struct{
int weight;
int price;
int status; //0:未选中；1:已选中；2：已经不可选
}OBJECT
typedef struct{
std::vector<OBJECT> objs;
int totalC;
}KNAPSACK_PROBLEM
4.确定子问题：
在背包承重还有C'的情况下，选择一个还没有被选择过的物品装入背包，每选择一次物品p[i]，都要调整背包承重量：
C' = C'-p[i].weight
直到不能再装入物品，或者所有物品都已经装入背包。
5.细分子问题：
那么如何选择物品呢？
1）根据物品价值选择，每次都选价格最高的物品：
4、2、6、5 总重量是130，总价值是165
2）根据物品重量选择，每次都选重量最轻的物品：
6、7、2、1、5 总重量是140，总价值是155
3）根据价值密度（si=pi/wi）
6、2、7、4、1 总重量是150，总价值是170
GreedyAlgo() 函数是贪心算法的主体结构，包括子问题的分解和选择策略的选择都在这个函数中。能够明显看出来这个算法使用了迭代法的算法模式，当然，这个算法主体的实现还可以使用递归法，正如函数所展示的那样，它可以作为此类问题的一个通用解决思路：
void GreedyAlgo(KNAPSACK_PROBLEM *problem,SELECT_POLICY spFunc){
int idx;
int ntc = 0;
// spFunc 每次选择最符合策略的那个物品，选后再检查
while（（idx = spFunc(problem->objs, problem->totalC - ntc)）!=-1）
{
//所选物品是否满足背包承重要求？
if((ntc + problem->objs[idx].weight) <= problem->totalC)
{
problem->objs[idx].status = 1;
ntc += problem->objs[idx].weight;
}
else {
//不能选这个物品了，做个标记后重新选 problem->objs[idx].status = 2;
}
}
PrintResult(problem->objs);
}
spFunc 参数是选择策略函数的接口，通过替换这个参数，可以实现上文提到的三种贪婪策略，分别得到各种贪婪策略下得到的解。以第一种策略为例，每次总是选择 price 最大的物品，可以这样实现：
int Choosefunc1(std::vector& objs,intc){
int index = -1; //-1表示背包容量已满
int mp = 0;
for(int i = 0; i < static_cast<int>(objs.size()); i++)
{
if((objs[i].status == 0) && (objs[i].price > mp))
{
mp = objs[i].price;
index = i;
}
}
return index;
}
看起来第三种策略取得了最好的结果，和动态规划方法得到的最优结果是一致的，但是实际上，这只是对这组数据的验证结果而已，如果换一组数据，结果可能完全相反。当然，对于一些能够证明贪婪策略得到的就是最优解的问题，应用贪婪法可以高效地求得结果，比如求最小生成树的 Prim 算法和 Kruskal 算法。
在大多数情况下，贪婪法受自身策略模式的限制，通常很难直接求解全局最优解问题，也很难用于多阶段决策问题。贪婪法只能得到比较接近最优解的近似最优解，但是作为一种启发式辅助方法在很多算法中都得到了广泛的应用，很多常用的算法在解决局部最优决策时，都会应用到贪婪法。比如 Dijkstra 的单源最短路径算法在从 dist 中选择当前最短距离的节点时，就是采用的贪婪法策略。事实上，在任何算法中，只要在某个阶段使用了只考虑局部最优情况的选择策略，都可以理解为使用了贪婪算法。
