1.6 饮料供应
1、问题描述及分析
微软每天为员工提供各种不同的饮料,如可乐,酸奶,豆浆,咖啡,绿茶……..,饮料i的单位容量为Vi,
其中每种饮料单个容量都是2的方幂,员工对饮料i的满意度为Hi,冰柜的总容量为V(每天必须装满),
问题是如何组合现有的各种饮料,使总的满意度最高。
解法一:动态规划
(Si,Vi,Ci,Hi,Bi)对应饮料名字、容量、可能的最大数量、满意度、实际购买量
设Opt(V’,i)表示从i到n-1种饮料中,Ci为第i种饮料可能的最大数量,算出总量为V’的方案中满意度之和的最大值。
Opt(V’,i)=max{ k*Hi+ Opt(V‘-Vi*k,i+1)}(k=0,1,2…,Ci,i=0,1,2…,n-1)
即: 最优化的结果=“选择k个第i中饮料的满意度+剩下部分不考虑第i种饮料的最优化结果”
解法二、贪心算法
把信息按照饮料的容量排序(其中设我们有n0种容量为20的饮料)
然后按照下面的顺序进行贪心选择:
1、饮料总量为1,从容量为20的饮料中选出快乐指数最大的。
2、饮料总量为2,从容量为21的饮料中选出快乐指数最大的(设为H1),
与容量为20的饮料中快乐指数最大的(设为H0),比较H1和2*H0,取出其中最大者为当前最佳选择
3、继续进行下去,直到求出Opt(V,0)
对于某种容量V’(以V’=11为例)来说,有两个问题:
1、首先,我们需要察看所有拆分的可能性,找出其中最大者作为本次贪心选择的结果。
其中,由于“每种饮料的单位容量都是2的方幂”,所以拆分结果仅考虑用小于V’的2的方幂来进行组合,
即(计算式1)11=8+2+1,4+4+2=1,4+2+2+2+1,….,1+1+…+1。
可以看到,对于V’我们至少可以“拆”出V’种组合(或许更多),
即便我们把每次的计算结果用表格保存起来,我们的查找次数也至少是Ω(1+2+…+V’=V’2),
空间复杂度也很高,并没有如数中说“简单很多”。
而且,如果取消“每种饮料的单位容量都是2的方幂”的限制,
拆分的结果就会变成(计算式2)11=10+1,9+2,…,5+5,5+5+1,5+4+2,…..,
导致查找次数进一步增加。
2、 其次,让我们回到贪心选择的定义上来。
由于贪心选择性,贪心算法的过程是每次选择都选取当前看来最好的结果,使得当达到最终状态时的结果刚好是最优解。
而我们再看V’=11的例子,假设最优解是4+4+2+1,则我们曾经计算过的8就不是最优解的一部分,
这就和贪心算法的精神不符,所以这个方法其实还是动态规划。