江苏龙网

  1. 主页 > 生活百科 > >

贪心算法简介( 二 )

贪婪算法

策略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;}有了物品，有了方法，下面就是将两者结合起来的贪心算法
GreedyAlgovoid 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;//如果背包没有装满，还可以再装,标记下装进去的物品状态为1sum_weight_current += problem->objs[idx].weight;//把这个idx的物体的重量装进去，计算当前的重量}else{//不能选这个物品了，做个标记2后重新选剩下的problem->objs[idx].status = 2;}}PrintResult(problem->objs);//输出函数的定义，查看源代码}注意：这里对objs[idx].status定义了三种状态，分别是待选择为0（初始所有状态均为0），装进包里变为1，判断不符合变为2，这样最后只需要拿去状态为1的即可 。主函数部分
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::assignproblem.totalC = 150;cout << "Start to find the best way ,NOW" << endl;GreedyAlgo(&problem, Choosefunc3);system("pause");return 0;}查看策略3的输出结果：

贪心算法简介

文章插图
 
但是，我们再回顾一下第一个事例问题现在问题变了，还是需要找给顾客41分钱，现在的货币只有 25 分、20分、10 分、5 分和 1 分四种硬币；该怎么办？按照贪心算法的三个步骤：1.41分，局部最优化原则，先找给顾客25分；2.此时，41-25=16分，还需要找给顾客10分，然后5分，然后1分；3.最终，找给顾客一个25分，一个10分，一个5分，一个1分，共四枚硬币 。是不是觉得哪里不太对，如果给他2个20分，加一个1分，三枚硬币就可以了呢？_;总结：贪心算法的优缺点优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解 。

【贪心算法简介】


推荐阅读


上一篇：nginx注册成windows服务的解决方法

下一篇：今年高端安溪铁观音秋茶收购价上涨至两成