1.4 买书问题

在节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。上柜的《哈利波特》平装本系列中，一共有五卷。假设每一卷单独销售均需8欧元1。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下。

在一份订单中，根据购买的卷数及本数，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望计算出的总额尽可能的低。

要求根据以上需求，设计出算法，能够计算出读者所购买一批书的最低价格。

分析与解法

怎么购买比较省钱呢？第一个感觉，当然是优先考虑最大折扣，然后次之。

这的确是一个有效的办法。但这个算法是不是最省钱的呢？我们直接分析可能的拆解方式，来看看算法的可行性。

比如对于两本不同卷的书，最多只能享受到2×5%=0.1的折扣。

对于三本不同卷的书，可以按照3卷的折扣或按照2卷+1卷的折扣。折扣额度分别为3×10%=0.3或者2×5%+1×0%=0.1。

基于这样的推算，除去所有不能享受折扣的组合（比如把三卷不同的书拆成三个一本来买，就不能享受任何折扣），可以得出如下的折扣表。

对于总数为10本以上的情况，都可以分解成为表1-1中所存在的组合。从表1-1中可以看到加粗的地方违反了贪心的规则。当我们要买8本书时，比如说买两本第一卷，两本第二卷，两本第三卷，一本第四卷，一本第五卷，其序列为（2,2,2,1,1）。

按照优先考虑最大折扣的策略，即选择5+3，购买序列为（1,1,1,1,1）和（1,1,1,0,0）。我们先买每卷各一本，花去5×8×（1-25%）=30，再买第一、二、三卷，花去3×8×（1-10%）=21.6，共计51.6欧元。但是如果我们换一个策略，即选择4+4，购买序列为（1,1,1,1,0）及（1,1,1,0,1）。先买第一、二、三、四卷，然后再买第一、二、三、五卷，那么总共花去2×4×8×（1-20%）=51.2欧元。

因此，针对这个问题试图用贪心策略行不通。

解法一

那么，有可能改进贪心算法，从而得到一个可行的方案吗？

从表1-1中可以看出，该贪心策略会在买5+3本的时候出错。因为根据贪心算法所推荐的5+3的购买方式，没有4+4购买方式的折扣大。

回过头对比一下。

在小于5本的情况下，直接按折扣买就好了。

这些用贪心算法都是适用的。

那么如果大于5本呢？由于折扣的规则仅针对2到5本的情况，那么选择两次扣除的最大的组合数为每次5本，最多为10本。对于10本以上理论上都能拆解为表1-1中出现的组合。

因此，暂时先来研究总数在10本以内的情况。如果要买的书为（Y1, Y2, Y3, Y4, Y5）（其中Y1＞=Y2＞=Y3＞=Y4＞=Y5），贪心策略建议我们Y5次5卷，（Y4-Y5）次4卷，（Y3-Y4）次3卷，（Y2-Y3）次2卷和（Y1-Y2）次1卷。

根据表1-1中出现的反例，必须做相应的调整。即考虑把5+3的组合都变成为4+4的组合（这样的调整总是可行的吗？）。因此，把K次5卷和K次3卷重新组合成2×K次4卷（K=min{Y5, Y3-Y4}）。结果就是应该购买（Y5-K）次5卷，（Y4-Y5+2K）次4卷，（Y3-Y4-K）次3卷，（Y2-Y3）次2卷和（Y1-Y2）次1卷（K=min{Y5, Y3-Y4}）。

比如要买2本第一卷，2本第二卷，1本第三卷，1本第四卷和3本第五卷，像前面所说的，我们要买的书可以用（3,2,2,1,1）表示。在新的贪心策略下，K=min{Y5, Y3-Y4}=min{1,1}=1。那么购买各种卷数的数量为

5种不同卷Y5-K=1-1=0

4种不同卷Y4-Y5+2K=1-1+2=2

3种不同卷Y3-Y4-K=2-1-1=0

2种不同卷Y2-Y3=2-2=0

1种不同卷Y1-Y2=3-2=1

具体组合信息如下。

那么，对于10本以上的情况，仍然有可能基于调整的贪心算法思路做应用吗？

第一种可能：

比如说，可以考虑把任意多组数据都分解为10以内的情况。考虑对大于10本的情况提出如下假设：

假设在分解的过程中，可以找到如下一种分法：可以把10本以上的书籍分成小于10的多组（X11,X12,X13,X14,X15）,（X21,X22,X23,X24,X25）…（Xn1,Xn2,Xn3,Xn4,Xn5），并且使得只要把每组的最优解相加，就可以得到全局的最优解。

