程式設計之美 - 1.6 飲料供貨 ☞ 【動态規劃】

問題導讀：

在微軟亞洲研究院上班，大家早上來的第一件事是幹啥呢？檢視郵件？No，是去水房拿飲料：酸奶，豆漿，綠茶、王老吉、咖啡、可口可樂……（當然，還是有很多同僚把拿飲料當做第二件事）。

管理水房的阿姨們每天都會準備很多的飲料給大家，為了提高服務品質，她們會統計大家對每種飲料的滿意度。一段時間後，阿姨們已經有了大批的資料。某天早上，當實習生小飛第一個沖進水房并一次拿了五瓶酸奶、四瓶王老吉、三瓶鮮橙多時，阿姨們逮住了他，要他幫忙。

從阿姨們統計的資料中，小飛可以知道大家對每一種飲料的滿意度。阿姨們還告訴小飛，STC（Smart Tea Corp.）負責給研究院供應飲料，每天總量為V。STC很神奇，他們提供的每種飲料之單個容量都是2的方幂，比如王老吉，都是23=8升的，可樂都是25=32升的。當然STC的存貨也是有限的，這會是每種飲料購買量的上限。統計資料中用飲料名字、容量、數量、滿意度描述每一種飲料。

那麼，小飛如何完成這個任務，求出保證最大滿意度的購買量呢？

解決方案：

package Chapter1;

import java.io.*;

public class Func_1_6_1 {
    public static void main(String []args) {
        Func_1_6_1 f = new Func_1_6_1();
        Beverage []beverages = f.getData("/data/BeautyProgramming/Func_1_6_1.txt");
        System.out.println(f.digitSatisfy(beverages, 7));
    }
    /*
    Opt(v`,i) 為從i到最後一種飲料中，算出總量為v`的最大滿意度之和
    Opt = max{
        k*Hi + Opt(v` - vi*k, i+1)
    }
     */
    // volume時最大滿意度
    int digitSatisfy(Beverage []beverages, int volume) {
        // 如果beverages 沒有資料，或者volume為0 直接傳回 -1
        if (beverages == null || beverages.length == 0 || volume == 0) {
            return -1;
        }

        //建立opt數組
        int v = volume;
        int t = beverages.length;
        int [][]opt = new int[v+1][t+1];

        //初始化opt
        int INF = 1000;
        opt[0][t] = 0;
        for (int i = 1; i <= v; i++) opt[i][t] = -INF; // 邊界
        for (int i = t-1; i >= 0; i--) {
            int mark = beverages[i].mark;
            int content = beverages[i].content;
            int count = beverages[i].count;
            // 體積
            for (int j = 0; j <= v; j++) {
                opt[j][i] = -INF; // 相對邊界
                // max
                for (int k = 0; k <= count; k++) {
                    if (j < k*content) break;
                    int x = opt[j-k*content][i+1] + mark*k;
                    if (x >= opt[j][i]) opt[j][i] = x;
                }
            }
        }
        /*
        裝不滿：
        3
        1 4 2
        2 4 3
        3 4 4
         */
        int res = -INF;
        for (int []i : opt)
            res = i[0] > res ? i[0] : res;
        return res; // 狀态轉移公式的最外層結果
    }
    // 飲料
    class Beverage {
        int mark; // 打分
        int content; // 容量
        int count; // 數量

        public Beverage(int mark, int content, int count) {
            this.mark = mark;
            this.content = content;
            this.count = count;
        }
    }
    // 将string 轉int
    int[] parseInt(String []str) {
        int []res = new int[str.length];
        for (int i = 0; i < str.length; i++) {
            res[i] = Integer.parseInt(str[i]);
        }
        return res;
    }
    // 得到data
    Beverage[] getData(String file_path) {
        Beverage []beverages;
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(
                    new InputStreamReader(
                            new FileInputStream(
                                    new File(file_path))));
            String line = null;
            String []str;
            int []digit;

            int total = Integer.parseInt(reader.readLine());

            beverages = new Beverage[total];
            for (int i = 0; i < total; i++) {
                if ((line = reader.readLine()) != null) {
                    str = line.split(" ");
                    digit = parseInt(str);
                    int mark = digit[0];
                    int content = digit[1];
                    int count = digit[2];
                    beverages[i] = new Beverage(mark, content, count);
                }
            }
            return beverages;
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }
}      

9
2 1 2
3 1 2
5 1 3
4 1 3
6 2 2
5 2 3
4 2 4
18 4 1
12 4 2      

33