买书问题 - 编程之美1.4

买书问题 - 编程之美1.4
上柜的《哈利波特》平装本系列，一共有五卷。假设每一卷单独销售均需8欧元。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：

        本数    2       折扣   5%

        本数    3       折扣  10%

        本数    4       折扣  20%

        本数    5       折扣  25% 

买书的需求一定，但通过不同的买书组合，能买到不同的折扣。

问题：设计出算法，能够计算出读者所购买的一批书的最低价格。

动态规划

        五卷书的价格相同都是8欧元，所以购买（1，0，0，0，0）跟（0，1，0，0，0）效果一样。这里就可以简化为，让所购买书按照本书递增（递减），从而方便讨论。

         要处理的参数为购买每种卷的个数，所以递归一定跟这五个参数相关。可以把参数按照从小到大顺序排列。讨论不为0的参数的个数，从而求出所有可能的折扣种类。然后从当前折扣种类中取价格最小值。

状态转移方程： 

                           （X1,X2,X3,X4,X5）代表购买每卷的个数，F（X1，X2，X3，X4，X5）代表最低价格。其中，X1 < X2 < X3 < X4 < X5

                            F（X1，X2，X3，X4，X5）=0  ；当所有参数都为0的情况（这也是退出递归的出口）

              F（X1，X2，X3，X4，X5）= min{

                    5*8*(1-25%) +F（X1-1，X2-1，X3-1，X4-1，X5-1） //参数全部  > 0

                    4*8*(1-20%) +F（X1，X2-1，X3-1，X4-1，X5-1）    //x2 > 0

                    3*8*(1-10%) +F（X1，X2，X3-1，X4-1，X5-1）       //x3 > 0

                    2*8*(1-5%) +F（X1，X2，X3，X4-1，X5-1）            //x4 > 0

                   8 +F（X1，X2，X3，X4，X5-1）                                 //x5 > 0

             }

1. double BestBuy(int x1, int x2, int x3, int x4, int x5)  
2. {  
3.     countRE++;  
4.     int i;  
5.     int n[5] ={ x1, x2, x3, x4, x5 };  
6.     reRank(n,5);  
7.     x1=n[0];  
8.     x2=n[1];  
9.     x3=n[2];  
10.     x4=n[3];  
11.     x5=n[4];  
12.     if(S[x1][x2][x3][x4][x5]>0) return S[x1][x2][x3][x4][x5];  
13.     countDP++;  
14.     /* x1 < x2 < x3 < x4  < x5*/   
15.     if (n[0]>0)  
16.     {  
17.         double solution = findMin( 8+BestBuy(x1, x2, x3, x4, x5 - 1),  
18.             2 * 8 * 0.95 + BestBuy(x1, x2, x3, x4 - 1, x5 - 1),  
19.             3 * 8 *0.9 + BestBuy(x1, x2, x3-1, x4 - 1, x5 - 1),  
20.             4 * 8 * 0.8 + BestBuy(x1, x2 - 1, x3 - 1, x4 - 1, x5 - 1),   
21.             5 * 8 * 0.75 + BestBuy(x1-1, x2 - 1, x3 - 1, x4 - 1, x5 - 1) );  
22.         S[x1][x2][x3][x4][x5] = solution;  
23.         return solution;  
24.     }  
25.     else if ((n[0] == 0) && (n[1] > 0))   
26.     {  
27.         double solution = findMin( 8+BestBuy(x1, x2, x3, x4, x5 - 1),  
28.             2 * 8 * 0.95 + BestBuy(x1, x2, x3, x4 - 1, x5 - 1),  
29.             3 * 8 *0.9 + BestBuy(x1, x2, x3-1, x4 - 1, x5 - 1),  
30.             4 * 8 * 0.8 + BestBuy(x1, x2 - 1, x3 - 1, x4 - 1, x5 - 1), large );  
31.         S[x1][x2][x3][x4][x5] = solution;  
32.         return solution;  
33.     }  
34.     else if ((n[0] == 0) && (n[1] == 0) &&(n[2]>0))   
35.     {  
36.         double solution = findMin( 8+BestBuy(x1, x2, x3, x4, x5 - 1),  
37.             2 * 8 * 0.95 + BestBuy(x1, x2, x3, x4 - 1, x5 - 1),  
38.             3 * 8 *0.9 + BestBuy(x1, x2, x3-1, x4 - 1, x5 - 1), large, large );  
39.         S[x1][x2][x3][x4][x5] = solution;  
40.         return solution;  
41.     }  
42.     else if ((n[0] == 0) && (n[1] == 0) && (n[2] == 0) && (n[3] > 0))   
43.     {  
44.         double solution = findMin( 8+BestBuy(x1, x2, x3, x4, x5 - 1),  
45.             2 * 8 * 0.95 + BestBuy(x1, x2, x3, x4 - 1, x5 - 1), large, large, large );  
46.         S[x1][x2][x3][x4][x5] = solution;  
47.         return solution;  
48.     }  
49.     else if ((n[0] == 0) && (n[1] == 0) && (n[2] == 0) && (n[3] == 0) && (n[4] > 0))   
50.     {  
51.         double solution = 8.0 + BestBuy(x1, x2, x3, x4, x5 - 1);   
52.         S[x1][x2][x3][x4][x5] = solution;  
53.         return solution;  
54.     }  
55.     else  
56.     {  
57.         S[x1][x2][x3][x4][x5] =0;  
58.         return 0;  
59.     }  
60. } 

