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），其中可能的最大数量指STC存货的上限。

基于如上表示：

饮料总容量为；

总满意度为；

那么题目的要求就是，在满足条件的基础上，求解。

对于求最优化的问题，我们来看看动态规划能否解决。用Opt（V', i）表示从第i, i+1, i+2, …, n-1种饮料中，算出总量为V’的方案中满意度之和的最大值。

因此，Opt（V, n）就是我们要求的值。

那么，我们可以列出如下的推导公式：Opt（V',i）=max{k×Hi+Op（t V'-Vi×k,i+1）}（k=0, 1, …, Ci, i=0, 1, …, n-1）。

即：最优化的结果=“选择k个第i种饮料的满意度+剩下部分不考虑第i种饮料的最优化结果”的最大值。根据推导公式，我们列出如下的初始边界条件：

Opt（0, n）=0，即容量为0的情况下，最优化结果为0；

Opt（x, n）=-INF（x !=0）（-INF为负无穷大），即在容量不为0的情况下，把最优化结果设为负无穷大，并把它作为初值。

根据以上的推导公式，就不难列出动态规划求解代码，如代码清单1-9所示。

代码清单1-9

    int Cal(int V, int T)
    {
        opt[0][T]=0;                            // 边界条件，T为饮料种类
        for(int i=1; i <=V; i++)               // 边界条件
        {
            opt[i][T]=-INF;
        }
        for(int j=T -1; j >=0; j--)
        {
            for(int i=0; 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];
    }

在上面的算法中，空间复杂度为O（V×N），时间复杂度约为O（V×N×Max（Ci））。

因为我们只需要得到最大的满意度，则计算opt[i][j]的时候不需要opt[i][j+2]，只需要opt[i][j]和opt[i][j+1]，所以空间复杂度可以降为O（V）。

解法二

应用上面的动态规划法可以得到结果，那么是否有可能进一步地提高效率呢？我们知道动态规划算法的一个变形是备忘录法，备忘录法也是用一个表格来保存已解决的子问题的答案，并通过记忆化搜索来避免计算一些不可能到达的状态。具体的实现方法是为每个子问题建立一个记录项。初始化时，该纪录项存入一个特殊的值，表示该子问题尚未求解。在求解的过程中，对每个待求解的子问题，首先查看其相应的纪录项。若记录项中存储的是初始化时存入的特殊值，则表示该子问题是第一次遇到，此时计算出该子问题的解，并保存在其相应的记录项中。若记录项中存储的已不是初始值，则表示该子问题已经被计算过，此时只需要从记录项中取出该子问题的解答即可。

因此，我们可以应用备忘录法来进一步提高算法的效率（如代码清单1-10）。

代码清单1-10

    int[V+1][T+1] opt;       // 子问题的记录项表，假设从i到T种饮料中，
                                  // 找出容量总和为V’的一个方案，满意度最多能够达到
                                  // opt（V', i, T-1），存储于opt[V'][i]，
                                  // 初始化时opt中存储值为-1，表示该子问题尚未求解
    int Cal(int V, 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）排序：

如上表，我们有n0种容量为20L的饮料，它们的数量和满意度分别为（TC0_0, H0_0）,（TC0_1, H0_1）……假设最大容量为2ML。一开始，如果V%（21）非零，那么，我们肯定需要购买20L容量的饮料，至少一瓶。在这里可以使用贪心规则，购买满意度最高的一瓶。除去这个，我们只要再购买总量（V-20）L的饮料就可以了。这时，如果我们要购买21L容量的饮料怎么办呢？除了21L容量里面满意度最高的，我们还应该考虑，两个容量为20L的饮料组合的情况。其实我们可以把剩下的容量为20L的饮料按满意度从大到小排列，并用最大的两个满意度组合出一个新的“容量为2L”的饮料。不断地使用这样贪心原则，即得解。这是不是就简单了很多呢？