俾人眼前一模一样亮的动态规划入门教程

今天于网上来看一个云动态规划的篇章,是盖01背包也例的,这篇与开上的上书非常不雷同,把动态规划用故事之不二法门出口了出去,令人面前一模一样亮啊,于是转载一下下~~~

初稿地址:经过资源模型介绍动态规划

点击下载01背包测试数据.rar 
   

         对于动态规划,每个刚接触的口都用一段时间来喻,特别是率先坏沾的时候总是想不通为什么这种办法中,这篇稿子就是是为帮助大家清楚动态规划,并透过讲课基本的01背包问题来带读者如何错过思考动态规划。本文力求通俗易懂,无异性,不吃读者感觉迷惑,引导读者去思想,所以只要您当读书中发觉发生未通畅的地方,让您闹错误理解的地方,让你难得读懂的地方,请跟贴指出,谢谢!

—-第一节—-初识动态规划——–

       经典的01背包问题是这么的:

       有一个包和n个物品,包的容量为m,每个物品都有个别的体积和价值,问当由当下n个物品被精选多单物品放在包里要物品体积总数不超包之容量m时,能够抱的极其要命价值是略?[对每个物品未得以获取多次,最多只能获取一不好,之所以受做01背包,0意味着未获,1意味收获]

       为了用同样种植潇洒而再形象之不二法门来上课此题,我把此题用另一样栽方法来叙述,如下:

       有一个国,所有的全员都生循规蹈矩憨厚,某天他们于和谐的国家意识了十幢宝库,并且这十幢宝库在地图上铲除成一长达直线,国王知道是信息继非常高兴,他要能将这些黄金还挖掘出来好百姓,首先他把这些宝藏按照在地图及之位置于胡至东头拓展编号,依次为0、1、2、3、4、5、6、7、8、9,然后他发号施令他的手下去对各个一样座金矿进行勘察,以便了解打得诸一样幢金矿需要多少人力及每座金矿能够挖掘起些许金子,然后发动全民都来打通金子。

 

       题目上1:挖每一样座金矿需要之食指是一贯的,多一个口掉一个口且大。国王知道每个宝藏各要有些人口,金矿i用之人头也peopleNeeded[i]。

       题目加2:每一样栋金矿所挖出来的金子数是稳定的,当第i所金矿发生peopleNeeded[i]口去打的语,就定能够正好挖来gold[i]独金。否则一个黄金还打不下。

       题目加3:开采一所金矿的总人口成功开采工作晚,他们无见面再度去开采外金矿,因此一个口顶多只能采用同样潮。

       题目加4:国王在举国上下限制外仅招募到了10000称为愿意为了国家失去开掘金子的人数,因此这些口或许未敷把所有的金还打出来,但是上欲开到之黄金越多越好。

       题目上5:这个国家之各级一个总人口且不行老实(包括皇帝),不见面私吞任何金子,也非会见伪装,不见面说鬼话。

       题目上6:有多口用到是题后的首先感应就是是针对性各国一个金矿求出平均每个人会掘进起些许金子,然后从赛至低进行选择,这里要强调这种措施是拂的,如果您啊是这般想的,请考虑背包模型,当有一个背包的容量为10,共发出3独物品,体积分别是3、3、5,价值分别是6、6、9,那么您的道得到到的凡前方少独物品,总价值是12,但显然不过大值是继少单物品做的15。

       题目加7:我们才待知道最多得打起些许金子即可,而无用关爱什么金矿挖哪些金矿不打。

 

       那么,国王究竟如何知道在只有来10000独人口之景况下最为多能挖起有些金子呢?国王是怎么样考虑是问题的吧?

 

       国王首先来到了第9只钱矿的所在地(注意,第9个就是最后一个,因为凡从0开始编号的,最西边的坏金矿是第0独),他的官僚告诉他,如果要是掏得第9个金矿的语虽待1500单人,并且第9只资源可以挖起8888独金。听到这里国王哈哈大笑起来,因为本他当如果了解十单资源在单纯来10000只人之情状下最多克开起多少金子是均等宗很麻烦思考的题目,但是,就于刚听了他的官宦所说的那么句话时,国王曾清楚一起不过多克开起些许金子了,国王是安在匪打听其他金矿的场面下知最多克掘进起些许金子的呢?他的官府们也无懂得此谜,因此他的命官们便咨询他了:“最明白的国王陛下,我们且未曾告诉你其它金矿的景,您是哪些理解最后答案的也罢?”

 

       得意的君笑了笑笑,然后拿他尽得意之“左、右手”叫到邻近,说交:“我并不需要考虑最终要挖哪些金矿才会取最多的金,我独自需要考虑自己前的当即所宝库就可以了,对于自面前的立所宝库不外乎就来半点种选择,要么挖,要么不开,对吧?”

       “当然,当然”大臣等答疑倒。

       国王继续说道:“如果自己打得第9座金矿的言辞那自己现即使可知得到8888单金,而我用就此去1500独人口,那么自己还剩余8500个人口。我亲近的左部下,如果您告诉自己当我拿具有盈余的8500私和拥有盈余的其余金矿都交你失去开采你太多会让我开来有些金子的言辞,那么自己非纵亮了在第9单资源一定开采的气象下所能够取的极致要命金币数为?”

       国王的左部下听后回道:“国王陛下,您的意是若自己力所能及用8500只人当其余金矿最多开采出x个金币的话,那你一起就能收获 x

  • 8888个金子,对吗?”

       “是啊,是呀……如果第9座宝库一定开采的说话……”大臣等点头说交。

       国王笑着累本着正值他的右侧部下说及:“亲爱的右边部下,也许我连无打算开采就第9幢宝库,那么自己还是拥有10000只人,如果本身管当下10000私家以及多余的宝库都为你的话语,你不过多克给自己打来小个黄金呢?”

       国王的右手管下聪明地商量:“尊敬之统治者陛下,我了解您的意了,如果本身回复最多能进开采出y单金币的话,那您尽管足以当y和x+8888之间选择一个于充分啊,而之比大者就是最终我们能赢得的无比酷金币数,您看自己这么懂对为?”

     

       国王笑得重复绚丽了,问他的左部下:“那么亲切的左部下,我叫你8500民用及外金矿的语你能够告我不过多克开起多少金子吗?”

       “请你放心,这个题材难以休倒我”。左部下向皇帝打包票说到。

       国王高兴地延续问他的下手部下:“那右管下您为,如果自身让您10000私及其余金矿的说话你能够告诉自己极其多能挖掘起多少金子吗?”

       “当然会了!交给自己吧!”右部下同左部下同样自信地回复道。

       “那便拜托给你们两各项了,现在本人只要返回我那舒适的宫殿里去享受了,我期待正在你们的对答。”国王说了就从头启程返回等信息了,他是多地信任他的少独大臣能够为他一个规范之应,因为皇帝其实明白他的点滴个大臣而比较他明白得差不多。

       故事发展及此,你是不是以惦记上的马上半个大臣而是何等找到为皇帝满意的答案的吧?他们怎么能够这样自信呢?事实上他们确实比较上而明白有,因为他们从皇帝的身上学到了好几,就是立一点受她们充满了自信。

       国王走后,国王的荒谬、右部下到了第8栋宝库,早已于那里等候她们之宝藏勘测兵向星星各大臣报道:“聪明的星星点点个大臣,您等好,第8幢金矿需要1000单人口才会开采,可以博7000只黄金”。

       因为上仅让他的左部下8500独人口,所以上的左部下为来了点滴单人口,对正在其中一个总人口咨询到:“如果自身被你7500私及除了第8、第9之别具有钱矿的语,你能够告我你太多能打通起多少金子吗?”

       然后上的左部下连续问其他一个人:“如果我被您8500个体以及除了第8、第9之其余具有钱财矿的言语,你能告我若太多能挖起多少金子吗?”

       国王的左部下在心底想方:“如果她们俩且能回应我之题材的话,那国王交给自己之题目非纵迎刃而解了邪?哈哈哈!”

       因为上为了他的右边管下10000个人,所以上的下手部下同样为深受来了一定量只人,对在其中一个丁问:“如果本身让您9000私家以及除了第8、第9的其余具有钱财矿的讲话,你能告我而不过多克开起多少金子吗?”

       然后王的下手部下继续问他叫来之任何一个人口:“如果自己让你10000个体与除了第8、第9的其余具有钱财矿的口舌,你可知告自己你无限多能挖来有些金子吗?”

       此时,国王的右手部下同左部下一样,他们还于也友好如此聪明而感到满足。

      

       当然,这四独让叫来的人一样自信地对没有问题,因为他们一致地自当下有限只大臣身上学到了同样的一些,而少于各由认为自己平大聪明的重臣得意地笑着回去了她们之官邸,等在别人对他们取出来的题目,现在若懂了这点儿单大臣是哪解决上交待给他们之题材了吗?

 

       那么你认为吃大臣叫去之那四独人口同时是怎完成大臣交给他们之题材之也罢?答案当然是她们找到了另外八只人!

       没因此粗功夫,这个题目曾当举国传开了,更多口之口找到了重复重多之丁来化解此问题,而聊人也未待去另外找点儿单人口拉他,哪些人无欲别人的帮带就得回复他们的问题吧?

       很明显,当被咨询到叫您z个人和就发生第0栋宝库时不过多克掘进来有些金子时,就无欲别人的帮忙,因为您知,如果z大于等于挖取第0栋金矿所用之人头之言语,那么开出来的不过多黄金数便是第0幢宝库能够打出来的金子数,如果立即z个人不够开采第0所宝库,那么能开出来的极致多金子数就是0,因为就唯一的宝藏不敷人力去开采。让咱们也这些不欲别人的帮就足以规范地查获答案的众人鼓掌吧,这就是风传着之最底层劳动人民!

       故事说到此地先暂停一下,我们本重新来分析一下以此故事,让我们针对动态规划来只理性认识。

 

       子问题:

       国王欲基于两单大臣的答案和第9座金矿的信才能够判定有尽多克开采出小金子。为了解决好面临的题材,他需要给旁人做另外两独问题,这半独问题就是子问题。

       思考动态规划的率先点—-太优子结构

       国王相信,只要他的点滴独大臣能够对出科学的答案(对于考虑会开采出的金子数,最多的也就是极了不起的又为便是科学的),再添加他的明白之判定即便肯定能够博取最终的没错答案。我们将立即粒问题最好优时母问题通过优化增选后自然最良好的景称“最优子结构”。

 

       思考动态规划之亚碰—-分段问题重叠

       实际上国王也好,大臣认可,所有人数对的都是一致的问题,即被您早晚数量的人口,给你势必数额之富源,让您请来会开采出的绝多黄金数。我们将这种母问题与子问题本质上是与一个题目的情称“子问题重叠”。然而问题被出现的不同点往往就是被问题里传递的参数,比如这里的人口及金矿数。

      

       思考动态规划的老三接触—-边界

       想想如果不有前我们关系的那些底层劳动者的言语是题目能化解也?永远都未可能!我们拿立即粒问题在一定时候就是不再要提出子子问题之情事称边界,没有界限就见面油然而生死循环。

 

       思考动态规划的季碰—-分层问题独立

       要明,当王的少个大臣在盘算他们协调的题材经常他们是勿会见关切对方是怎么计算怎样开采金矿的,因为她俩懂得,国王只会挑个别单人口吃的一个当最终方案,另一个总人口之方案并无见面收获推行,因此一个人口之支配对其它一个人的决定是从未有过影响之。我们将这种一个本问题在对问题选择时,当前深受捎的分支问题两少互相免影响的状况称“子问题独立”。

 

       这便是动态规划,具有“最优子结构”、“子问题重叠”、“边界”和“子问题独立”,当您意识你正在考虑的问题有着这四只属性的话,那么恭喜你,你基本上就找到了动态规划之措施。

       有矣方的即时几乎触及,我们尽管可以描绘起动态规划之换方程式,现在我们来形容来相应之问题之方程式,如果因此gold[mineNum]代表第mineNum个资源能够开起底金子数,用peopleNeeded[mineNum]意味着开第mineNum个资源需要的口,用函数f(people,mineNum)表示当有people个人与数码为0、1、2、3、……、mineNum的金矿时亦可拿走的极端特别金子数的语,f(people,mineNum)等于什么也?或者说f(people,mineNum)的转换方程是什么的啊?

       答案是:

       当mineNum = 0且people >=
