贪心算法 | 背包问题——阿里巴巴与四十大盗
2、背包问题——阿里巴巴与四十大盗
问题:有一天,阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时,远处突然出现一股烟尘,弥漫着直向上空非扬,朝他这儿卷过来,而且越来越近。靠近以后,他才看清原来是一支马队,他们公有四十人,一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋,从丛林中一支来打那个大石头跟前,喃喃地说到:“芝麻、开门吧!”,随着那个头目的喊声,大石头前突然出现一道宽阔的门路,于是强盗们鱼贯而入。阿里巴巴待在树上观察他们,直到他们走的无影无踪之后,才从树上下来。他大声喊道:“芝麻、开门吧!”,他的喊声刚落,洞门立刻打开了,他小心翼翼地走了进去,一下子惊呆了,洞中堆满了财务,还有多的无法计数的金银财宝,有的散堆在地上,有的盛在皮袋中。突然看见这么多的金银财宝,阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界,见识一下这些宝物,他想一种宝物只拿一个,如果太重就用锤子凿开,但毛驴的运载能力是有限的,怎么才能用驴子运走最大价值的财宝分给穷人呢?
2.1问题分析
假设山洞中有n种宝物,每种宝物有一定重量w和相应的价值v,毛驴运载能力有限,只能运走m重量的宝物,一种宝物只能拿一样,宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢?
(1)每次挑选价值最大的宝物装入背包,得到的结果是否最优?
(2)每次挑选重量最小的宝物装入背包,能否得到最优解?
(3)每次选择单位重量价值最大的宝物,能否使价值最高?
如果选择价值最大的宝物,但重量非常大,也是不行的,因为运载能力是有限的,所以舍弃策略(1);如果选重量小的物品装入,那么其价值不一定高,所以不能再总重限制的情况下保证价值最大,所以舍弃策略(2);而第三种是每次选择单位重量价值最大的宝物,也就是说每次选择性价比(价值/重量)最高的宝物,如果可以达到运载重量m,那么一定能使得价值最大。
因此采用策略(3),每次从剩下的宝物中选择性价比最高的宝物。
2.2算法设计
(1)数据结构及初始化
将n种宝物的重量、价值和性价比存储结构体three(包含重量、价值、性价比3个成员)中,将其按照性价比从高到低排序。采用sum来存储毛驴能够运走的最大价值,初始化为0;
(2)贪心策略
按照性价比从大到小选取宝物,直到达到毛驴的运载能力。每次选择性价比高的物品,判断是否小于m(毛驴运载能力),如果小于m,则放入,sum(已放入物品的价值)加上当前宝物的价值,m减去放入宝物的重量;如果不小于m,则取该宝物的一部分m*p[i],m=0时,程序结束。m减少到0,则sum得到最大值。
2.3图解算法
假设有一批宝物,价值和重量如下表所示,其中毛驴运载能力m=30
宝物i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
重量w[i] |
4 |
2 |
9 |
5 |
5 |
8 |
5 |
4 |
5 |
5 |
价值v[i] |
3 |
8 |
18 |
6 |
8 |
20 |
5 |
6 |
7 |
15 |
(1)按照性价比(价值/重量)降序排序,如下表所示:
宝物i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
重量w[i] |
4 |
2 |
9 |
5 |
5 |
8 |
5 |
4 |
5 |
5 |
价值v[i] |
3 |
8 |
18 |
6 |
8 |
20 |
5 |
6 |
7 |
15 |
性价比p[i] |
4 |
3 |
2.5 |
2 |
1.6 |
1.5 |
1.4 |
1.2 |
1 |
0.75 |
(2)按照贪心策略,每次选择性价比高的宝物放入:
第1次选择宝物2,剩余容量30-2=28,目前装入最大价值为8;
第2次选择宝物10,剩余容量28-5=23,目前装入最大价值为8+15=23;
第3次选择宝物6,剩余容量23-8=15,目前装入最大价值为23+20=43;
第4次选择宝物3,剩余容量15-9=6,目前装入最大价值为43+18=61;
第5次选择宝物5,剩余容量6-5=1,目前装入最大价值为61+8=69;
第6次选择宝物8,剩余容量1<4,装入1,目前装入最大价值为69+(6/4)*1=70.5;
(3)构造最优解
把这些让如的宝物序号组合在一起,就得到了最优解(2,10,6,3,5,8),其中最后一个宝物为部分装入(装入1单位),能够装入宝物的最大价值为70.5
2.4伪代码详解
(1)数据结构定义
根据算法设计中的数据结构,首先定义一个结构体three:
struct three {
double w; //每种宝物的重量
double v; //每种宝物的价值
double p; //每种宝物的性价比(价值/重量)
}
(2)性价比排序
可以利用C++中的排序函数sort,对宝物的性价比进行从小到大(非递减)排序。要使用此函数需引入头文件:
#include <algorithm>
sort(begin, end) //参数begin和end表示一个范围,分别为待排序数组的首地址和尾地址
//sort 函数默认为升序
在本例中采用结构体形式存储,按结构体中的一个字段,即性价比排序。如果不适用自定义比较函数,那么sort函数排序时不知道按哪一项的值排序,因此采用自定义比较函数的办法实现宝物性价比的降序排序:
(3)贪心算法求解
在性价比排序的基础上,进行贪心算法运算。如果剩余容量比当前宝物的重量大,则可以放入,剩余容量减去当前宝物的重量,已放入物品的价值加上当前宝物的价值。如果剩余容量比当前宝物的重量小,表示不可以全部放入,可以切割下来一部分(正好是剩余容量),然后令剩余容量乘以当前物品的单位重量价值,已放入物品的价值加上该价值,即为能放入宝物的最大价值。
for(int i=0; i<n; i++) //按照排好的顺序,执行贪心策略
{
if( m > s[i].w) //如果宝物的重量小于毛驴的运载能力,即剩余容量
{
m -= s[i].w;
sum += s[i].v;
}
else //如果宝物的总量大于毛驴的承载能力
{
//进行宝物切割,切割一部分(m重量),正好达到毛驴称重
sum += m * s[i].p;
break;
}
}