贪心算法 （又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
基本要素
编辑
贪心选择
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。
最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题 [2] 。
基本思路
编辑
思想
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加 算法 停止 [3] 。
过程
- 建立数学模型来描述问题；
- 把求解的问题分成若干个子问题；
- 对每一子问题求解，得到子问题的局部最优解；
- 把子问题的解局部最优解合成原来解问题的一个解。
算法特性
编辑
贪婪算法可解决的问题通常大部分都有如下的特性：
- 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
- 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
- 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
- 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
- 最后，目标函数给出解的值。
- 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
例题分析
编辑
0-1背包问题
有一个背包，背包容量是M=150kg。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。 它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
马踏棋盘
在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c–
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序：
#define N 8
void dfs( int x, int y, int count)
{
int i,tx,ty;
if (count>N*N)
{
output_solution();//输出一个解
return ;
}
for (i=0; i<8; i++)
{
tx=hn[i].x;//hn[]保存八个方位子结点
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);//递归调用
s[tx][ty]=0;
}
}
应用
编辑
如把3/7和13/23分别化为三个单位分数的和
【贪心算法】
设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：
步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b – a*q1）
步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r1)/b(q1+1）
步骤三：重复步骤2，直到分解完毕
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
以上其实是数学家 斐波那契 提出的一种求解埃及分数的贪心算法，准确的算法表述应该是这样的：
设某个真分数的分子为a，分母为b;
把b除以a的商部分加1后的值作为埃及分数的某一个分母c；
将a乘以c再减去b，作为新的a；
将b乘以c，得到新的b；
如果a大于1且能整除b，则最后一个分母为b/a；算法结束；
或者，如果a等于1，则，最后一个分母为b；算法结束；
否则重复上面的步骤。
备注：事实上，后面判断a是否大于1和a是否等于1的两个判断可以合在一起，及判断b%a是否等于0，最后一个分母为b/a，显然是正确的。
PHP代码：
class tanxin{
public $weight;
public $price;
public function __construct($weight=0,$price=0){
$this->weight=$weight;
$this->price=$price;
}
}
//生成数据
$n=10;
for ($i=1;$i<=$n;$i++){
$weight=rand(1,20);
$price=rand(1,10);
$x[$i]= new tanxin($weight,$price);
}
//输出结果
function display($x){
$len=count($x);
foreach ($x as $val){
echo $val->weight,’ ‘,$val->price;
echo ‘<br>’;
}
}
//按照价格和重量比排序
function tsort(&$x){
$len=count($x);
for ($i=1;$i<=$len;$i++)
{
for ($j=1;$j<=$len-$i;$j++)
{
$temp=$x[$j];
$res=$x[$j+1]->price/$x[$j+1]->weight;
$temres=$temp->price/$temp->weight;
if ($res>$temres){
$x[$j]=$x[$j+1];
$x[$j+1]=$temp;
}
}
}
}
//贪心算法
function tanxin($x,$totalweight=50){
$len=count($x);
$allprice=0;
for ($i=1;$i<=$len;$i++){
if ($x[$i]->weight>$totalweight) break ;
else {
$allprice+=$x[$i]->price;
$totalweight=$totalweight-$x[$i]->weight;
}
}
if ($i<$len) $allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);
return $allprice;
}
tsort($x);//按非递增次序排序
display($x);//显示
echo ‘0-1背包最优解为:’;
echo tanxin($x);
Java 源代码
package main;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class Main {
/**
* 测试
*/
public static void main(String[] args) {
// 1.随机构造一批任务
List< Pair < Integer >> inputList = new ArrayList<Pair<Integer>>();
Random rand = new Random();
for ( int n = 0; n < 20; ++n) {
Integer left = rand.nextInt(100);
Integer right = left + rand.nextInt(100) + 1;
Pair<Integer> pair = new Pair<Integer>(left, right);
inputList.add(pair);
}
// 将任务列表按结束时间排序（也就是根据right字段进行排序）
sortByRight(inputList);
printPairList(inputList);
// 执行算法
List<Pair<Integer>> outputList = algorithm(inputList);
System.out.println();
printPairList(outputList);
}
/**
* 贪心算法
*
* @paraminputList
* @return使数量最多的任务方案
*/
public static <T extends Comparable<T>> List<Pair<T>> algorithm(
List<Pair<T>> inputList) {
if ( null == inputList || inputList.size() == 0 || inputList.size() == 1) {
return inputList;
}
sortByRight(inputList);
List<Pair<T>> outputList = new ArrayList<Pair<T>>();
int last = 0;
outputList.add(inputList.get(last));
int intputSize = inputList.size();
for ( int m = 1; m < intputSize; ++m) {
Pair<T> nextPair = inputList.get(m);
T nextLeft = nextPair.getLeft();
Pair<T> lastOutPair = inputList.get(last);
T lastRight = lastOutPair.getRight();
int flag = nextLeft.compareTo(lastRight);
if (flag >= 0) {
outputList.add(nextPair);
last = m;
}
}
return outputList;
}
/**
* 对传入的List<Pair<T>>对象进行排序，使Pair根据right从小到大排序。
*
* @paraminputList
*/
private static <T extends Comparable<T>> void sortByRight(
List<Pair<T>> inputList) {
CompareByRight<T> comparator = new CompareByRight<T>();
Collections.sort(inputList, comparator);
}
/**
* 打印一个List<Pair<T>>对象。
*
* @paraminputList
*/
private static <T extends Comparable<T>> void printPairList(
List<Pair<T>> inputList) {
for (Pair<T> pair : inputList) {
System.out.println(pair.toString());
}
}
}
/**
* 根据Pair.right比较两个Pair。用于Conlections.sort()方法。
*
* @param<T>
*/
class CompareByRight<T extends Comparable<T>> implements Comparator<Pair<T>> {
/* @ Override */
public int compare(Pair<T> o1, Pair<T> o2) {
T r1 = o1.getRight();
T r2 = o2.getRight();
int flag = r1.compareTo(r2);
return flag;
}
}
/**
* 代表一个任务对象。有点装逼用模板来写了。left表示开始时间，right表示结束时间。
*
* @param<T>
*/
class Pair<T extends Comparable<T>> {
private T left;
private T right;
public Pair(T left, T right) {
this .left = left;
this .right = right;
}
@Override
public String toString() {
return “[left=” + left.toString() + ‘,’ + “right=” + right.toString()
+ ‘]’;
}
public T getLeft() {
return left;
}
public void setLeft(T left) {
this .left = left;
}
public T getRight() {
return right;
}
public void setRight(T right) {
this .right = right;
}