peopleNeeded[mineNum]时 f(people,mineNum) = gold[mineNum]

       当mineNum = 0且people <
peopleNeeded[mineNum]时 f(people,mineNum) = 0

       当mineNum != 0时 f(people,mineNum) =
f(people-peopleNeeded[mineNum], mineNum-1) +
gold[mineNum]及f(people,
mineNum-1)中之于充分啊,前少独姿态对应动态规划之“边界”,后一个姿势对应动态规划的“最优子结构”请读者为明白后更累往下看。

—-次节—-动态规划的亮点——–

       现在自身若读者你既闹明白了胡动态规划是毋庸置疑的法子,但是我们为何要运用动态规划也?请预连续玩这故事:

       国王得知他的个别独手下使用了跟外相同之措施去解决交代给他俩之题材后,不但没有觉得他的有数独大臣在偷懒,反而死喜悦,因为他了解,他的大臣必然会找更多之人头一头解决此问题,而重多之人会寻找更还多的口,这样他者聪明之法门就会于非留神间流传开来,而全国老百姓都见面分晓这聪明的法是他俩伟大之君主想出去的,你说上能无欢吗?

       但是天子也闹一部分焦虑,因为他实在不懂得者“工程”要运到多少人口来好,如果帮他解决这题目之口极其多的讲话那就是最划不来了。“会无见面影响至今年之收成啊?”国王在心尖想着这个题材,于是他呼吁来了整整国家里唯一的星星独数学天才,一个号称小天,另一个称呼小才。

       国王问小天:“小天啊,我发现这问题不怎么严重,我懂得其实这好大概的作为一个做问题,也即是于十个资源中摘若干单资源进行采,看看啊种组成获得的金子最多,也许用整合措施会重新好有的。你可知告自己合计发生多少种组成情况呢?”

       “国王陛下,如果因此做措施的口舌一共使考虑2底10蹩脚方种情况,也即是1024种情景。”小天思考了同样碰头答应到。

       “嗯……,如果每一样种植情景本身付出一个人数失去算能得到的金子数的口舌,那自己吗如1024单人口,其实还是挺多之。”国王好像又感到到了好之方式是不利的。

       国王心理期待在小才能够给她一个再好之答案,问到:“小才啊,那么你会告我因此自身之不胜方式总共用有些人口乎?其实,我为算算了,好像得的食指是1+2+4+8+16+32+64+……,毕竟每一个总人口真的还亟需寻找另外两单人口来帮她们……”

       不辜负国王的企盼,小才微笑着说交:“亲爱的上陛下,其实我们并不需要那么基本上人,因为发成千上万题目莫过于是平等的,而我辈无非待呢各一个差的题目下一个人力就可。”

       国王高兴的问话到:“此话如何谈?”

       “打个比方,如果产生一个总人口需掌握1000私及3独资源可以开采出小金子,同时其它一个人也急需懂得1000私有与3只资源可以开采出有些金子的语句,那么他们可错过了解同之一个总人口,而非用各自找不同之人头浪费人力了。”

       国王思考正说交:“嗯,很有道理,如果问题是同样的口舌那即便未待去了解两单例外的人数了,也就是说一个不比之题材只是需一个人力,那么一共来小个例外之问题也?”
  

       “因为每个问题的食指可以从0取到10000,而金矿数可以从0取到10,所以极多约产生10000
