买书问题

来自计算思维百科
跳转至: 导航搜索
买书问题1.png

《哈利波特》系列一共有五卷,每一卷售价均8欧元。同时买不同的卷(各一本)有折扣,具体如下表:

购买数量(卷)

折扣(%)

2

5

3

10

4

20

5

25

在一份订单中,根据购买的卷数及本数,可以有多种不同的折扣规则,但一本书只能应用一个折扣规则。

请设计一个算法,计算购书组合,使得所购买的一批书花费最少。

解决方案

本案例中为了方便计算,我们假设现在要买的一批书数量为:1本卷1,2本卷2,2本卷3,2本卷4,1本卷5。

方案一-直接比较法

购买组合及其总折扣如下。

组合一:{卷1,卷2,卷3,卷4,卷5},{卷2,卷3,卷4}

折扣:5*0.25+3*0.1=1.55


组合二:{卷1,卷2,卷3,卷4},{卷2,卷3,卷4,卷5}

折扣:4*0.2+4*0.2=1.6


组合三:{卷1,卷2,卷3},{卷2,卷3,卷4},{卷4,卷5}

折扣:3*0.1+3*0.1+2*0.05=0.7


组合四:{卷1,卷2},{卷2,卷3},{卷3,卷4},{卷4,卷5}

折扣 2*0.05+2*0.05+2*0.05+2*0.05=0.4
从上述计算结果可以看出最优组合为4+4时,折扣最大为1.6。

运用的计算思维

直接比较法是找出所有的组合数计算总折扣,运用了机械化的计算思维,当要购买数量很多时,不是最佳解法。

方案二-贪心法

传统贪心总是作出当前局部的最优选择—总是选择25%的折扣,这个折扣对我们最有利,如果没有5本不一样,则选择次大的20%,如果没有4本不一样的,选择10%,……以此类推,因此,贪心法的选择的结果是(5+3)组合,即5*0.25+3*0.1=1.55({卷1,卷2,卷3,卷4,卷5},{卷2,卷3,卷4})

运用的计算思维

贪心法虽然每次都作出局部最优选择,但显然在本题中,局部最优解并不是全局最优解。对于规模大的问题,贪心算法能够快速找出局部最优解,在一定程度上能够满足我们对于最终结果的要求。贪心算法的运用是一种“优化”思维的体现。

方案三-动态规划法

每卷的价格都一样,故算法可做简化。
   F为总折扣率。
   输入Y为每卷的书数。
  F(Y1,Y2,Y3,Y4,Y5)
  = 0 , if (Y1=Y2=Y3=Y4=Y5=0)
  = max{
  5*0.25+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1), if (Y5>=1)
  4*0.20+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5), if (Y4>=1)
  3*0.10+F(Y1-1,Y2-1,Y3-1,Y4,Y5), if (Y3>=1)
  2*0.05+F(Y1-1,Y2-1,Y3,Y4,Y5), if (Y2>=1)
  1*0+F(Y1-1,Y2,Y3,Y4,Y5), if (Y1>=1)
  }
  动态规划,获取最大的折扣。
   F(1,2,2,2,1)
  = max{
  5*0.25+F(0,1,1,1,0),
  4*0.20+F(0,1,1,1,1),
  3*0.10+F(0,1,1,2,1),
  2*0.05+F(0,1,2,2,1),
  1*0+F(0,2,2,2,1),
}

运用的计算思维

动态规划法由于采用了递归,时间复杂度太高,是一个指数级的算法。仔细分析可以发现,递归算法中子问题会发生重复,导致执行了很多步骤。但在本题中,动态规划法是最佳方法,体现了优化的计算思维。

参考文献

《编程之美》小组.《编程之美》.电子工业出版社.2008