《编程之美》买书问题

摘要：编程之美有一道很有趣的题目买书问题，题目的内容如下上柜的哈利波特平装本系列，一共有五卷。假设具体折扣的情况如下本数折扣本数折扣本数折扣本数折扣设计出算法，能够计算出读者所购买的一批书的最低价格。列出公式购买的书里，其中有五卷享受到了折扣。

《编程之美》有一道很有趣的题目：买书问题，题目的内容如下：
上柜的《哈利波特》平装本系列，一共有五卷。假设每一卷多带带销售均需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