* 10 等于100000独不同的题材。” 小才一边算着一面回答。

       “什么?十万只问题?十万只人工?”国王有点失望。

       “请皇上放心,事实上我们用的人工远远小于是数之,因为无是各级一个题目都见面赶上,也许我们仅仅需同、两百独人工就得化解这题目了,这至关重要和各个金矿所欲之人头有关。” 小才及时对到。

       故事之最终,自然是帝王还同破向他的臣民们证明了外是这个国家里最明白的人数,现在咱们经过故事之次有些来设想动态规划的另外两个思考点。

 

       思考动态规划的第五沾—-做备忘录:

       正使上面所说的一样,当我们相遇同样之题材时,我们好问同一个丁。讲的通俗一点哪怕是,我们可以管题目的解放在一个变量中,如果重复相见这问题即直接打变量中取得答案,因此各一个题材只是会精打细算同一举,如果未做备忘的话,动态规划纵从不其他优势可言了。             

 

       思考动态规划的第六点—-时间分析:

       正而上面所说,如果我们所以穷举的不二法门,至少用2^n个常反复时,因为一起发生2^n种情况需要考虑,如果在背包问题备受,包的容量也1000,物品数为100,那么需要考虑2^100种植状态,这个数约为10之30次方。

 

       而使因此动态规划,最多约就来1000*100 =
