买书问题-程序员宅基地

技术标签: 编程之美  算法  

一、问题:

买书问题:

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

        本数    2       折扣   5%

        本数    3       折扣  10%

        本数    4       折扣  20%

        本数    5       折扣  25% 

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

二、分析

注意此题的关键点在两个地方:首先题目要求我们的折扣需要不同的书,比如两本卷一是不能使用折扣的;其次我们注意当买的书较多的时候会出现不同的组合情况,我们的目的就是求出哪一种组合情况最省钱。

三、解法一贪心算法

贪心算法指的就是我们每次先去看能不能使用五本折扣的,如果不能再去寻找四本折扣的,一次类推。
但是书中给出的情况也说明了,这样的话,当书的情况是(2,2,2,1,1)的时候采用贪心算法的话采用的是5,3进行折扣,但是这种折扣不如4,4的折扣。
虽然书中最后还给出了其改进的算法,但是到最后还是没有进行证明改进后的算法一定是最优的。
所以本文对贪心算法也不再进行赘述。

四、动态规划

1.问题中等价性

我们假设用Xn表示购买第n卷的的数量,那么我们用(X1,X2,X3,X4,X5)表示购买五种书的数量。我们用F(X1,X2,X3,X4,X5)表示购买这些书需要花费的最少费用。那么我们不难看出:F(X1,X2,X3,X4,X5)=F(X2,X1,X3,X4,X5),原因是各卷书的价格都是一样的,打折的要求和每一本书的种类是没关系的,只需要不同卷就行。
那么我们下面来把购书的这个向量进行更改一下,我们首先把X1,X2,X3,X4,X5从大到小进行排序,我们把排序的结果用Y1>=Y2>=Y3>=Y4>=Y5来进行表示。
那么由于上面的等价性我们知道F(X1,X2,X3,X4,X5)= F(Y1,Y2,Y3,Y4,Y5)的,我们为什么要进行这样的转换呢?接着往下看。

     2.动态规划

假设我们要买的书是(Y1,Y2,Y3,Y4,Y5),如果第一次我们考虑的是为五本不同的书进行付款(要求Y5>=1),也就是五种书分别减一就行了,我们好像并没有别的选择了。
那么假设我们第一次考虑的是为四本不同的书进行付款呢?那么我们就有可能有如下的购买集合:
(Y1-1 ,Y2-1 ,Y3-1 ,Y4-1 ,Y5)此时我们要求Y4>=1, 注意书上没有写要求,但是我认为下面的四个组合要求Y5>=1

