買書問題
題目：
在節假日的時候，書店一般都會做促銷活動。由于《哈利波特》系列相當暢銷，店長決定通過促銷活動來回饋讀者。上櫃的《哈利波特》平裝書系列中，一共有五卷。假設每一卷單獨銷售均需8歐元。如果讀者一次購買不同的兩卷，就可以扣除5%的費用，三卷則更多，假設具體折扣的情況如下：
本數
折扣
2
5%
3
10%
4
20%
5
25%
在一份訂單中，根據購買的卷數及本數，就會出現可以應用不同折扣規則的情況。但是，一本書隻會應用一個折扣規則。比如，讀者一共買了兩本卷一，一本卷二。那麼，可以享受5%的折扣。另外一本卷一則不能享受折扣。如果有多種折扣，希望計算出的總額盡可能的低。
要求根據以上需求，設計出算法，能夠計算出讀者所購買一批書的最低價格。
思路：
1. 用動态規劃首先需找到遞歸公式，因為動态規劃是由頂向下遞歸的，自頂向下求解，根據底層結果得到最終解。
2. 5卷數的價格相同，如果用x1...x5對應1~5卷書的本數，F(x1,x2,x3,x4,x5)表費用，那F(x1,x2,x3,x4,x5)=F(x2,x1,x3,x4,x5)，根據排列組合，就有5!種表示方法，是以沒有必要區分不同的卷，可以讓書本按遞減(或遞增)來表示，(Y1,Y2,Y3,Y4,Y5)是x1,x2,x3,x4,x5的重排列，Y1>=Y2>=Y3>=Y4>=Y5。
3. 遞歸公式：
F(Y1,Y2,Y3,Y4,Y5)
=0 (當Y1=Y2=Y3=Y4=Y5=0)
=min{
5*8*(1-0.25)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1)， (當Y5>=0)
4*8*(1-0.20)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5)， (當Y4>=0)
3*8*(1-0.10)+F(Y1-1,Y2-1,Y3-1,y4,Y5)， (當Y3>=0)
2*8*(1-0.05)+F(Y1-1,Y2-1,Y3,Y4,Y5)， (當Y2>=0)
8+F(y1-1,y2,y3,y4,y5)， (當Y1>=0)
}
實作：
#include#include#define n 5
#define INF 9999
using namespace std;
double min5(double a,double b,double c,double d,double e)//求5個double數的最小值
{
return min(min(min(a,b),min(c,d)),e);
}
double F(int y1,int y2,int y3,int y4,int y5)//遞歸實作動态規劃
{
if(y1+y2+y3+y4+y5==0)return 0;//遞歸出口
//排序
int p[5]={y1,y2,y3,y4,y5};
sort(p,p+5,[](int a,int b){
return a=1)t5=5*8*(1-0.25)+F(y1-1,y2-1,y3-1,y4-1,y5-1);
if(y4>=1)t4=4*8*(1-0.20)+F(y1-1,y2-1,y3-1,y4-1,y5);
if(y3>=1)t3=3*8*(1-0.10)+F(y1-1,y2-1,y3-1,y4,y5);
if(y2>=1)t2=2*8*(1-0.05)+F(y1-1,y2-1,y3,y4,y5);
if(y1>=1)t1=8+F(y1-1,y2,y3,y4,y5);
//cout<>x[i];
}
sort(x,x+n,[](int a,int b){
return a