这样就可以应用以上的修改方法来进行计算，从而得到最优解。

那么这种分法是正确的吗？有办法证明或者找到反例吗？

第二种可能：

对于适用贪心算法的情况来讲，最重要的原则就是做出当前最好的选择，而不考虑整体最优。那么，如果我们考虑在贪心算法的选择上做些文章，把贪心算法的选择思路做进一步扩充，结果会不会更好呢？

既然依然沿着贪心选择的思路来走，那么，在对任意一组数据的分解上来看，依然考虑按照最大的分法进行组合。

比如给定一个序列（7,6,5,3,2），根据贪心算法，势必会分成如下组合。

根据表1-1出现的反例，直接按照贪心算法分解会得到错误的结果。那么，是否有可能约束使做当前选择时，仅仅往前面多考虑一步，根据下一步的情况来决定当前的选择呢？

比如说，当前理论上应该选择5，但是由于下面有4或者3的组合，那么应该把5+3的组合拆分为4+4的组合。

很快地，我们会发现，当前给出的例子第一次选择5之后，下一步仍然选择5，也就是说我们很难仅仅根据多考虑一步的情况来做出正确选择，从而得到最优解。

如果换个思路呢？比如根据贪心算法计算出一个表，如表1-3，直接套用总数为10本以下的调整方法，找出所有违反贪心算法的反例，直接进行调整（如把所有5+3的组合改变成为4+4的组合）呢？这样是否可以充分利用贪心算法的便捷，同时又对其不足和反例进行调整？

比如，对于当前序列（7,6,5,3,2），贪心的结果是5+5+4+3+3+2+1的组合，调整之后会成为4+4+4+4+4+2+1的组合。这个看起来是正确的。

那么，有办法证明查表法是正确的吗？

解法二

经过多次努力，我们很难证明贪心算法，甚至是找到一个合适的改进过的贪心算法。那么，还有什么办法吗？似乎只能使用动态规划法了。

首先，在使用动态规划之前，得考虑怎么表达购买中间出现的状态。假设我们用Xn来表示购买第n卷书籍的数量。如果要买X1本第一卷，X2本第二卷，X3本第三卷，X4本第四卷，X5本第五卷，那么我们可以用（X1, X2, X3, X4, X5）表示，而F（X1, X2, X3, X4, X5）表示我们要买这些书需要的最少花费。

如果我们要买X3本第一卷，X2本第二卷，X1本第三卷，X4本第四卷，X5本第五卷呢？是否需要用F（X3, X2, X1, X4, X5）来表示呢？其实不难看出，因为各卷的价格一样，需要的最少花费仍然等于F（X1, X2, X3, X4, X5）。也就是说，F（X1, X2, X3, X4, X5）等价于F（X3, X2, X1, X4, X5）。因此我们没有必要区分不同的卷。那么对于所有跟（X1, X2, X3, X4, X5）等价的情况，我们用什么来表示呢？F（X1, X2, X3, X4, X5）还是F（X1, X2, X3, X5, X4），还是……

根据排列组合的规则，最多有5！种可选择的表示方法，我们可以选择一种特别的表示（Y1, Y2, Y3, Y4, Y5）（其中，Yn用来表示购买第n卷书籍的数量，Y1, Y2, Y3, Y4, Y5是X1, X2, X3, X4, X5的重新排列，满足Y1≥Y2≥Y3≥Y4≥Y5），我们称它为所有跟（X1, X2, X3, X4, X5）等价的情况的“最小表示”。

接下来，就需要考虑怎么把一个大问题转化为小一点的问题。

假定要买的书为（Y1, Y2, Y3, Y4, Y5）。如果第一次考虑为5本不同卷付钱（当然这里需要保证Y5>=1），那么剩下还要再付钱的书集合为（Y1-1, Y2-1, Y3-1, Y4-1, Y5-1）。显然，如果一次买5本书，我们没有其他的选择。

如果第一次考虑买4本不同卷（Y4>=1）那么我们就有如下可能的买书集合。

（Y1-1, Y2-1, Y3-1, Y4-1, Y5）

（Y1-1, Y2-1, Y3-1, Y4, Y5-1）

（Y1-1, Y2-1, Y3, Y4-1, Y5-1）

（Y1-1, Y2, Y3-1, Y4-1, Y5-1）

（Y1, Y2-1, Y3-1, Y4-1, Y5-1）

