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

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

??????? 本數(shù)????2?????? 折扣?? 5%

??????? 本數(shù)????3???????折扣? 10%

??????? 本數(shù)????4???????折扣? 20%

??????? 本數(shù)??? 5?????? 折扣??25%?
???????
設(shè)計出算法，能夠計算出讀者所購買的一批書的最低價格。
作者先嘗試用貪心算法分析問題，最后得出結(jié)論：針對這個問題試圖用貪心策略行不通，然后轉(zhuǎn)用動態(tài)規(guī)劃算法解答。大概思路是：
用（X1,X2,X3,X4,X5）代表購買每卷的個數(shù)，F(xiàn)（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)
                         }???

我們來分析題目，“讀者所購買的一批書的最低價格”分兩種場景，一種是這批書里每一卷的本數(shù)都是確定的；另一種是這批書里每一卷的本數(shù)都是不確定的，我們只能得知這批書總共有多少本，然后根據(jù)總數(shù)推算出所有組合的最低價格。顯然，作者給出的算法針對的是前者，如果是后者的話，如何設(shè)計算法呢？
我們用N代表書的總數(shù)，F(xiàn)(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;
    }

}

運行結(jié)果如下：

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