100000个例外的问题,这同10的30不良方比起来优势是十分显眼的。而实质上状况并无会见起那么多不同的题目,比如当资源模型中,如果所有的聚宝盆所用人口还是1000单人口,那么问题总数约只有发生100只。

 

       非正式地,我们好好易得动态规划所用时日,如果共有questionCount独一样的分层问题,而每一个题材需对chooseCount种选择时,我们所要时哪怕也questionCount
* chooseCount单常反复。在资源模型中,子问题最好多发生大约people *
n 个(其中people是用来开矿金矿的到底人数,n是金钱矿的总额),因此questionCount
= people *
n,而就是如王欲考虑是使左部下的结果要么使用右部下之结果一律,每个问题直面少数单选项,因此chooseCount
= 2,所以程序运行时间啊 T = O(questionCount * chooseCount) =O(people *
n),别忘了事实上要之光阴低于这个价值,根据所遇的具体情况有所不同。

 

       这即是动态规划之魔力,它减少了大气之乘除,因此我们要动态规划!

—-叔节—-动态规划的沉思角度———-

       那么什么是动态规划为?我个人觉得,如果一个缓解问题之点子满足上面六单思考点中之前方四只,那么这法子就是属于动态规划。而当思索动态规划方式时,后少点同样为是待考虑的。

       面对问题设物色动态规划之不二法门,首先要明一些,动态规划不是算法,它是相同种植方法,它是于同码业务闹的进程遭到寻觅最优值的办法,因此,我们得对当时桩工作所起的长河进行考虑。而常见咱们由过程的终极一步开始考虑,而无是先考虑过程的开。

       打只假设,上面的打金矿问题,我们好当满门开采过程是从海交东拓展采的(也尽管是由第0栋开始),那么到底有面对最后一所金矿的下(第9所),对当下座宝库不外乎两单选项,开采和不开采,在结尾一步确定时再次去确定倒数第二步,直到考虑第0幢宝库(过程的初步)。

 

       而经过的启幕,也就是考虑的结尾一步,就是界。

       因此在碰到一个题目想就此动态规划之法子去解决时,不妨先考虑一下这个过程是安的,然后考虑过程的结尾一步是什么样选的,通常我们需要协调失去组织一个进程,比如后面的操练。

