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”的飲料。不斷地使用這樣貪心原則，即得解。這是不是就簡單了很多呢？