《编程之美》1.6 饮料供货
在微软亚洲研究院上班，大家早上来的第一件事是干啥呢？查看邮件？No，是去水房拿饮料：酸奶，豆浆，绿茶、王老吉、咖啡、可口可乐……（当然，还是有很多同事把拿饮料当做第二件事）。
管理水房的阿姨们每天都会准备很多的饮料给大家，为了提高服务质量，她们会统计大家对每种饮料的满意度。一段时间后，阿姨们已经有了大批的数据。某天早上，当实习生小飞第一个冲进水房并一次拿了五瓶酸奶、四瓶王老吉、三瓶鲜橙多时，阿姨们逮住了他，要他帮忙。
从阿姨们统计的数据中，小飞可以知道大家对每一种饮料的满意度。阿姨们还告诉小飞，STC（Smart Tea Corp.）负责给研究院供应饮料，每天总量为V。STC很神奇，他们提供的每种饮料之单个容量都是2的方幂，比如王老吉，都是23=8升的，可乐都是25=32升的。当然STC的存货也是有限的，这会是每种饮料购买量的上限。统计数据中用饮料名字、容量、数量、满意度描述每一种饮料。
那么，小飞如何完成这个任务，求出保证最大满意度的购买量呢？
【解法一】
我们先把这个问题“数学化”一下吧。
假设STC共提供n种饮料，用（Si、Vi、Ci、Hi、Bi）（对应的是饮料名字、容量、可能的最大数量、满意度、实际购买量）来表示第i种饮料（i = 0, 1,…, n-1），其中可能的最大数量指如果仅买某种饮料的最大可能数量，比如对于第i中饮料Ci=V/Vi。
基于如上公式：
饮料总容量为
；
；
总满意度为
；
；
那么题目的要求就是，在满足条件
的基础上，求
的基础上，求
对于求最优化的问题，我们来看看动态规划能否解决。用Opt（V', i）表示从第i, i+1, i+2, …, n-1种饮料中，算出总量为V'的方案中满意度之和的最大值。
因此，Opt（V, 0）就是我们要求的值。
那么，我们可以列出如下的推导公式：Opt （V', i） = max { k* Hi + Opt（V' - Vi * k, i+1）}（k = 0, 1, …, Ci,i =0, 1, …, n-1）。
即：最优化的结果 = 选择第k种饮料×满意度+减去第k种饮料×容量的最优化结果根据这样的推导公式，我们列出如下的初始边界条件：
Opt（0, n）= 0，即容量为0的情况下，最优化结果为0。
Opt（x, n）= -INF（x != 0）（–INF为负无穷大），即在容量不为0的情况下，把最优化结果设为负无穷大，并把它作为初值。
那么，根据以上的推导公式，就不难列出动态规划求解代码，如下所示：
在上面的算法中，空间复杂度为O（V*N），时间复杂度约为O（V*N*Max（Ci））。
因为我们只需要得到最大的满意度，则计算opt[i][j]的时候不需要opt[i][j+2]，只需要opt[k][j+1](0<=k<=V)，所以空间复杂度可以降为O（v）。
- int Cal(intV, int type)
- {
- opt[0][T] = 0;// 边界条件
- for(int i = 1; i <=V; i++)// 边界条件
- {
- opt[i][T] = -INF;
- }
- for(int j = T - 1; j>= 0; j--)
- {
- for(int i = 1; i <= V; i++)
- {
- opt[i][j] = -INF;
- for(int k = 0; k <= C[j];k++) // 遍历第j种饮料选取数量k
- {
- if(i < k * V[j])
- {
- break;
- }
- int x = opt[i - k * V[j]][j + 1];
- if(x != -INF)
- {
- x += H[j] * k;
- if(x > opt[i][j])
- {
- opt[i][j] = x;
- }
- }
- }
- }
- }
- return opt[V][0];
- }
【解法二】
应用上面的 动态规划法可以得到结果，那么是否有可能进一步地提高效率呢？我们知道动态规划算法的一个变形是备忘录法，备忘录法也是用一个表格来保存已解决的子问题的 答案，并通过记忆化搜索来避免计算一些不可能到达的状态。具体的实现方法是为每个子问题建立一个记录项。初始化时，该纪录项存入一个特殊的值，表示该子问 题尚未求解。在求解的过程中，对每个待求解的子问题，首先查看其相应的纪录项。若记录项中存储的是初始化时存入的特殊值，则表示该子问题是第一次遇到，此 时计算出该子问题的解，并保存在其相应的记录项中。若记录项中存储的已不是初始化时存入的初始值，则表示该子问题已经被计算过，其相应的记录项中存储的是 该子问题的解答。此时只需要从记录项中取出该子问题的解答即可。
因此，我们可以应用备忘录法来进一步提高算法的效率。
动态规划解法中，前两层循环的次序可以颠倒。也就是在生成的动态数组中，我们可以从上往下一行一行地填，或者从右往左一列一列地填都不影响最后结果，最关键的是需要事先把边界值设定好，最上面一行全为0，最右边一列全为0。
- int opt[V + 1][T + 1]; // 子问题的记录项表，假设从i到T种饮料中，
- // 找出容量总和为V’的一个方案，快乐指数最多能够达到
- // opt（V'，i，T-1），存储于opt[V’][i]，
- // 初始化时opt中存储值为-1，表示该子问题尚未求解。
- int Cal(intV, int type)
- {
- if(type == T)
- {
- if(V== 0)
- return 0;
- else
- return -INF;
- }
- if(V < 0)
- return -INF;
- else if(V == 0)
- return 0;
- else if(opt[V][type] !=-1)
- return opt[V][type]; // 该子问题已求解，则直接返回子问题的解；
- // 子问题尚未求解，则求解该子问题
- int ret = -INF;
- for(int i = 0; i <=C[type]; i++)
- {
- int temp = Cal(V– i * C[type], type + 1);
- if(temp != -INF)
- {
- temp += H[type] * i;
- if(temp > ret)
- ret = temp;
- }
- }
- return opt[V][type] =ret;
- }
【解法三】
请注意这个题目的限制条件，看看它能否给我们一些特殊的提示。
我们把信息重新整理一下，按饮料的容量（单位为L）排序：
Volume
|
TotalCount
|
Happiness
|
| 20 | TC0_0 | H0_0 |
| … | … | … |
| 20 | TC0_n0 | H0_n0 |
| … | … | … |
| 21 | TC1_0 | H1_0 |
| … | … | … |
| 2M | TCM_0 | HM_0 |
| … | … | … |
假设最大容量为2 000L。一开始，如果V%（21）非零，那么，我们肯定需要购买20L容量的饮料，至少一瓶。在这里可以使用贪心规则，购买快乐指数最高的一瓶。除去这个，我们只要再购买总量（V-20） L的饮料就可以了。这时，如果我们要购买21L容量的饮料怎么办呢？除了21L容量里面快乐指数最高的，我们还应该考虑，两个容量为20L的饮料组合的情 况。其实我们可以把剩下的容量为20L的饮料之快乐指数从大到小排列，并用最大的两个快乐指数组合出一个新的“容量为2L”的饮料。不断地这样使用贪心原 则，即得解。这是不是就简单了很多呢？
书中的贪心解法似曾相识，把信息按照饮料的容量排序（其中设我们有n0种容量为20的饮料）：
Volume
|
TotalCount
|
Happiness
|
| 20 | TC0_0 | H0_0 |
| … | … | … |
| 20 | TC0_n0 | H0_n0 |
| … | … | … |
| 21 | TC1_0 | H1_0 |
| … | … | … |
| 2M | TCM_0 | HM_0 |
| … | … | … |
然后按照下面的顺序进行贪心选择：
(1) 饮料总量为1，从容量为20的饮料中选出快乐指数最大的。
(2) 饮料总量为2，从容量为21的饮料中选出快乐指数最大的（设为H1），与容量为20的饮料中快乐指数最大的（设为H0），比较H1和2* H0，取出其中最大者为当前最佳选择
(3) 继续进行下去，直到求出Opt（V，0）
粗看一下，有些似曾相识。我们在买书问题的时候也曾面临将买书计划拆分，然后查表进行贪心选择。然而买书问题每次选择至多选M本书，而且每次选择只影响下一次选择，所以只需要把2M进行有限的拆分即可。
而本题则不尽相同，对于某种容量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就不是最优解的一部分，这就和贪心算法的精神不符，所以这个方法其实还是动态规划。
书中提到第二种解法，贪心算法。由于所有饮料的容量都是2的整数幂，这就给贪心创造了条件。
假设给定的容量为V，我们可以把V写成二进制的形式，不妨设V=7，二进制的写法为111。
接下来我们就从最低位开始取：
第一步，取第一个1：拿出容量为1满意度最大的饮料，
第二步，取第二个1：使用剩余容量为1的饮料构造容量为2的饮料，比如(1,2)(1,3)构造出(2,5)，并从新构造的和原有容量为2的所有饮料中选出满意度最大的。
第三步，取第三个1：递归构造容量为4的饮料，并从新构造的和原有容量为4的所有饮料中选出满意度最大的。
- int TakeOutMax( int k)
- {
- int maxHappiness = 0;
- if (k < 0) return 0;
- if (k > 0){
- int t =k/2;
- int h = TakeOutMax(t);
- if (h>0){
- drinks[t].push_back(Drink((int)pow(2,t), 1, h));
- h = TakeOutMax(t);
- if (h>0)
- {
- drinks[t].push_back(Drink((int)pow(2,t), 1, h));
- }
- }
- int p1, p2;
- p1 = p2 = -1;
- for (int i=0; i<drinks[t].size(); i++)
- {
- for (int j=i+1; j<drinks[t].size(); ++j)
- {
- if (drinks[t][i].TotalCount>0 && drinks[t][j].TotalCount>0 && drinks[t][i].Happiness+drinks[t][j].Happiness>maxHappiness)
- {
- maxHappiness = drinks[t][i].Happiness+drinks[t][j].Happiness;
- p1 = i;
- p2 = j;
- }
- }
- }
- if (p1 >-1 && p2 > -1)
- {
- drinks[t][p1].TotalCount--;
- drinks[t][p2].TotalCount--;
- drinks[k].push_back(Drink((int)pow(2,k), 1, maxHappiness));
- }
- }
- int p=-1;
- maxHappiness = 0;
- for (int i=0; i<drinks[k].size(); ++i)
- {
- if (drinks[k][i].TotalCount>0 && drinks[k][i].Happiness>maxHappiness)
- {
- maxHappiness = drinks[k][i].Happiness;
- p = i;
- }
- }
- if (p >=0 ){
- drinks[k][p].TotalCount--;
- }
- return maxHappiness;
- }
- // 贪心算法
- int GetMaxHappinessByGreed(int V)
- {
- int k = V;
- int i=0;
- int happiness = 0;
- while(k)
- {
- if (k & 1) happiness += TakeOutMax(i);
- k >>= 1;
- i++;
- }
- return happiness;
- }
http://bylijinnan.iteye.com/blog/1601908
- * 设Opt（V’，i）表示从i到n-1种饮料中，总容量为V’的方案中，满意度之和的最大值。
- * 那么递归式就应该是：Opt（V’，i）=max{ k * Hi+Opt（V’-Vi * k，i+1）}（k=0，1，2…，Ci，i=0，1，2…，n-1）
- * 其中Ci为第i种饮料的最大供应量
- *
- * 想了好久都没法理解书上这个递推公式里面的i+1，为什么是i+1而不是其他？
- * 后来我转换了一下，代码本质上是一样的，只是比较符合我自己的思路：
- * opt[i][j] i代表供货总容量，j代表饮料种类。假设容量都是整数。i和j都从1开始考虑：
- * 当只有一种饮料时，容易求得各种总容量对应的最大满意度；当新增加一种饮料时，将一部分容量用新饮料代替，求得新的满意度；
- * 将新的满意度与旧满意度比较，如果新结果较大就更新。
- * 如何由opt[i][j-1]求得opt[i][j]呢？
- * --将一部分容量分给第j种饮料，那新的满意度就是(opt[i-k*v][j]+k*value),其中v代表第j种饮料每瓶的容量,k代表瓶数,value代表满意度
- public int maxValue(Beverage[] beverages,int V,int T){
- if(beverages==null||beverages.length==0){
- return -1;
- }
- if(V<0){
- return -1;
- }
- if(T<0 || T>beverages.length){ //beverages' index starts with 1
- return -1;
- }
- int[][] opt=new int[V+1][T+1];
- for(int j=1;j<=T;j++){
- int c=beverages[j].count;
- int v=beverages[j].volume;
- int value=beverages[j].value;
- for(int i=1;i<=V;i++){
- for(int k=0;k<=c;k++){
- if(i<k*v){
- break;
- }
- int x=opt[i-k*v][j-1];
- int y=x+k*value;
- if(y>=opt[i][j]){
- opt[i][j]=y;
- }
- }
- }
- }
- // myprint(opt);
- return opt[V][T];
- }
- static class Beverage{
- int value; //满意度
- int volume; //每瓶的容量
- int count; //最多可提供多少瓶
- Beverage(int value,int volume,int count){
- this.value=value;
- this.volume=volume;
- this.count=count;
- }
- }
http://www.cnblogs.com/gaopeng527/p/4604079.html
public int cal(int v, int T){ int i,j,k; //opt[v][i]表示从i,...,t种饮料中，算出总容量为v的方案的满意度之和的最大值 int[][] opt; opt = new int[v+1][T+1]; opt[0][T] = 0; //边界条件 for(i=1;i<=v;i++){ opt[i][T]=-INF; //边界条件 } for(j=T-1;j>=0;j--){ for(i=0;i<=v;i++){ opt[i][j] = -INF; for(k=0;k<=count[j];k++){ //遍历第j种饮料选取数量k if(i<=k*V[j]){ break; } int x = opt[i-k*V[j]][j+1]; if(x!=-INF){ x += k*h[j]; if(x > opt[i][j]){ opt[i][j]=x; } } } } } return opt[v][0]; }
【解法二】备忘录法
public int cal(int v, int t){ int i,j; //opt[v][i]表示从i,...,t种饮料中，算出总容量为v的方案的满意度之和的最大值 int[][] opt; //子问题的记录项表，初始化时opt中存储值为-1，表示该子问题尚未求解 opt = new int[v+1][T+1]; for(i=0;i<=v;i++){ //初始化opt, this should be put outside for(j=0;j<=t;j++){ opt[i][j] = -1; } } if(t == T){ if(v == 0) return 0; else return -INF; } if(v < 0) return -INF; else if(v == 0) return 0; else if(opt[v][t]!=-1){ //该子问题已求解，直接返回子问题的解 return opt[v][t]; } //子问题尚未求解，则求解子问题 int result = -INF; for(i=0;i<count[t];i++){ int temp = cal(v-i*V[t],t+1); if(temp != INF){ temp += i*h[t]; if(temp>result) result = temp; } } return opt[v][t] = result; }
【解法三】 贪心算法