—-第四节—-总结——-

       那么遇到问题如何用动态规划去解决呢?根据地方的辨析我们得依照下面的步子去考虑:

 

       1、构造问题所对应的长河。

       2、思考过程的终极一个手续,看看有哪些选择情况。

       3、找到最后一步的子问题,确保入“子问题重叠”,把子问题遭不等同的地方设置也参数。

       4、使得子问题切合“最优子结构”。

       5、找到边界,考虑边界的各种处理方式。

       6、确保满足“子问题独立”,一般而言,如果我们是于差不多个子问题遭甄选一个作实施方案,而无见面同时执行多个方案,那么子问题就是是单身的。

       7、考虑怎么做备忘录。

       8、分析所要时日是否满足要求。

       9、写来易方程式。

—-第五节—-练习——-

       题目一:买书

       有雷同书店引进了扳平模拟书,共发生3卷,每窝书定价是60初次,书店为将促销,推出一个挪,活动如下:

      

       如果单独买其中同样窝,那么得打9.5折。

       如果以市两窝不同之,那么可打9折。

       如果又请三窝不同之,那么好打8.5折。

      

       如果小明希望买第1卷x本,第2卷y本,第3窝z本,那么至少需要有些钱吧?(x、y、z为三个就清楚整数)。

       当然,这道题完全可以不用动态规划来解,但是今咱们是设读书动态规划,因此要想想什么用动态规划来开?

       答案:

       1、过程为同样坏同坏的置,每一样差购进或只是进同样依照(这来三种方案),或者打简单按照(这吗发出三种植方案),或者三遵照一起进(这生平等栽方案),最后直到进完所有需要之题。

       2、最后一步我定会当7栽购买方案受到甄选相同种植,因此自只要以7种植购买方案被选取一个超级状态。

       3、子问题是,我选了某方案后,如何令进剩余的开能够就此最少的钱?并且这选项无会见使剩余的书啊负数。母问题和子问题还是被得三卷写之购买量,求最好少得为此的钱,所以有“子问题重叠”,问题屡遭三个购买量设置为参数,分别吗i、j、k。

       4、的确可。

       5、边界是一致涂鸦购买就好买完所有的书,处理方式请读者自己考虑。

       6、每次挑最多发生7种植方案,并且不会见又履行之中多,因此方案的挑三拣四互不影响,所以产生“子问题独立”。

       7、我好用minMoney[i][j][k]来保存购买第1窝i本,第2卷j本,第3卷k本时所用的无比少金钱。

       8、共有x * y * z 个问题,每个题目对7种植选择,时间呢:O( x * y
* z * 7) =  O( x * y * z )。

       9、用函数MinMoney(i,j,k)来表示请第1窝i本,第2卷j本,第3窝k本时所需要的绝少金钱,那么有:

              MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分别吗相应的7种植方案以的无比少金钱:

              s1 = 60 * 0.95 + MinMoney(i-1,j,k)

              s2 = 60 * 0.95 + MinMoney(i,j-1,k)

              s3 = 60 * 0.95 + MinMoney(i,j,k-1)

              s4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k)

              s5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)

              s6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)

              s7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1)

