摘要：編程之美有一道很有趣的題目買書問題，題目的內容如下上柜的哈利波特平裝本系列，一共有五卷。假設具體折扣的情況如下本數折扣本數折扣本數折扣本數折扣設計出算法，能夠計算出讀者所購買的一批書的最低價格。列出公式購買的書里，其中有五卷享受到了折扣。

《編程之美》有一道很有趣的題目：買書問題，題目的內容如下：
上柜的《哈利波特》平裝本系列，一共有五卷。假設每一卷多帶帶銷售均需8歐元。如果讀者一次購買不同的兩卷，就可以扣除5%的費用，三卷則更多。假設具體折扣的情況如下：

??????? 本數????2?????? 折扣?? 5%

??????? 本數????3???????折扣? 10%

??????? 本數????4???????折扣? 20%

??????? 本數??? 5?????? 折扣??25%?
???????
設計出算法，能夠計算出讀者所購買的一批書的最低價格。
作者先嘗試用貪心算法分析問題，最后得出結論：針對這個問題試圖用貪心策略行不通，然后轉用動態規劃算法解答。大概思路是：
用（X1,X2,X3,X4,X5）代表購買每卷的個數，F（X1，X2，X3，X4，X5）代表最低價格。并滿足X1 <= X2 <= X3 <= X4 <= X5
可得到：

F（X1，X2，X3，X4，X5）  = 0                                                // if (X1 = X2 = X3 = X4 = X5 = 0)
                       = min{
                            5*8*(1-25%) +F（X1-1，X2-1，X3-1，X4-1，X5-1）  // if (X1 > 0)
                            4*8*(1-20%) +F（X1，X2-1，X3-1，X4-1，X5-1）??? // if (X2 > 0)
                            3*8*(1-10%) +F（X1，X2，X3-1，X4-1，X5-1）??????// if (X3 > 0)
                            2*8*(1-5%) +F（X1，X2，X3，X4-1，X5-1）?????????// if (X4 > 0)
                            8 +F（X1，X2，X3，X4，X5-1）???????             // if (X5 > 0)
                         }???

我們來分析題目，“讀者所購買的一批書的最低價格”分兩種場景，一種是這批書里每一卷的本數都是確定的；另一種是這批書里每一卷的本數都是不確定的，我們只能得知這批書總共有多少本，然后根據總數推算出所有組合的最低價格。顯然，作者給出的算法針對的是前者，如果是后者的話，如何設計算法呢？
我們用N代表書的總數，F(N)代表N本書的價格，并滿足N > 0 ，那么有以下五種組合：
1、購買的書里，其中有多帶帶的一卷沒享受到折扣。舉例：11本書，5+5+1組合。列出公式：

F(N) = F(N - 1) + 8                                                       // if (N > 0)

2、購買的書里，其中有兩卷享受到了5%折扣。舉例：11本書，5+4+2組合。列出公式：

F(N) = F(N - 2) + 8 × 2 × 95%                                             // if (N > 1)

3、購買的書里，其中有三卷享受到了10%折扣。舉例：11本書，4+4+3組合。列出公式：

F(N) = F(N - 3) + 8 × 3 × 90%                                             // if (N > 2)

4、購買的書里，其中有四卷享受到了20%折扣。舉例：11本書，5+4+2組合。列出公式：

F(N) = F(N - 4) + 8 × 4 × 80%                                             // if (N > 3)

5、購買的書里，其中有五卷享受到了25%折扣。舉例：11本書，5+4+2組合。列出公式：

F(N) = F(N - 5) + 8 × 5 × 75%                                             // if (N > 4)

可得到：

min(F(N)) = min{
                F(N - 1) + 8                                              // if (N > 0)
                F(N - 2) + 8 × 2 × 95%                                    // if (N > 1)
                F(N - 3) + 8 × 3 × 90%                                    // if (N > 2)
                F(N - 4) + 8 × 4 × 80%                                    // if (N > 3)
                F(N - 5) + 8 × 5 × 75%                                    // if (N > 4)
            }

源代碼如下：

package algorith.books;

import java.util.Scanner;

public class Books1 {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            System.out.println("the min price is " + price(n));
        }
    }

    public static double price(int n){
        double min_p = 0;

        if (n==0)
            return 0;

        min_p = price(n-1) + 8;

        if (n >= 2) {
            double temp = price(n-2)+8*2*0.95;
            if (min_p > temp)
                min_p = temp;
        }

        if (n >= 3) {
            double temp = price(n-3)+8*3*0.9;
            if (min_p > temp)
                min_p = temp;
        }

        if (n >= 4) {
            double temp = price(n-4)+8*4*0.8;
            if (min_p > temp)
                min_p = temp;
        }

        if (n >= 5) {
            double temp = price(n-5)+8*5*0.75;
            if (min_p > temp)
                min_p = temp;
        }

        return min_p;
    }

}

運行結果如下：

1
the min price is 8.0
2
the min price is 15.2
3
the min price is 21.6
4
the min price is 25.6
5
the min price is 30.0
6
the min price is 38.0
7
the min price is 45.2
8
the min price is 51.2
9
the min price is 55.6
10
the min price is 60.0