贪心方法一般策略

贪心方法
能够得到某种量度意义下的最优解的分级处理方法。
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题
贪心问题关键：选取能够得到问题最优解的量度标准。
抽量化控制描述

背包问题

问题描述

目标函数：$\sum_{i=1}^n \ pw$i=1∑n​ pw
约束条件：$\sum_{i=1}^n \ wx\leq \ M$i=1∑n​ wx≤ M
可行解：满足上述条件的任一集合(解向量：x₁,x₂,…,x_n)
最优解：能够使目标函数取最大值的可行解（可能为多个）

贪心算法求解
度量标准的选择

1. 目标函数：每装入一件物品，就使背包获得最大可能的效益增量
   
   存在问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗，从而不能装入更多物品
2. 容量：让背包容量尽可能慢的消耗，从而可以尽量装入更多的物品
   处理规则：按物品重量的非降次序将物品装入到背包，如果正考虑的物品放不进去，则只取其中一部分装满背包
   
   存在问题：效益值没有得到最大增加
3. 最优：已装入物品的累计效益值
   影响背包效益值的因素：背包容量M&放入背包中的物品重量及其可能带来的效益值
   处理规则：按照物品单位效益值（p_i/w_i）的非增次序考虑
   
   背包问题的贪心算法代码
   伪代码：
   
   最优解证明
   证明提出：第三种策略为最优解
   证明基本思想：将此贪心解与任一最优解相比较。若两解相同，则是最优解。若两解不同，则找开始不同的第一个分量位置i，用比较方案xi替换最优解xi，证明最优解在分量代换前后总效益值没变。
   定理