—-第六节—-代码参考——

       下面提供资源问题的程序源代码帮助读者知道,并提供测试数据给大家练习。

 

       输入文件称吧“beibao.in”,因为此题材其实即便是背包问题,所以测试数据文件名就保留原名吧。

       输入文件首先实践有一定量个数,第一单凡是陛下可用用来开采金矿的终究人数,第二只凡是凡发现的金矿数。

       输入文件的第2交n+1行每行有有限只数,第i行的少数独数分别代表第i-1个资源需要之总人口和可以获得的金子数。

       输出文件只一个整数,表示能赢得的尽深黄金数。

 

       输入样例:

       100 5

       77 92

       22 22

       29 87

       50 46

       99 90

       输出样例:

       133

       参考代码如下:

java版代码(把本来的c++代码转之java代码):

package com.readwrite;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Scanner;

public class 动态规划 {

    static final int max_n = 100;//程序支持的最多金矿数
    static final int max_people = 10000;//程序支持的最多人数
    static int count= 0;
    static int scount= 0;
    static int n;//金矿数
    static int peopleTotal;//可以用于挖金子的人数
    static int[] peopleNeed = new int[max_n];//每座金矿需要的人数
    static int gold[] = new int[max_n];//每座金矿能够挖出来的金子数
    static int maxGold[][] = new int[max_people+1][max_n];//maxGold[i][j]保存了i个人挖前j个金矿能够得到的最大金子数,等于-1时表示未知


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //初始化数据
        init();
        //输出给定peopleTotal个人和n个金矿能够获得的最大金子数,再次提醒编号从0开始,所以最后一个金矿编号为n-1
        System.out.println(GetMaxGold(peopleTotal,n-1));
        System.out.println("count:"+count+" scount:"+scount);//count:672 scount:106
    }

    //初始化数据
    static void init(){
        File f = new File("beibao9.in"); 

        try {
            Scanner sc = new Scanner(new FileInputStream(f));
            peopleTotal = sc.nextInt();  //总人数
            n = sc.nextInt();   //金矿数
            for(int i = 0;i<n;i++){
                peopleNeed[i] = sc.nextInt();
                gold[i] = sc.nextInt();
            }
            for(int i=1;i<=peopleTotal;i++) //人数从1开始,不然容易逻辑混乱
                for(int j = 0;j<n;j++)
                    maxGold[i][j] = -1;//等于-1时表示未知 [对应动态规划中的“做备忘录”]


        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        //测试读取数据,成功
        /*System.out.println("peopleTotal:"+peopleTotal+" n:"+n);
        for(int i = 0;i<n;i++){
            System.out.println("peopleNeed["+i+"]:"+peopleNeed[i]+" gold"+gold[i]);
        }*/
    }

    //获得在仅有people个人和前mineNum个金矿时能够得到的最大金子数,注意“前多少个”也是从0开始编号的
    static int GetMaxGold(int people, int mineNum)
    {
        //申明返回的最大金子数
        int retMaxGold;

        //如果这个问题曾经计算过  [对应动态规划中的“做备忘录”]
        if(maxGold[people][mineNum] != -1)
        {   scount++;
            //System.out.println("people:"+people+"  mineNum:"+ mineNum);
            //获得保存起来的值
            retMaxGold = maxGold[people][mineNum];
        }
        else if(mineNum == 0)//如果仅有一个金矿时 [对应动态规划中的“边界”]
        {
            //当给出的人数足够开采这座金矿
            if(people >= peopleNeed[mineNum])
            {    
                //得到的最大值就是这座金矿的金子数
                retMaxGold = gold[mineNum];
            }
            else//否则这唯一的一座金矿也不能开采
            {
                //得到的最大值为0个金子
                retMaxGold = 0;
            }
        }
        else if(people >= peopleNeed[mineNum])//如果给出的人够开采这座金矿 [对应动态规划中的“最优子结构”]
        { 
            //考虑开采与不开采两种情况,取最大值
            retMaxGold = Math.max(GetMaxGold(people - peopleNeed[mineNum],mineNum -1) + gold[mineNum],
                                            GetMaxGold(people,mineNum - 1));
        }
        else//否则给出的人不够开采这座金矿 [对应动态规划中的“最优子结构”]
        {
            //仅考虑不开采的情况
            retMaxGold  = GetMaxGold(people,mineNum - 1);
        }
        count++;
        //System.out.println("people:"+people+"  mineNum:"+ mineNum);
        //做备忘录    
        maxGold[people][mineNum] = retMaxGold;
        return retMaxGold;
    }
}

  C++版:

