贪婪法（Greedy Algorithm）

贪婪法（Greedy Algorithm），又称贪心算法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好或最优的解。因为不进行回溯处理，贪婪法只在很少的情况下可以得到真正的最优解，比如最短路径问题、图的最小生成树问题。在大多数情况下，由于选择策略的“短视”，贪婪法会错过真正的最优解，而得不到问题的真正答案。但是贪婪法简单、高效，省去了为找最优解可能需要的穷举操作，可以得到与最优解比较接近的近似最优解，通常作为其他算法的辅助算法来使用。

当然，对于一些能够证明贪婪策略得到的就是最优解的问题，应用贪婪法可以高效地求得结果，比如求最小生成树的 Prim 算法和 Kruskal 算法。事实上，在任何算法中，只要在某个阶段使用了只考虑局部最优情况的选择策略，都可以理解为使用了贪婪算法。

贪婪法的基本设计思想有以下三个步骤：

建立对问题精确描述的数学模型，包括定义最优解的模型；
将问题分解为一系列的子问题，同时定义子问题的最优解结构；
应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用子问题的局部最优解堆叠出全局最优解。

0-1 贪婪法的例子：0-1 背包问题背包问题

核心代码如下：
spFunc:

int Choosefunc1(std::vector<OBJECT>& objs, int c)
{
    int index = -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;
}

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);
}\

完整代码如下：

// knapsack.cpp : Defines the entry point for the console application.
//
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef struct tagObject
{
    int weight;
    int price;
    int status; //0:未选中；1:已选中；2:已经不可选
}OBJECT;

typedef struct tagKnapsackProblem
{
    std::vector<OBJECT> objs;
    int totalC;
}KNAPSACK_PROBLEM;

typedef int (*SELECT_POLICY)(std::vector<OBJECT>& objs, int c);

int Choosefunc1(std::vector<OBJECT>& objs, int c)
{
    int index = -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;
}

int Choosefunc2(std::vector<OBJECT>& objs, int c)
{
    int index = -1;
    int mw = 10000;
    for(int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if((objs[i].status == 0) && (objs[i].weight < mw))
        {
            mw = objs[i].weight;
            index = i;
        }
    }

    return index;
}

int Choosefunc3(std::vector<OBJECT>& objs, int c)
{
    int index = -1;
    double ms = 0.0;
    for(int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if(objs[i].status == 0)
        {
            double si = objs[i].price;
            si = si / objs[i].weight;
            if(si > ms)
            {
                ms = si;
                index = i;
            }
        }
    }

    return index;
}

void PrintResult(std::vector<OBJECT>& objs)
{
    int totalW = 0;
    int totalP = 0;
    for(int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if(objs[i].status == 1)
        {
            totalW += objs[i].weight;
            totalP += objs[i].price;
            std::cout << "object " << i + 1 << ": weight=" << objs[i].weight <<
                                               ", price=" << objs[i].price << std::endl;
        }
    }
    std::cout << "total weight : " << totalW << ", total price : " << totalP << std::endl;
}

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);
}

const int MIN=0x80000000;
const int N=7;   //物品数量
const int V=150;  //背包容量
int f[N+1][V+1];

int Package(int *W,int *C,int N,int V)
{
 int i,j;
 memset(f,0,sizeof(f));  //初始化为0

 for(i=0;i<=N;i++)
 for(j=1;j<=V;j++)               //此步骤是解决是否恰好满足背包容量，
  f[i][j]=MIN;                //若“恰好”满足背包容量，即正好装满背包，则加上此步骤，若不需要“恰好”，则初始化为0

 for(i=1;i<=N;i++)
  for(j=C[i];j<=V;j++)
  {
   f[i][j]=(f[i-1][j]>f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]);
   std::cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<std::endl;
  }
 return f[N][V];
}

void DPAlgo()
{
 int W[8]={0,10,40,30,50,35,40,30};      //物品权重
 int C[8]={0,35,30,60,50,40,10,25};      //物品大小
 int result=Package(W,C,N,V);
 if(result>0)
 {
  std::cout<<std::endl;
  std::cout<<"the opt value:"<<result<<std::endl;
  int i=N,j=V;
  while(i)
  {
   if(f[i][j]==(f[i-1][j-C[i]]+W[i]))
   {
    std::cout<<i<<":"<<"w="<<W[i]<<",c="<<C[i]<<std::endl;
    j-=C[i];
   }
   i--;
  }
 }
 else
     std::cout<<"can not find the opt value"<<std::endl;
}

OBJECT objects[] = { {35,10,0}, {30,40,0}, {60,30,0}, {50,50,0},
                     {40,35,0}, {10,40,0}, {25,30,0} };

int main(int argc, char* argv[])
{

    KNAPSACK_PROBLEM problem;

    problem.objs.assign(objects, objects + 7);
    problem.totalC = 150;

    //GreedyAlgo(&problem, Choosefunc1);
    //GreedyAlgo(&problem, Choosefunc2);
    //GreedyAlgo(&problem, Choosefunc3);
    DPAlgo();

	return 0;
}

算法的乐趣之贪婪法

贪婪法（Greedy Algorithm）

0-1 贪婪法的例子：0-1 背包问题背包问题