根据题意，不同卷的书组合起来才能享受折扣，至于具体是哪几卷，并没有要求。但是，问题在于，应该如何选择一种组合来继续分解下去呢？

凭直觉来看，选择（Y1-1, Y2-1, Y3-1, Y4-1, Y5）的组合能够留下最多的后续组合。因为Y1≥Y2≥Y3≥Y4≥Y5。比如对于（2,2,2,2,1）这样的卷数组合来说，选择扣除（1,1,1,1,0）之后，留下的组合为（1,1,1,1,1）还可以做一次基于5本书的折扣。但是如果选择扣除（1,1,1,0,1）之后，留下的组合是（1,1,1,2,0）。后续只能分解为（1,1,1,1,0）和（0,0,0,1,0）。那么，是否能够证明（Y1-1, Y2-1, Y3-1, Y4-1, Y5）就是最好的组合呢？

可以做如下的假设，假设在（Y1, Y2, Y3, Y4, Y5）的情况下选择扣除（1,1,1,0,1）得到了最优解。此时，剩下的组合为（Y1-1, Y2-1, Y3-1, Y4, Y5-1）。

在此基础上，如果能够证明在扣除（1,1,1,1,0）之后，剩下组合为（Y1-1, Y2-1, Y3-1, Y4-1, Y5）的情况下也能得到最优解，那么，可以认为每次都按照（1,1,1,1,0）的扣除方式可以代表后续的所有组合。

从选择扣除4本书的组合来看，目前的选择扣除为（1,1,1,0,1），由于Y4≥Y5，那么，显然在（Y1-1, Y2-1, Y3-1, Y4, Y5-1）的组合中，Y4>Y5-1。则在（Y1-1, Y2-1, Y3-1, Y4, Y5-1）的所有最优解中，一定存在某些组合仅有Y4而没有Y5。

举例来说明。

假设Y1=Y2=Y3=Y4=Y5=2。

选择（1,1,1,1,0），剩下（Y1-1, Y2-1, Y3-1, Y4-1, Y5）的组合为（1,1,1,1,2），剩下的书序号集合为{1,2,3,4,5,5}。

选择（1,1,1,0,1），剩下（Y1-1, Y2-1, Y3-1, Y4, Y5-1）的组合为（1,1,1,2,1），剩下的书序号集合为{1,2,3,4,4,5}。

由于Y4≥Y5>Y5-1，所以后者的各种折扣方案中，总是有一个方案的某个组合中存在第4本书而没有第5本书。

（Y1-1, Y2-1, Y3-1, Y4, Y5-1）的可能折扣方案：

{1,2,3,4,5} {4}

{1,2,3,4} {4,5}

{1,2,4} {3,4,5}

…

可以看到不管哪个方案，都一定存在有第4本书，而没有第5本书的分解情况。

{1,2,3,4,5} {4}中的{4}

{1,2,3,4} {4,5}中的{1,2,3,4}

{1,2,4} {3,4,5}中的{1,2,4}

这样，我们总可以把有第4本书，而没有第5本书的组合里面的第4本书换成第5本书。

{1,2,3,4,5} {4} → {1,2,3,4,5} {5}

{1,2,3,4} {4,5} → {1,2,3,5} {4,5}

{1,2,4} {3,4,5} → {1,2,5} {3,4,5}

右边的这些解，就是扣除（1,1,1,1,0）之后，（Y1-1, Y2-1, Y3-1, Y4-1, Y5）的解。

也就是说，对于任何（Y1-1, Y2-1, Y3-1, Y4, Y5-1）的最优解都能转化为（Y1-1, Y2-1, Y3-1, Y4-1, Y5）的一个解，那么对于在扣除4本书折扣组合的情况下，选择（Y1-1, Y2-1, Y3-1, Y4-1, Y5）可以代表其他组合的解，即我们不用再考虑其他的可能，如（Y1-1, Y2-1, Y3-1, Y4, Y5-1）。

其他同理，不再做具体讨论。根据如上推理可以得到状态转移方程：

状态转化之后得到的（Y1-1, Y2-1, Y3-1, Y4-1, Y5）等可能不是“最小表示”，我们需要把它们转化为对应的最小表示。比如：

从上面的表示公式中可以看出，整个动态规划的算法需要耗费O（Y1×Y2×Y3×Y4×Y5）的空间来保存状态的值，所需要的时间复杂度也为O（Y1×Y2×Y3×Y4×Y5）。