最优装载贪心算法
1. 贪心算法及其应用
求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。
比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装100KG重量的袋子，怎么装才能使得袋子中的豆子价值最大？
我们首先看看这个问题是否符合贪心算法的使用场景？限制值是袋子100KG，期望值是袋子里面的价值最高。所以是符合的。那么我们尝试着应用下贪心算法的方法，每一个步骤都寻找当下的最优解，怎么做呢？
把仓库里面的每种豆子价值除以重量，得出每种豆子的单价，那么当下的最优解，肯定是尽可能最多地装单价最贵的，也就是先把20KG的黄豆都装上，然后再把30KG的绿豆都装上，再装50KG的红豆，那么此时正好装满袋子，总价值将是270元，这就是通过贪心算法求解的答案。
贪心算法的应用在这个问题上的求解是否是最优解需要一个很复杂的数学论证，我们不用那样，只要心里举几个例子，验证下是否比它更好即可，如果举不出例子，那么就可以认为这就是最优解了。
虽然贪心算法虽然在大部分实践场景中都能得到最优解，但是并不能保证一定是最优解。比如在如下的有向带权图中寻找从S到T的最短路径，那么答案肯定就是S->A->E->T，总代价为1+4+4=9；
然而，实际上的最短路径是S->B->D->T，总代价为6。
所以，不能所有这类问题都迷信贪心算法的求解，但其作为一种算法指导思想，还是很值得学习的。
除了以上袋子装豆子的问题之外，还有很多应用场景。这种问题能否使用贪心算法来解决的关键是你能否将问题转换为贪心算法适用的问题，即找到问题的限制值和期望值。
我们有m个糖果要分给n个孩子，n大于m，注定有的孩子不能分到糖果。其中，每个糖果的大小都不同，分别为S1,S2,S3...,Sm，每个孩子对糖果的需求也是不同的，为N1,N2,N3...,Nn，那么我们如何分糖果，才能尽可能满足最多数量孩子的需求？
这个问题中，限制值是糖果的数量m，期望值满足最多的孩子需求。对于每个孩子，能用小的糖果满足其需求，就不要用大的，避免浪费。所以我们可以给所有孩子的需求排个序，从需求最小的孩子开始，用刚好能满足他的糖果来分给他，以此来分完所有的糖果。
我们有1元、5元、10元、20元、50元、100元纸币各C1、C5、C10、C20、C50、C100张，现在要购买一个价值K元的东西，请问怎么才能适用最少的纸币？
这个问题应该不难，限制值是各个纸币的张数，期望值是适用最少的纸币。那么我们就先用面值最大的100元去付钱，当再加一张100元就超过K时，就更换小面额的，直至正好为K元。
对于n个区间[L1,R1],[L2,R2]...[Ln,Rn]，我们怎么从中选出尽可能多的区间，使它们不相交？
我们需要把这个问题转换为符合贪心算法特点的问题，假设这么多区间的最左端点是Lmin，最右端点是Rmax，那么问题就是在[Lmin,Rmax]中，选择尽可能多的区间往里面塞，并且保证它们不相交。这里，限制值就是区间[Lmin,Rmax]，期望值就是尽可能多的区间。
我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。
贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。
2. 装载问题的贪心选择性质如何证明
设箱子重量从小到大（x1,x2,...,xn），若集合A是最优装载问题的一个最优解。A中第一个箱子为k。若k=1，A就是一个满足贪心性质的最优解。假如当k>1，令B=A-{k}+{1},因为Wk>=W1,则B中的总重量小于等于A中的总重量，A是最优解，则B也是最优解，而B是选择以箱子1为开始的最优解。可知总存在以贪心选择开始的最优解。
3. 贪心算法的最优装载问题
void loading(W[],X[],c,n)
{
for(i=1,i<n,i++)
1.void loading(int W[],int X[],int c,int n)
2.没有定义i;
3.for（;;）是冒号，非逗号
4. 贪心算法的本质
1. 贪心法（Greedy Algorithm）定义
求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择；
贪心法就是这样的算法：它在每个决策点作出在当时看来最佳的选择，即总是遵循某种规则，做出局部最优的选择，以推导出全局最优解（局部最优解->全局最优解）
2. 对贪心法的深入理解
（1）原理：一种启发式策略，在每个决策点作出在当时看来最佳的选择
（2）求解最优化问题的两个关键要素：贪心选择性质+最优子结构
①贪心选择性质：进行选择时，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解；
②最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质
（3）解题关键：贪心策略的选择
贪心算法不是对所有问题都能得到整体最优解的，因此选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
（4）一般步骤：
①建立数学模型来描述最优化问题；
②把求解的最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解；
③证明做出贪心选择后：
1°原问题总是存在全局最优解，即贪心选择始终安全；
2°剩余子问题的局部最优解与贪心选择组合，即可得到原问题的全局最优解。
并完成2°
3. 贪心法与动态规划
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。
5. 如何证明最优装载问题具有贪心选择性质
设某种货币系统为(1,5,10,25)四种币值(单位:元)，要用最少的币数找出 n元钱，
问:能否用贪心算法进行求解，并证明。(不要求写算法) 参考解答:贪心性质(最大面额优先选最多)证明:
对 n<=25的情况，易由穷举得证。
当 n>25时，设 n=1*a1+5*a2+10*a3+25*a4
为了使 a1+a2+a3+a4最小，易知:
a1<5，若 a1>=5，可将 5个 1元兑换为 1个 5元，币数减少。
a2<2，若 a2>=2，可将 2个 5元兑换为 1个 10元，币数减少。
当 a2=0时，a3<3，若 a3>=3，可将 3个 10元兑换为 1个 5元和 1个 25元，币数减 少。
当 a2>0时，a3<2，若 a2>=2，可将 1个 5元和 2个 10元兑换为 1个 25元，币数减 少。
即，为了使 a1+a2+a3+a4最小，所使用的 1、5、10元币的币数的上限为: a1=4,a2=0,a3=2或 a1=4,a2=1,a3=1
则所使用的 1、5、10元币的币值上限为:
4*1+0*5+2*10=24或 4*1+1*5+1*10=19
均不超过 25，因此，为了使 a1+a2+a3+a4最小，应使 a4达到最大。贪心选择性质得 证。
最优子结构性质证明:
当 a4的值确定后，为了使 a1+a2+a3+a4达到最小，须使 a1+a2+a3达到最小，仍为同 型的最优问题。
6. 贪心算法——最优装载
•贪心算法的特点是每个阶段所作的选择都是局部最优的，它期望通过所作的局部最优选择产生出一个全局最优解。
贪心与动态规划： 与动态规划不同的是，贪心是 鼠目寸光 ；动态规划是 统揽全局 。
–动态规划：每个阶段产生的都是全局最优解
•第i阶段的“全局”： 问题空间为(a1, … , ai)
•第i阶段的“全局最优解”：问题空间为 (a1, … , ai)时的最优解
–贪心：每个阶段产生的都是局部最优解
•第i阶段的“局部”：问题空间为按照贪心策略中的优先级排好序的第i个输入ai
•第i阶段的“局部最优解”： ai
•贪心选择性质：所求问题的全局最优解可以通过一系列局部最优的选择（即贪心选择）来达到。
–这是贪心算法与动态规划算法的主要区别。
•最优子结构性质：当原问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。
最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征
首先证明该问题具有贪心选择性质和最优子结构性质
1.最轻者先装一定是整体最优解，满足贪心选择
2.该问题的子问题仍是最优解，满足最优子结构