1.4 买书问题

描述

买书，书共有5种，不同种类的书的组合在一起，能够打折。打折方案如下：

给定书的总数，消费者可以自行搭配书的购买方案，求购买总额最低。

分析

《BoP》书上给出了两种方案，一种是贪心算法，一种是动态规划。

贪心算法的方法不能得到证明是最优的，而动态规划方法正确性有保证。

设书本书为N

贪心算法

单纯的先配对5个，再配对4个。。。这方法不能最优。

注意到若N = 8，则容易考虑到两种较优的方案5 + 3 和4 + 4 $$5 + 3 \rightarrow 5 \times 0.25 + 3 \times 0.1 = 1.55$$ $$4 + 4 \rightarrow 4 \times 0.2 \times 2 = 1.6 $$

所以，需要将所有3个的与5个的进行转化，变成两个4个的。即：\( 5 + 3 \rightarrow 4 + 4\)

复杂度低，但无法证明。

动态规划

中间状态

设某状态，第i本书为\(N_i\)

则最优的价钱可表示为：

由于书本数与书本序号无关，故表示为： ，其中：

状态转移

每个\(X_{i} \)

都是由 求得。

由于从大到小依次减1，比任何其他减1的方法要小，如\(X_{i-3}\)：

所以可以直接让： 其它状态类似。

具体解法参考书。