(Y1-1 ,Y2-1 ,Y3-1 ,Y4 ,Y5-1

(Y1-1,Y2-1,Y3,Y4-1,Y5-1)

(Y1-1 ,Y2 ,Y3-1 ,Y4-1 ,Y5-1

(Y1 ,Y2-1 ,Y3-1 ,Y4-1 ,Y5-1
既然有这五种的购买集合,那么我们用哪一种的购买方式比较好呢?
直觉上,好像第一种购买方式可能比较好,原因是什么呢?第一种购买方式之后,好像留下最多的后续组合,我们举个例子,假设我们的购买书的向量是
(2,2,2,2,1),那么如果采用上面的第一种购买组个我们剩余的是(1,1,1,1,1)这样接下来可以直接选择五本的折扣,如果我们选择第二种的购买方式,余下的组合是:
(1,1,1,2,0),这样接下来我们的购买方式智能分解为(1,1,1,1,0)和(0,0,0,1,0),直觉告诉我们如果我们要准备选择4本的折扣的时候,尽量紧着数目多种类的书选,这样对不对呢?是不是要选择三本书,两本书进行折扣的时候都是按照这样的原则就能找到最优解呢?接下来我们证明。
书上给出的证明方式真的很巧妙,不得不服啊。
假设:如果在(Y1,Y2,Y3,Y4,Y5)的情况下选择扣除(1,1,1,0,1)能够得到最优解,此时剩下的组合是 (Y1-1 ,Y2-1 ,Y3-1 ,Y4 ,Y5-1
     注意:这只是假设,不要迷糊了。
那么在这个假设的基础上,我们如果能够证明,采用扣除(1,1,1,1,0)也同样能够得到最优解, 那么我们就可以说每次按照(1,1,1,1,0)就行了
注意这句话的理解:为什么?举个例子吧,如果商家A和商家B同时卖一种商品,商家B说了,我卖的价格一定不会比A高,意思也就是说A卖多少,我至少会和他相等,或者小于他。同样的道理用到我们的题目中,采用方案二扣除的方式如果能够找到最优解的话,我们的方案一也一定能够找到最优解,结果是什么,我的方案一一定不会比方案二差。假设这个定理我们已经证明过了(注意是假设,我们会在后续把它证明了),你用同样的道理去比较方案三和方案二,你说加入方案三能够找到最优解,那么我的方案二也一定能够找到最优解,一次类推,最后你会发现其实方案一是最好的。
下面我们来证明:
从选择扣除四本书的组合来看,目前选择扣除方式是(1,1,1,0,1),由于Y4>=Y5那么显然在剩余的情况 (Y1-1 ,Y2-1 ,Y3-1 ,Y4 ,Y5-1 中,Y4>Y5-1,则在
(Y1-1 ,Y2-1 ,Y3-1 ,Y4 ,Y5-1 的最优解中一定存在某些组合仅有Y4,没有Y5.
举个例子:注意书中给出了这样的例子Y1=Y2=Y3=Y4=Y5,我认为举这样的例子不太恰当,我后面再给出解释,我们先看书上的证明

假设 Y1=Y2=Y3=Y4=Y5=2,选择(1,1,1,1,0)的话我们就会得到(1,1,1,1,2),那么剩下的书的序号就是{1,2,3,4,5,5}.
选择(1,1,1,0,1)的话我们就会得到(1,1,1,2,1),那么剩下的书的序号就是{1,2,3,4,4,5},由于Y4>Y5-1,则在 (Y1-1 ,Y2-1 ,Y3-1 ,Y4 ,Y5-1 的最优解中一定存在某些组合仅有Y4,没有Y5,我们来看 (Y1-1 ,Y2-1 ,Y3-1 ,Y4 ,Y5-1 的可能折扣方案:
{1,2,3,4,5} {4}
{1,2,3,4}   {4,5}
{1,2,4}        {3,4,5}
........
不管在哪个方案中都会出现一定有4而没有5的情况
{1,2,3,4,5} {4} 中的{4}
{1,2,3,4}   {4,5}中的{1,2,3,4}
{1,2,4}       {3,4,5}中的 {1,2,4}
其实你仔细看会发现,如果我们把由第4本书而没有第5本书的组合里面的4换成5之后,是什么呢?就是我们如果最初采用(1,1,1,1,0)之后的可能的折扣方案。
{1,2,3,4,5} {4}——> {1,2,3,4,5} {5}
{1,2,3,4,}   {4,5} ——>{1,2,3,5}   {4,5}
{1,2,4}        {3,4,5} ——>{1,2,5}        {3,4,5}
这说明什么?这说明我们的方案二的最优解都能转化为方案一的最优解,这样的话,我们上面已经讨论过,这样我们就可以只是使用方案一来进行扣除了,因为他是最好的。
那么接下来我来说说为什么书上举这个例子是不太好的, Y1=Y2=Y3=Y4=Y5=2,他举的这个例子让人容易产生错觉,太巧了,为什么Y4要等于Y5呢,大于的时候会出现什么?大于的时候这个定理还成立吗?接下来我们进行讨论
当(Y1,Y2,Y3,Y4,Y5)为(2,2,2,2,1)的时候。
如果我们采用方案二扣除,得出的是(1,1,1,2,0),它剩余了{1,2,3,4,4}那么它之后的可能的方案是:
{1,2,3,4}  {4}
{1,2,4}  {3,4}
{1,3,4}  {2,4}
.......
那么我们如果采用第一种扣除方案的时候呢?得出的是(1,1,1,1,1),它剩余了{1,2,3,4,5},它之后的可能的方案是什么呢?
{1,2,3,4}  {5}
{1,2,4}  {3,5}
{1,3,4}  {2,5}

........

发现没有,你和上面进行对比,同样是可以转化的。

所以说无论是Y4=Y5,还是Y4>Y5,都是满足的。

这样我们就可以证明了方案一是最好的。

也就是说我们在进行扣除的时候,无论我们准备要扣除四个,三个,还是两个,紧着数目多的书进行扣除就一定能找到最优解。

下面给出书中的伪代码:

F(Y1,Y2,Y3,Y4,Y5)
  = 0 if (Y1=Y2=Y3=Y4=Y5=0)
  = min

       {
  5*8*(1-0.25)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1), if (Y5>=1)
  4*8*(1-0.20)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5), if (Y4>=1)
  3*8*(1-0.10)+F(Y1-1,Y2-1,Y3-1,Y4,Y5), if (Y3>=1)
  2*8*(1-0.05)+F(Y1-1,Y2-1,Y3,Y4,Y5), if (Y2>=1)
  8+F(Y1-1,Y2,Y3,Y4,Y5), if (Y1>=1)
  }

注意一点:我们每次进行扣除后,都要对剩下的书再次进行从大到小的排序。

例:
  F(1,2,2,2,1)
  = min{
  5*8*(1-0.25)+F(0,1,1,1,0),
  4*8*(1-0.20)+F(0,1,1,1,1),
  3*8*(1-0.10)+F(0,1,1,2,1),
  2*8*(1-0.05)+F(0,1,2,2,1),
  8+F(0,2,2,2,1),
  }
  注意下面这一步就是再次进行从大到小的排序
  = min{
  5*8*(1-0.25)+F(1,1,1,0,0),
  4*8*(1-0.20)+F(1,1,1,1,0),
  3*8*(1-0.10)+F(2,1,1,1,0),
  2*8*(1-0.05)+F(2,2,1,1,0),
  8+F(2,2,2,1,0),
  }

再解释下这个代码的过程,它其实就是一个穷举的过程,采用递归的方式,不过每次递归的时候都采用当前来说最好的扣除方案,不过具体扣除几个它都进行了穷举,最后把穷举的结果比较,看那个花费的少就返回哪个值,其实这个和上一个问题的烙饼的那个问题有点像。

代码就不贴了,网上很多,时间太紧了,我要赶紧去学机器学习了。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ML_algorithmResearch/article/details/50409903

智能推荐

Manjaro 使用 pacman 安装软件出现 错误:无法从 mirrors.ustc.edu.cn : XXX 错误:无法升级 archlinuxcn (下载数据库出错) 信息_archlinuxcn.db下载失败-程序员宅基地

文章浏览阅读2.4w次,点赞6次,收藏18次。系统:Manjaro 20.0.3桌面:Gnome安装软件时出现错误:无法从 mirrors.ustc.edu.cn : Operation timed out after 10001 milliseconds with 0 out of 0 bytes received 获取文件 'archlinuxcn.db'错误:无法升级 archlinuxcn (下载数据库出错)错误:无法从 lonewolf-builder.duckdns.org : Recv failure: 连接被对方重设 获取._archlinuxcn.db下载失败

技术面试时这样介绍自己的项目经验,等于成功了一大半-程序员宅基地

文章浏览阅读2.9k次,点赞4次,收藏35次。源/头条 文 /程序员界的彭于晏面试时7分靠能力,3分靠技能,而刚开始时的介绍项目又是技能中的重中之重,决定一次面试的成败,那么面试时如果要介绍自己的项目该..._技术面如何将自己做的项目

git生成ssh密钥详细步骤 git如何生成ssh密钥_gitssh密钥生成-程序员宅基地

文章浏览阅读3.7w次,点赞16次,收藏100次。git生成ssh密钥详细步骤 git如何生成ssh密钥_gitssh密钥生成

app账号退不出去_ios企业签名掉签?苹果近日批量封了几百个企业级开发者账号...-程序员宅基地

文章浏览阅读687次。目前苹果基本暂停了新号注册,但今天开始市场会流入大量欧洲国家残留下的号到中国!全是虚假资质注册,使用超不过一个月100%会封号,(群里之前曝光的俄罗斯人所为,目前已下榻深圳某酒店甩卖)!苹果目前严厉查封虚假资质账号,未满14天也会被封的可能,哪怕不买,也不能趁虚而入被坑!熬过了这段时间,以后自然会有新的资质没问题账号下来!  个人 公司账号 查的同时 又把矛头指向了 企业账号?就在刚刚,..._app store 频繁封号

Chai3D之相机视角_chai3d示例-程序员宅基地

文章浏览阅读127次。相机是 3D 可视化中的主要查看工具。它们被放置在世界上并以独特的方式命名。场景中可以存在多个摄像机,每个摄像机都连接到单独的视口(窗口)以向用户显示场景。相机可以查看固定目标,跟随路径,或直接由触觉设备控制(例如模拟内窥镜)。本章探讨使用摄像机并将其连接到窗口显示或视口的基本过程。世界内的摄像机指向场景。近剪裁平面和远剪裁平面定义摄像机渲染的区域。_chai3d示例

Java 文件内容修改(一)_java 修改文件-程序员宅基地

文章浏览阅读5k次,点赞8次,收藏36次。遇到一个需求,需要修改文件中的内容,查找资料发现如下工具类:原链接:点击打开链接/** * 修改文件内容 * * @param fileName * @param oldstr * @param newStr * @return */ private static boolean modifyFileContent(String fileName, String o..._java 修改文件

随便推点

【哈士奇赠书活动 - 24期】-〖前端工程化:基于Vue.js 3.0的设计与实践〗_程沛权 博客-程序员宅基地

文章浏览阅读3.6k次,点赞132次,收藏98次。【哈士奇赠书活动 - 24期】-〖前端工程化:基于Vue.js 3.0的设计与实践〗_程沛权 博客

聊聊Git的使用方法_rsa key fingerprint is sha256:jok3fh7q5lj6qve7ipne-程序员宅基地

文章浏览阅读226次。Git克隆项目克隆项目代码git clone ssh地址若出现密钥问题The authenticity of host 'git.dev.tencent.com (118.25.166.124)' can't be established.RSA key fingerprint is SHA256:jok3FH7q5LJ6qvE7iPNehBgXRw51ErE77S0Dn+Vg/I..._rsa key fingerprint is sha256:jok3fh7q5lj6qve7ipnehbgxrw51ere77s0dn+vg/ik. a

强化学习(reinforcement learning)教程_强化学习教程-程序员宅基地

文章浏览阅读3.4w次,点赞2次,收藏29次。前一阵研究强化学习,发现中文的资料非常少,实例就更少。于是翻译一篇q学习算法的教程,供需要的人学习。原文链接:http://mnemstudio.org/path-finding-q-learning-tutorial.htm正文:Q学习算法是一种用来解决马尔可夫决策过程中最优化问题的方法。Q学习算法最大的特点是它具有选择瞬时奖励和延迟奖励的能力。在每一步中,agent通过观察状态_强化学习教程

字节跳动安全Ai挑战赛-小样本赛道方案总结_小样本赛题数据-程序员宅基地

文章浏览阅读3.8k次。1 赛题描述在真实的社交网络中,存在的作弊用户会影响社交网络平台。在真实场景中,会受到多方面的约束,我们仅能获取到少部分的作弊样本和一部分正常用户样本,现需利用已有的少量带标签的样本,去挖掘大量未知样本中的剩余作弊样本。给定一段时间内的样本,其中包含少量作弊样本,部分正常样本以及标签未知的样本。参赛者应该利用这段时间内已有的数据,提出自己的解决方案,以预测标签未知的样本是否为作弊样本。数据处理方法和算法不限,但是参赛者需要综合考虑算法的效果和复杂度,从而构建合理的解决方案。2 题目思路基于给定的少_小样本赛题数据

vuex之getters用法_vuex调用字仓库方法-程序员宅基地

文章浏览阅读278次。vuex的作用是用来状态共享的,state中定义数据,但如果需要对数据进行一定的处理,比如说state中有一个数组,但我们需要显示该数组中某些符合特定要求的值,而这些特定的数据需要在多个组件中shi'yong..._vuex调用字仓库方法

列表去重_列表去重吗-程序员宅基地

文章浏览阅读510次。List listWithDup = new ArrayList(); listWithDup.add(1); listWithDup.add(2); listWithDup.add(3); listWithDup.add(1); listWithDup.add(3); List listWithout_列表去重吗