编程之美1 哈利波特买书问题

Tag：贪心；动态规划

题目

《哈利波特》系列一共有五卷，假设每一卷单独销售均需8欧元。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：
本数 2 折扣 5%
本数 3 折扣 10%
本数 4 折扣 20%
本数 5 折扣 25%
在一份订单中，根据购买的卷数及本数，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一、一本卷二。那么可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望计算出的总额尽可能的低。

需要根据以上需求，设计出算法，能够计算出读者所购买的一批书的最低价格。

思路与算法

方法一

先考虑贪心算法，如果每次选最大的折扣，是否总折扣就是最大的呢？可以列一个表格先计算1-5本（假设都能获得最大折扣，即买的都是不同卷的书籍）：

可以看到在5本之内都是选择最大的折扣，那如果继续计算也是这样的结果吗？

可以发现，在本数=8时，贪心使用最大的折扣并不能获得最大的优惠，所以，我们可以把所有的本数分解为10以内的来解决。

方法二

可以使用动态规划的方式来解决：
假设（Y1,Y2,Y3,Y4,Y5),其中Yn表示购买第n卷书的数量，Y1,Y2,Y3,Y4,Y5是购买第1,2,3,4,5卷书数量的重排列，满足Y1>=Y2>=Y3>=Y4>=Y5，用F(Y1,Y2,Y3,Y4,Y5)表示买书的最大折扣，则：
F ( Y 1 , Y 2 , Y 3 , Y 4 , Y 5 ) = 0 i f ( Y 1 = Y 2 = Y 3 = Y 4 = Y 5 = 0 ) F ( Y 1 , Y 2 , Y 3 , Y 4 , Y 5 ) = m i n { x = 5 ∗ 8 ∗ ( 1 − 0.25 ) + F ( Y 1 − 1 , Y 2 − 1 , Y 3 − 1 , Y 4 − 1 , Y 5 − 1 )   if  Y 5 > = 1 x = 4 ∗ 8 ∗ ( 1 − 0.2 ) + F ( Y 1 − 1 , Y 2 − 1 , Y 3 − 1 , Y 4 − 1 , Y 5 )   if  Y 4 > = 1 x = 3 ∗ 8 ∗ ( 1 − 0.1 ) + F ( Y 1 − 1 , Y 2 − 1 , Y 3 − 1 , Y 4 , Y 5 ) if  Y 3 > = 1 x = 2 ∗ 8 ∗ ( 1 − 0.05 ) + F ( Y 1 − 1 , Y 2 − 1 , Y 3 , Y 4 , Y 5 )   if  Y 2 > = 1 x = 1 ∗ 8 + F ( Y 1 − 1 , Y 2 , Y 3 , Y 4 , Y 5 )   if  Y 1 > = 1 F(Y1, Y2, Y3, Y4, Y5) = 0 \quad if(Y1 = Y2 = Y3 = Y4 = Y5=0) \\ F(Y1, Y2, Y3, Y4, Y5) = min{

} F(Y1,Y2,Y3,Y4,Y5)=0if(Y1=Y2=Y3=Y4=Y5=0)F(Y1,Y2,Y3,Y4,Y5)=min⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​​x=5∗8∗(1−0.25)+F(Y1−1,Y2−1,Y3−1,Y4−1,Y5−1) if Y5>=1x=4∗8∗(1−0.2)+F(Y1−1,Y2−1,Y3−1,Y4−1,Y5) if Y4>=1x=3∗8∗(1−0.1)+F(Y1−1,Y2−1,Y3−1,Y4,Y5)if Y3>=1x=2∗8∗(1−0.05)+F(Y1−1,Y2−1,Y3,Y4,Y5) if Y2>=1x=1∗8+F(Y1−1,Y2,Y3,Y4,Y5) if Y1>=1​

代码

package arithmetic;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Main {

    // 贪心算法
    private static double discount1(double number) {
        switch((int) number) {
            case 0:
                return 0;
            case 1:
                return 8;
            case 2:
                return 8 * 2 * (1 - 0.05);
            case 3:
                return 8 * 3 * (1 - 0.1);
            case 4:
                return 8 * 4 * (1 - 0.2);
            case 5:
                return 8 * 5 * (1 - 0.25);
            default:
                // 当本数为8时的最优策略是4 + 4 本分配
                if(number % 5 == 3){
                    return 8 * 4 * (1 - 0.2) * 2 + discount1(number - 8);
                } else {
                    return 8 * 5 * (1 - 0.25) + discount1(number - 5);
                }
        }
    }

    // 动态规划

    private static void rerank(double[] n, int length) {
        double temp;
        int i = length - 1;
        for(; i > 0; i--) {
            for(int j = 0; j < i; j++) {
                if(n[j] < n[j + 1]) {
                    temp = n[j];
                    n[j] = n[j + 1];
                    n[j + 1] = temp;
                }
            }
        }
    }

    private static double MAX_VALUE = 12138;
    private static double min(double x1, double x2, double x3, double x4, double x5) {
        double[] n = {x1, x2, x3, x4, x5};
        rerank(n, 5);
        return n[4];
    }

    private static double discount2(double x1, double x2, double x3, double x4, double x5){
        double[] n =  {x1,x2,x3,x4,x5};
        rerank(n, 5);
        if(n[4] > 0) {
            return min(5 * 8 * (1 - 0.25) + discount2(n[0] - 1, n[1] - 1, n[2] - 1, n[3] - 1, n[4] - 1),
                    4 * 8 * (1 - 0.2) + discount2(n[0] - 1, n[1] - 1, n[2] - 1, n[3] - 1, n[4]),
                    3 * 8 * (1 - 0.1) + discount2(n[0] - 1, n[1] - 1, n[2] - 1, n[3], n[4]),
                    2 * 8 * (1 - 0.05) + discount2(n[0] - 1, n[1] - 1, n[2], n[3], n[4]),
                    8 + discount2(n[0] - 1, n[1] , n[2], n[3], n[4])
            );
        } else if(n[4] == 0 && n[3] > 0) {
            return min(MAX_VALUE,
                    4 * 8 * (1 - 0.2) + discount2(n[0] - 1, n[1] - 1, n[2] - 1, n[3] - 1, n[4]),
                    3 * 8 * (1 - 0.1) + discount2(n[0] - 1, n[1] - 1, n[2] - 1, n[3], n[4]),
                    2 * 8 * (1 - 0.05) + discount2(n[0] - 1, n[1] - 1, n[2], n[3], n[4]),
                    8 + discount2(n[0] - 1, n[1] , n[2], n[3], n[4])
            );
        } else if(n[4] == 0 && n[3] == 0 && n[2] > 0) {
            return min(MAX_VALUE, MAX_VALUE,
                    3 * 8 * (1 - 0.1) + discount2(n[0] - 1, n[1] - 1, n[2] - 1, n[3], n[4]),
                    2 * 8 * (1 - 0.05) + discount2(n[0] - 1, n[1] - 1, n[2], n[3], n[4]),
                    8 + discount2(n[0] - 1, n[1] , n[2], n[3], n[4])
            );
        } else if(n[4] == 0 && n[3] == 0 && n[2] == 0 && n[1] > 0) {
            return min(MAX_VALUE, MAX_VALUE, MAX_VALUE,
                    2 * 8 * (1 - 0.05) + discount2(n[0] - 1, n[1] - 1, n[2], n[3], n[4]),
                    8 + discount2(n[0] - 1, n[1] , n[2], n[3], n[4])
            );
        } else if(n[4] == 0 && n[3] == 0 && n[2] == 0 && n[1] == 0 && n[0] > 0) {
            return min(MAX_VALUE, MAX_VALUE, MAX_VALUE, MAX_VALUE,
                    8 + discount2(n[0] - 1, n[1] , n[2], n[3], n[4])
            );
        } else {
            return 0;
        }
    }
    public static void main(String[] args) {
        System.out.println(discount2(2, 3, 4, 5, 6));
        System.out.println(discount1(12));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

时间复杂度

贪心算法：O(n)
动态规划：O(Y1 * Y2 * Y3 * Y4 * Y5)

不过这两种方法的输入是不一样的，我暂时还没想好贪心法如果输入是每种书的购买数量该怎么做