1.     cout<<BestBuy(a[0],a[1],a[2],a[3],a[4])<<endl;  

《编程之美》读书笔记(四)：卖书折扣问题的贪心解法
1 本次选择的书的数量不应该小于下一次可选择的书的最大数量（其中，书的取法按照书中动态规划方法给出的选法来进行）。
2 每一次选择之前都应该查表，选择其中使得近两次折扣数最大的那个作为本次选择（因为我们使得本次选择的影响被控制在两次选择的范围内）

http://bylijinnan.iteye.com/blog/1574941

1.     public double findMinCost(int Y1,int Y2,int Y3,int Y4,int Y5){  
2.         int[] x={Y1,Y2,Y3,Y4,Y5};  
3.         Arrays.sort(x);  
4.         if(x[0]<0){  
5.             System.out.println("购书数量不能为负数");  
6.             return 0;  
7.         }  
8.         //Y1>=Y2>=Y3>=Y4>=Y5  
9.         Y5=x[0];  
10.         Y4=x[1];  
11.         Y3=x[2];  
12.         Y2=x[3];  
13.         Y1=x[4];  
14.         double cost=0;  
15.         if(Y5>=1){  
16.             cost=min(  
17.                     8*5*(1-0.25)+findMinCost(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1),  
18.                     8*4*(1-0.20)+findMinCost(Y1-1,Y2-1,Y3-1,Y4-1,Y5),  
19.                     8*3*(1-0.10)+findMinCost(Y1-1,Y2-1,Y3-1,Y4,Y5),  
20.                     8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)  
21.                 );  
22.         }else if(Y4>=1){  
23.             cost=min(  
24.                     8*4*(1-0.20)+findMinCost(Y1-1,Y2-1,Y3-1,Y4-1,Y5),  
25.                     8*3*(1-0.10)+findMinCost(Y1-1,Y2-1,Y3-1,Y4,Y5),  
26.                     8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)  
27.                 );  
28.         }else if(Y3>=1){  
29.             cost=min(  
30.                     8*3*(1-0.10)+findMinCost(Y1-1,Y2-1,Y3-1,Y4,Y5),  
31.                     8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)  
32.                 );  
33.         }else if(Y2>=1){  
34.             cost=min(  
35.                     8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)  
36.                 );  
37.         }else if(Y1>=1){//{Y1,0,0,0,0},说明买的是同一卷书，没有折扣  
38.             cost=8*Y1;  
39.         }else{//{0,0,0,0,0}  
40.             cost=0;  
41.         }  
42.         return cost;  
43.     }  

Read full article from 每日一题(18)——买书问题（动态规划） - 小熊不去实验室 - 博客频道 - CSDN.NET