买书问题

71 阅读 0 评论 47 点赞

我是靠谱客的博主小巧乌冬面，最近开发中收集的这篇文章主要介绍买书问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

  买书问题 

          有五卷书，价格一样，若一次性买不同的两卷，折扣为0.05；若一次买不同三卷，则折扣为0.10，若一次买四卷 

  不同书，折扣为0.2，若买五卷不同书，折扣为0.25. 

  问  设计算法，计算读者一次性购买一批书的最低价格。 

  问题解析： 

          买1-5本书，最高折扣为一次性购买，6-10本书，可以拆分为1-5的多种组合之和，若购买大于10本，则可以拆分为十本以下的组合。因此这里重点讨论6-10本书的折扣问题，寻找价格最低的方案。 

  我们优先考虑最大折扣，只有当最大折扣的限制不可行时，再一次考虑其他可行折扣 

      
      1. 贪心算法，注意到这里四卷书折扣为0.2，三卷和五卷分别为0.1和0.25. 

         计算4+4与3+5哪种方案更为合算： 

      4+4=  0.2*4+0.2*4=1.6 

      3+5=  0.1*3+0.25*5=1.55 

  因此，若有八卷书可以组合成4+4和3+5两种，则选择4+4的组合，这样优惠更多。 

  假定购买的五卷书的本书从多到少一次为Y1>=Y2>=Y3>=Y4>=Y5. 

      原始贪心算法：购买Y5次五卷，（Y4-Y5）次四卷，（Y3-Y4）次三卷，（Y2-Y3）次两卷，（Y1-Y2）次一卷， 

      优化之后的贪心算法，设K=min{Y5，Y3-Y4}   

      选择方案为：购买四卷次数为（Y4-Y5）+2K次，购买五卷次数为（Y5-K），购买三卷次数为（Y3-Y4-K），（Y2-Y3）次两卷，（Y1-Y2）次一卷。 

          
 2.动态规划法 

  每次购买的卷数为1,2,3,4,5五种选择方法， 

      假定购买的五卷书的本书从多到少一次为Y1>=Y2>=Y3>=Y4>=Y5. 

  动态方程为F（Y1，Y2，Y3，Y4，Y5）表示花费最少的表示。 

  那么，我们的最优解可表示如下 

  F（Y1，Y2，Y3，Y4，Y5）= 

   min{ 

      1*单价+F（Y1-1，Y2，Y3，Y4，Y5）， 

      2*单价*0.95 +F（Y1-1，Y2-1，Y3，Y4，Y5）， 

      3*单价*0.9 +F（Y1-1，Y2-1，Y3-1，Y4，Y5）， 

      4*单价*0.8+F（Y1-1，Y2-1，Y3-1，Y4-1，Y5）， 

      5*单价*0.75+F（Y1-1，Y2-1，Y3-1，Y4-1，Y5-1）     

}

以上就是小巧乌冬面为你收集整理的买书问题的全部内容，希望文章能够帮你解决买书问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。