/*
=========程序信息========
对应题目:01背包之金矿模型
使用语言:c++
使用编译器:Visual Studio 2005.NET
使用算法:动态规划
算法运行时间:O(people * n) [people是人数,n是金矿数]
作者:贵州大学05级 刘永辉 
昵称:SDJL
编写时间:2008年8月
联系QQ:44561907
E-Mail:44561907@qq.com
获得更多文章请访问我的博客:www.cnblogs.com/sdjl
如果发现BUG或有写得不好的地方请发邮件告诉我:)
转载请保留此部分信息:)
*/

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

const int max_n = 100;//程序支持的最多金矿数
const int max_people = 10000;//程序支持的最多人数

int n;//金矿数
int peopleTotal;//可以用于挖金子的人数
int peopleNeed[max_n];//每座金矿需要的人数
int gold[max_n];//每座金矿能够挖出来的金子数
int maxGold[max_people][max_n];//maxGold[i][j]保存了i个人挖前j个金矿能够得到的最大金子数,等于-1时表示未知

//初始化数据 
void init()
{
    ifstream inputFile("beibao.in");
    inputFile>>peopleTotal>>n;
    for(int i=0; i<n; i++)
        inputFile>>peopleNeed[i]>>gold[i];
    inputFile.close();

    for(int i=0; i<=peopleTotal; i++)
        for(int j=0; j<n; j++)
            maxGold[i][j] = -1;//等于-1时表示未知 [对应动态规划中的“做备忘录”]

}

//获得在仅有people个人和前mineNum个金矿时能够得到的最大金子数,注意“前多少个”也是从0开始编号的
int GetMaxGold(int people, int mineNum)
{
    //申明返回的最大金子数
    int retMaxGold;

    //如果这个问题曾经计算过  [对应动态规划中的“做备忘录”]
    if(maxGold[people][mineNum] != -1)
    {
        //获得保存起来的值
        retMaxGold = maxGold[people][mineNum];
    }
    else if(mineNum == 0)//如果仅有一个金矿时 [对应动态规划中的“边界”]
    {
        //当给出的人数足够开采这座金矿
        if(people >= peopleNeed[mineNum])
        {    
            //得到的最大值就是这座金矿的金子数
            retMaxGold = gold[mineNum];
        }
        else//否则这唯一的一座金矿也不能开采
        {
            //得到的最大值为0个金子
            retMaxGold = 0;
        }
    }
    else if(people >= peopleNeed[mineNum])//如果给出的人够开采这座金矿 [对应动态规划中的“最优子结构”]
    {
        //考虑开采与不开采两种情况,取最大值
        retMaxGold = max(GetMaxGold(people - peopleNeed[mineNum],mineNum -1) + gold[mineNum],
                                        GetMaxGold(people,mineNum - 1));
    }
    else//否则给出的人不够开采这座金矿 [对应动态规划中的“最优子结构”]
    {
        //仅考虑不开采的情况
        retMaxGold  = GetMaxGold(people,mineNum - 1);
    }

    //做备忘录    
    maxGold[people][mineNum] = retMaxGold;
    return retMaxGold;
}

int _tmain(int argc, _TCHAR* argv[])
{
    //初始化数据
    init();
    //输出给定peopleTotal个人和n个金矿能够获得的最大金子数,再次提醒编号从0开始,所以最后一个金矿编号为n-1
    cout<<GetMaxGold(peopleTotal,n-1);
    system("pause");
    return 0;
}