什么是贪心算法？
贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。
这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。
贪心法则通常以自顶向下的方式做出一系列的贪心选择。
贪心算法的基本要素
（1）最优量度标准
是指可以根据该量度标准，实行多步决策进行求解，虽然在该量度意义下所做的这些选择是局部最优的，但最终得到的解却是全局最优的。
如何选择最优量度标准是使用贪心法求解问题的核心问题。
最优量度标准也称贪心选择性质，是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到（仅在当前状态下做出最好选择）。
（2）最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。
贪心算法的求解过程
（1）分解，将原问题分解为若干相互独立的阶段；
（2）求解，对于每个阶段求局部最优解，即进行贪心选择。在每个阶段，选择一旦做出就不可更改。做出贪心选择的依据称为贪心准则。贪心准则的制定是用贪心算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量的高低。
（3）合并，将各个阶段的解合并为原问题的一个可行解。
背包问题
1.问题描述
给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?
2.分析
根据题意分析：从1-n的wi(i属于1-n)的和应该小于等于C；我们的目标是让从1-n的vi(i属于1-n)的和取得MAX。目前看来，至少有三种看似合理的贪心策略：
（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。
（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗的慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。
（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。
如果我们应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。
那么我们如何确定最优量度标准？
选择价值最大的物品与选择重量最轻的物品是两个极端的情况，它们就像是一个区间的两端，在这个区间上一定存在着背包问题的最优解，但是我们不知道如何找到它，我们采取一个折中的思路，找到两方妥协的办法，因此我们采取选择单位价值最大的物品。
3.实例
例如，有3个物品，其重量分别是{20, 30, 10}，价值分别为{60, 120, 50}，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值。
