1.4 买书问题
题目描述：
在 节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中，一共有五 卷，用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。
如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：
本数 折扣
2 5%
3 10%
4 20%
5 25%
在一份订单中，根据购买的卷数以及本书，就会出现可以应用不同折扣规则的情况。
但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。
那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。
如果有多种折扣，希望能够计算出的总额尽可能的低。
要求根据这样的需求，设计出算法，能够计算出读者所购买一批书的最低价格。
解法一：贪心策略
当书的数目N<5时，直接按照折扣购买
当书的数目N>5时，按最大折扣购买；
情况如下：
先找出是所有书中5种不同的书，如果有则按照5本书折扣价购买
其次找出剩余书中所有4种书，如果有则按照4本书的折扣价购买
再找出剩余书中所有3种书，如果有则按照3本书的折扣价购买
最后在剩余书中找出所有2种书，如果有则按照2本书的折扣价购买
剩下的书则按照全价购买。
如果按照这种方法（贪心法）存在反例，
比如买8本书时，可以拆成5+3，折扣为1.55；
也可以拆成4+4，折扣为1.6
这种两种情况组合中都包括，通过选择一个折扣最低的可以排除掉第一种情况。
结论：贪心策略不可取
解法二：动态规划
五卷书的价格相同都是8欧元，所以购买（1，2，3，5，4）跟（5，4，3，2，1）相同。
让所购买书按照本书递减讨论。
（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） //X5>=1
4*8*(1-20%) +F（X1-1，X2-1，X3-1，X4-1，X5） //x4>=1
3*8*(1-10%) +F（X1-1，X2-1，X3-1，X4，X5） //x3>=1
2*8*(1-5%) +F（X1-1，X2-1，X3，X4，X） //x2>=1
8 +F（X1-1，X2，X3，X4，X5） //x1>=1
}
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX=100000000;//定义一个最大值，相当于取最小值时忽略这个位置的值
bool cmp(double a,double b)
{
return a>b;
}
double Min(double a, double b, double c, double d, double e)//返回最小值
{
double nn[5]={a,b,c,d,e};
sort(nn,nn+5,cmp);//从大到小排序
return nn[4];
}
double f(int x1,int x2,int x3,int x4,int x5)//动态规划
{
int n[5]={x1,x2,x3,x4,x5};
sort(n,n+5,cmp);//从大到小排序
x1=n[0];x2=n[1];x3=n[2];x4=n[3];x5=n[4];
if (x5>=1)
{
return Min(
8.0+f(x1-1,x2,x3,x4,x5),
2*8*0.95+f(x1-1,x2-1,x3,x4,x5),
3*8*0.9+f(x1-1,x2-1,x3-1,x4,x5),
4*8*0.8+f(x1-1,x2-1,x3-1,x4-1,x5),
5*8*0.75+f(x1-1,x2-1,x3-1,x4-1,x5-1));
}
else if (x4>=1)
{
return Min(
8.0+f(x1-1,x2,x3,x4,x5),
2*8*0.95+f(x1-1,x2-1,x3,x4,x5),
3*8*0.9+f(x1-1,x2-1,x3-1,x4,x5),
4*8*0.8+f(x1-1,x2-1,x3-1,x4-1,x5),
MAX);
}
else if (x3>=1)
{
return Min(
8.0+f(x1-1,x2,x3,x4,x5),
2*8*0.95+f(x1-1,x2-1,x3,x4,x5),
3*8*0.9+f(x1-1,x2-1,x3-1,x4,x5),
MAX,MAX);
}
else if (x2>=1)
{
return Min(
8.0+f(x1-1,x2,x3,x4,x5),
2*8*0.95+f(x1-1,x2-1,x3,x4,x5),
MAX,MAX,MAX);
}
else if (x1>=1)
{
return 8.0+f(x1-1,x2,x3,x4,x5);
}
else//都为0
{
return 0;
}
}
int main()
{
//int n1[5] = {3,4,2,1,0};
int n1[5] = {2,2,2,1,1};
//5+3=5*8*0.75+3*8*0.9=51.6
//4+4=4*8*0.8+4*8*0.8=51.2
double solution =f(n1[0],n1[1],n1[2],n1[3],n1[4]);
cout<<"所花费的最少的钱为："<<solution<<endl;
}