采药问题分析与解答

《采药问题分析与解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、采药问题的分析与解答采药问题的分析与解答一一0-1背包问题的教学实践作者:fzdl9zx@gmail.com2011-3-17【摘要】0・1背包问题，是NOIP（青少年信息学奥林匹克竞赛）的一个常见问题。对于普及组水平的学生來说，该问题的理解与论述是比较抽象的。但是，引导青少年选手理解这一类型的问题，有助于选手进一步理解动态规划的实质，也有助于帮助选手利用该算法的解决其他同质的问题。本文利用NOIP2005的一个实际例题，分析并解释0・1背包问题的解决过程。文中代码采用C语言描述。【文章难度】屮级【预期读者类

2、型】程序设计语言初学者（已经学过基本的结构化程序设计语言）【关键字】动态规划背包问题C语言NOIP算法设计引入这是2005NOIP普及组复赛的第3题：问题名称：采药（medic.c）【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他岀了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需耍一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如杲你

3、是一个聪明的孩子，你应该可以讣采到的草药的总价值最人。-如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1<=T<二1000）和M（1<=M<二100）,用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下來的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大

4、总价值。【样例输入】7037110069112【样例输出】3【数据规模】对于30%的数据，M<=10；对于全部的数据,M<=100o初窥门径首先，我们來解释一下，为什么这个问题如此困难？难就难在，辰辰面对一株草药的时候，很难决断是否耍采它。在实践中，选手提出了许多解决问题的策略，主要有：作者：fzd19zx@gmail.comPage1of6采药问题的分析与解答1、价值优先策略：辰辰总是先采摘价值最大的草药。2、时间优先策略：辰辰总是先采摘“采药所需时间”最短的草药。3、价值/时间优先策略：辰辰总

5、是先采摘“价值/采药所需时间"（性价比）最大的草药。但是，考虑以下输入数据的实例，我们很容易发现，上述3种策略都是有缺陷的：实例1：采药的总时间上线:10；草药数量：3编号123再看，实例2：采药的总时间上线:10；草药数量：3编号123再看，实例3：采药的总时间上线:10；草药数量:3编号123先策略也是不妥的。那么，究竟该如何是好呢？理论分析其实，这个问题屈于数学上的“动态规划''的一个子问题：背包问题；意指如何在给定承重上限的背包中，装入最大价值的物品。如果背包问题中的每种物品只有1个实例，那么该问题乂

6、被称为0・1背包问题。采药问题，就是0・1背包问题的一个变种。动态规划、背包问题、0・1背包问题之间的关系，如下图所示：采摘时间192价值2104采摘时间497价值185采摘时间476价值485此时，若应用价值优先策略，应采摘编号2的草药。而最住方案是采1、3号草约。所以，价值优先策略是不妥的。此时，若应用时间优先策略，应采摘编号1的草药。而最佳方案是采2的草药。所以，时间优先策略也是不妥的。此时，若应用价值/时间优先策略，应采摘编号1、3的草药。而最佳方案是采1、2号草药。所以，价值/时间优动态规划问题背包

7、问题o・i背包问题下面，我们来解释一卜•，如何解决这个采药问题。作者：fzd19zx@gmail.comPage2of6采药问题的分析与解答首先为了方便讨论，我们给出下列约定：1、我们把总共m株草药，从上到卜•排成1歹IJ,分别叫做第1株、第2株第m株草药。并且，我们把向上方向叫做“前面,’,向下方向叫做“后面"o2、对于第j株草要來说，采摘它所需时间记为wj,其价值为pjo3、总的采药时间上限记为To依题意，T<100o4、草药数量的上限记为Mo依题意，M<1000。有了上述约定，采药问题就可以转换为如下数

8、学表述：采药问题的最终冃标，是求:mmaximize》(pjxxj)j=1其中，xj指的是第j株草药的数量。在这里，xje{0,1}o这也就是为什么类似这种问题，被称为0・1背包问题。上式意指对于m株草药中的每一株而言，耍么采(xj=l),要么不采(xj=O)。我们的冃标即是耍求(也就是要求(plXxl)+(p2xx2)+…+(pmxxm)的最大值；)(plxxl)+(p2xx2)+...+(pmx