题目:
在 节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中，一共有五 卷，用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：
本数折扣25%310%420%525%在一份订单中，根据购买的卷数以及本书，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望能够计算出的总额尽可能的低。要求根据这样的需求，设计出算法，能够计算出读者所购买一批书的最低价格。
分析:
首先假设五册书分别为A,B,C,D,E,不失一般性可以假设Na>=Nb>=Nc>=Nd>=Ne
设所有书可以划分为k组,每组中书不重复,
则在最优解中有如下性质:
1 所有只包含一本书的组均只包含同一本书
若有两组包含一本书的组包含的书不同,则这两组合并,能得到更优解,与最优解矛盾.
2包含一本书的组只包含A
若包含书为A',若Na'==Na,则A,A'对调即可
若Na'<Na,则必存在某组包含A不包含A',则将只包含A'的组并入该组能得到更优解
3所有只包含两本书的组均包含相同两本书
组(A', B'), (A',C')折扣0.2重组为(A',B',C')与(A)折扣0.3
4包含两本书的组必包含A
若存在包含一本A的组,而两本书的组不包含A,则合并能得更优解
若不存在包含一本A的组,而两本书组包含为A',A'',则包含三本书,四本组必含A而缺A'者
(A', A''), (AXY), 折扣0.4不如(A''),(AXYA')0.8
(A',A''),(AXYZ)折扣0.9不如(A''),(AXYZA')1.25
5 包含两本书的组必包含B
同上证
6所有只包含三本书的组均包含相同三本书
(A,B,C),(A,B,D)折扣0.6,(A,B),(A,B,C,D)折扣0.9
7所有包含三本书的组均包含A
若存在只包含A的组,合并得更优
若存在只包含A, B的组(A,B)(XYZ)折扣0.4,不如(B)(AXYZ)折扣0.8
若不存在一,二本组,假设三本书组为(X,Y,Z),则必有包含A的四本组缺X,(X,Y,Z)(A,A',A'',A''')折扣1.1,不如
(Y,Z),(A,A',A'',A''',X)折扣1.35
8所有包含三本的组均包含B,C
同上可证
9所有包含四本书的组均包含A,B,C
设XYZW为
(ABC)(BCDE)折扣1.1,不如(B,C),(A,B,C,D,E)折扣1.35
其它情况同理可证
10包含五本书与包含三本书情况不会同时出现
(A,B,C),(A,B,C,D,E)折扣1.55,不如(A,B,C,D),(A,B,C,E)折扣1.6
由以上证明可得如下结论
每组均包含A,所有组数与A相同所有包含两本及以上的组均包含B,组数与B同所有包含三本及以上的组均包含C,组数与C同三,五不并存
由此可得解法如下:
代码constdoubleBuyBook::UNIT_PRICE=8;
constdoubleBuyBook::DISCOUNTS[5]={1,0.95,0.9,0.8,0.75};
staticconstintBOOK_KINDS=5;
doubleBuyBook::SearchFast(int*books)
{
Sort(books);
intg[5];
g[0]=books[0]-books[1];
g[1]=books[1]-books[2];
g[2]=books[2]-books[3];
g[3]=books[3]-books[4];
g[4]=books[4];
intt=min(g[2],g[4]);
if(t>0)
{
g[2]-=t;
g[4]-=t;
g[3]+=2*t;
}
doublesum=0;
for(inti=0;i<BOOK_KINDS;++i)
{
sum+=g[i]*(i+1)*UNIT_PRICE*DISCOUNTS[i];
}
returnsum;
}
