`
v5qqbrowser
  • 浏览: 353052 次
文章分类
社区版块
存档分类
最新评论

《编程之美》中买书问题算法。空间复杂度O(n),时间复杂度O(n),求挑战

 
阅读更多

一,问题

上柜的《哈利波特》平装本系列,一共有五卷。假设每一卷单独销售均需8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下:

本数2 折扣 5%

本数3折扣 10%

本数4折扣 20%

本数 5 折扣25%

问题:设计出算法,能够计算出读者所购买的一批书的最低价格。

二、问题的简化

8欧元是个对算法没有影响的条件。我们假设第一本书的价格为1。

现在我不是一组一组(组指一个能够享受优惠的单位,组中的书的数量可以为1,此时无优惠)的买书,而是一本一本的买书。

买第一本的价格为1

买第二本的价格为0.9(第二本必须和第一本不同,它的价格是0.95*2-1=0.9)

买第三本的价格为0.8(第三本必须和前两本均不同,它的价格是0.9*3-0.95*2=0.8)

买第四本的价格为0.5

买第五本的价格为0.55

我们可以看书这个问题的关键就在于买第五本的时候反而会比买第四本贵!可以想象如果商店进行这样的促销活动,大家买到4件的时候就会不想买第五件了!

所以我们就知道,如果目前有两个人一个人买了4本书,另一个买了3本,现在新来了一哥们,想和其中一个人拼团购。那么这哥们会果断的选择买了3本的那个人,而不会选择买了4本的那个人。

三、问题的解法

按照一本一本买书的原则,我们保证“每一本新买的书的价格必须最低”,最后就可以得到一个最低的总价。

用集合{N1,N2,N3,N4,N5}表示每种书的数量,其中N1>=N2>=N3>=N4>=N5

我们怎么个开始买法呢?当然应该从N1这本开始买起,因为同一组里面不能有相同的书,组的数量肯定要等于N1.

我先证明组的数量不会大于N1

买4本书需要花3.2,买5本要花3.75.当我要买20本的时候,我是以每组4本买5组好呢,还是以每组5本买4组好呢?

3.2*5>3.75*5,所以在这种情况下以一组5本的方式来购买花费更少。其他情况可以类似的证明。我们可以得出的结论就是“不要在迫不得已的时候新开组”。

接下来我们就可以开始买书了。

我先买N1个第一本书,把它们一溜排开放好。之后我买书的时候就往之前的书上摞,摞的原则是:1、该书没有和该摞中的其他书重复。2、该书的购买价格最小。

举书中给出的例子{7,6,3,2,1}

我先买第一本,书是这样放置的

N1 N1 N1 N1 N1 N1 N1

接着开始买第二本书,买完之后书堆变成了这样

N2 N2 N2 N2 N2 N2

N1 N1 N1 N1 N1 N1 N1

然后买第三本,这里N3显然不能往最后一个N1上面放,因为这样买要花0.9,而放在N2上只要花0.8

N3 N3 N3

N2 N2 N2 N2 N2 N2

N1 N1 N1 N1 N1 N1 N1

继续买第四本,放在N1上面需要0.9,放N2需要0.8,放在N3上只要0.5,那我果断的放在N3上面

N4 N4

N3 N3 N3

N2 N2 N2 N2 N2 N2

N1 N1 N1 N1 N1 N1 N1

终于买到最后一本了!我发现把这本摞在N3上面只需要0.5,而摞在N4上面竟然需要0.55!我当然不会选择那个花钱多的了

N4 N4 N5

N3 N3 N3

N2 N2 N2 N2 N2 N2

N1 N1 N1 N1 N1 N1 N1

于是书买好了。我买了3个四本,3个2本,1个1本。和教材中的买法是相同的。

四、算法的时间复杂度和空间复杂度

空间复杂度:每本书用一个空间存储,所以空间复杂度是O(n)

时间复杂度:每本书的排列一次到位,所以时间复杂度是O(n)

五、求伪证

由于本算法过于简单,故作者不相信微软的人们想不出来,求这个算法在何种情况下不适用!

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics