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(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>=1F(Y1, Y2, Y3, Y4, Y5) = 0 \quad if(Y1 = Y2 = Y3 = Y4 = Y5=0) \\ F(Y1, Y2, Y3, Y4, Y5) = min{\begin{cases} & x = 5 * 8 * (1 - 0.25) + F(Y1 - 1, Y2 - 1, Y3 - 1, Y4 - 1, Y5 - 1) \text { \quad if } Y5>= 1\\ & x = 4 * 8 * (1 - 0.2) + F(Y1 - 1, Y2 - 1, Y3 - 1, Y4 - 1, Y5) \text { \quad if } Y4>= 1\\ & x = 3 * 8 * (1 - 0.1) + F(Y1 - 1, Y2 - 1, Y3 - 1, Y4, Y5) \text {\quad if } Y3>= 1\\ & x = 2 * 8 * (1 - 0.05) + F(Y1 - 1, Y2 - 1, Y3, Y4, Y5)\text { \quad if } Y2>= 1\\ & x = 1 * 8 + F(Y1 - 1, Y2, Y3, Y4, Y5)\text { \quad if } Y1>= 1 \end{cases}} 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));}
}

时间复杂度

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

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