一,问题
上柜的《哈利波特》平装本系列,一共有五卷。假设每一卷单独销售均需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)
五、求伪证
由于本算法过于简单,故作者不相信微软的人们想不出来,求这个算法在何种情况下不适用!
分享到:
相关推荐
算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
算法时间复杂度
算法时间复杂度分析基础算法时间复杂度分析基础算法时间复杂度分析基础
均值滤波很常见 但一般的算法复杂度都和取值窗口w*h有关 算法复杂度太高 本算法优化了基础的均值滤波算法 算法复杂度大大降低
算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
时间复杂度和空间复杂度,大O表示法【数据结构和算法入门2】
算法设计目标与时间复杂度与空间复杂度.ppt
程序员应该掌握的算法复杂度速查表 这个总结非常方便 不仅形象地把各个算法对比开来 也特别利于面试前的复习。
使用 rust 实现的矩阵乘法算法,包括矩阵乘法定义的直接相乘算法,时间复杂度 O(n^3),简单的分治算法(将矩阵划分为 4 个子矩阵),时间复杂度 O(n^3),以及strassen算法(使用了10个中间矩阵存储中间运算结果),...
算法实验代码和报告(时间复杂度、0-1背包问题、分治与贪心、蛮力法)。
排序算法时间复杂度的研究 期刊网站可是要现金的哦。
大学二年级课程 算法设计与分析的一般算法时间复杂度的证明过程,希望可以帮到大家.
关于递归算法时间复杂度分析的探讨.pdf
算法时间复杂度分析中递归方程求解方法综述
信息学奥赛算法时间复杂度和空间复杂度计算 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。 时间效率被称为时间复杂度 空间效率被称作空间复杂度
多段图算法时间复杂度图像
数据结构教程(JAVA语言描述) 设计一个算法,将含有n个整数元素的数组a[0..n-1]循环右移m位,要求算法的空间复杂度为O(1)