1.4 买书问题
题目描述:
在 节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五 卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。
如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下:
本数 折扣
2 5%
3 10%
4 20%
5 25%
在一份订单中,根据购买的卷数以及本书,就会出现可以应用不同折扣规则的情况。
但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。
那么,可以享受到5%的折扣。另外一本卷一则不能享受折扣。
如果有多种折扣,希望能够计算出的总额尽可能的低。
要求根据这样的需求,设计出算法,能够计算出读者所购买一批书的最低价格。
解法一:贪心策略
当书的数目N
当书的数目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
}