微软亚洲研究院--饮料供货

在微软亚洲研究院上班，大家早上来第一件事是做什么呢？查看邮件？不，是去水房拿饮料：绿茶、王老吉、星巴克咖啡、可口可乐……（当然，还是有很多同事把拿饮料当作第二件事）。

阿姨们每天都会准备很多的饮料给大家，为了提高服务质量，同时也会统计大家对每种饮料满意度。一段时间后，阿姨们已经有了大批的数据。她们希望能从这些数据中挖掘出一些有用的信息，以使大家的满意度和值最大。某天早上，当实习生小飞第一个冲进水房并一次拿了五个酸奶、四个王老吉、三个鲜橙多时，阿姨们逮住了他，要他解决满意度最大化的问题。

从阿姨们统计的数据中，小飞可以知道大家对每一种饮料的满意度。阿姨们还告诉小飞， STC（Smart Tea Corp.）负责给研究院供应饮料，每天总量为V。STC很神奇，他们的每种饮料的单个容量都是2的方幂，比如王老吉，都是2^3=8升的，可乐都是2^5=32升的。当然STC的存货也是有限的，这会是每种饮料的购买量上限。统计数据中用（饮料名字，容量，数量，满意度）描述每一种饮料。

那么，小飞如何完成这个任务，求出保证最大满意度的购买量呢？

 

我们先把这个问题“数学化”一下吧。

假设STC共提供T种饮料，用(S_i, V_i, C_i, H_i, B_i)（对应（饮料名字，容量，可能的最大数量，满意度，实际购买量））来表示第i种饮料(i = 0, ..., T-1)，其中可能的最大数量为是指如果仅买某种饮料的最大可能数量，比如对于第i中饮料C_i=V/V_i。

基于如上公式：

饮料总容量为

总满意度为

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

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

因此，Opt(V, T)就是我们要求解的值。

那么，我们可以列出如下的推导公式：Opt(V', i) = max { k* H_i + Opt(V' - V_i * k, i-1)} (k = 0, 1, ..., C_i,  i=0,1,…,T-1)。

即：最优化的结果=选择第k种饮料*满意度+减去第k种饮料*容量的最优化结果

根据这样的推导公式，我们列出如下的初始边界条件：

Opt(0, T) = 0   容量为0的情况下，最优化结果为0

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

那么，根据以上的推导公式，就不难列出动态规划求解代码如下：

代码：1-6-1

    int Cal(int V, 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 = 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*T)，时间复杂度约为O(V*T*Max(C_i)) 。

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