经典案例解析贪心算法

贪心算法，又名贪婪算法，顾名思义，是指在对问题求解时，总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，背包最大价值问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

这里我们采用更容易理解的背包最大价值问题：

有一个背包，最多能承载重量为 C=150的物品，现在有7个物品（物品不能分割成任意大小），编号为 1~7，重量分别是 wi=[35,30,60,50,40,10,25]，价值分别是 pi=[10,40,30,50,35,40,30]，现在从这 7 个物品中选择一个或多个装入背包，要求在物品总重量不超过 C 的前提下，所装入的物品总价值最高。这里需要明确的几个点：1.每个物品都有重量和价值两个属性；2.每个物品分被选中和不被选中两个状态（后面还有个问题，待讨论）；3.可选物品列表已知，背包总的承重量一定。所以，构建描述每个物品的数据体结构 OBJECT和背包问题定义为：//typedef是类型定义的意思

//定义待选物体的结构体类型
typedef struct tagObject
{
    int weight;
    int price;
    int status;
}OBJECT;

//定义背包问题
typedef struct tagKnapsackProblem
{
    vector<OBJECT>objs;
    int totalC;
}KNAPSACK_PROBLEM;

如下,实例化objectsOBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 },

                    { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };

那么，我们思考一下，如何选，才使得装进背包的价值最大呢？

策略1：价值主导选择，每次都选价值最高的物品放进背包；

策略2：重量主导选择，每次都选择重量最轻的物品放进背包；

策略3：价值密度主导选择，每次选择都选价值/重量最高的物品放进背包。

策略1：价值主导选择

每次都选价值最高的物品放进背包根据这个策略最终选择装入背包的物品编号依次是 4、2、6、5，此时包中物品总重量是 130，总价值是 165。//遍历没有被选的objs,并且选择price最大的物品,返回被选物品的编号

int Choosefunc1(std::vector<OBJECT>& objs, int c)
{
    int index = -1;  //-1表示背包容量已满
    int max_price = 0;
    //在objs[i].status == 0的物品里，遍历挑选objs[i].price最大的物品
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if ((objs[i].status == 0) && (objs[i].price > max_price ))//objs没有被选,并且price> max_price
        {
            max_price  = objs[i].price;
            index = i;
        }
    }
    return index;
}

策略2：重量主导选择

每次都选择重量最轻(小)的物品放进背包根据这个策略最终选择装入背包的物品编号依次是 6、7、2、1、5，此时包中物品总重量是 140，总价值是 155。int Choosefunc2(std::vector<OBJECT>& objs, int c)

{
    int index = -1;
    int min_weight= 10000;
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if ((objs[i].status == 0) && (objs[i].weight < min_weight))
        {
            min_weight= objs[i].weight;
            index = i;
        }
    }
    return index;
}

策略3：价值密度主导选择

每次选择都选价值/重量最高(大)的物品放进背包物品的价值密度 si 定义为 pi/wi，这 7 件物品的价值密度分别为 si=[0.286,1.333,0.5,1.0,0.875,4.0,1.2]。根据这个策略最终选择装入背包的物品编号依次是 6、2、7、4、1，此时包中物品的总重量是 150，总价值是 170。int Choosefunc3(std::vector<OBJECT>& objs, int c)

{
    int index = -1;
    double max_s = 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 > max_s)
            {
                max_s = si;
                index = i;
            }
        }
    }
    return index;
}

回过头来，我们再来根据贪心算法的定义来对这个问题进行贪心算法GreedyAlgo：

void GreedyAlgo
(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc)
{
    int idx;
    int sum_weight_current = 0;
    //先选
    while ((idx = spFunc(problem->objs, problem->totalC- sum_weight_current)) != -1)
    {   //再检查，是否能装进去
        if ((sum_weight_current + problem->objs[idx].weight) <= problem->totalC)
        {
            problem->objs[idx].status = 1;//如果背包没有装满，还可以再装,标记下装进去的物品状态为1
            sum_weight_current += problem->objs[idx].weight;//把这个idx的物体的重量装进去，计算当前的重量
        }
        else
        {
            //不能选这个物品了，做个标记2后重新选剩下的
            problem->objs[idx].status = 2;
        }
    }
    PrintResult(problem->objs);//输出函数的定义，查看源代码
}

主函数部分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()
{
    KNAPSACK_PROBLEM problem;
    problem.objs.assign(objects, objects + 7);//assign赋值，std::vector::assign
    problem.totalC = 150;
    cout << "Start to find the best way ,NOW" << endl;
    GreedyAlgo(&problem, Choosefunc3);
    system("pause");
    return 0;
}

策略3的输出结果：

通过上面的背包价值最大问题，我们不难看出：贪心算法总体来说简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；但贪心算法不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。贪心算法只是众多优秀算法中的一员，想要了解更多神奇的算法可以观看本站的数据结构和算法教程，学习新的算法知识。