精华内容
下载资源
问答
  • 最近在看动态规划,这篇文章是0-1背包问题,看到这个具体化例子真的讲的不错,收藏了,顺便附带了原文评论中的分析部分!原文地址:http://www.cnblogs.com/sdjl/articles/1274312.html对于动态规划,每个刚接触的...

    最近在看动态规划,这篇文章是0-1背包问题,看到这个具体化的例子真的讲的不错,收藏了,顺便附带了原文评论中的分析部分!

    原文地址:http://www.cnblogs.com/sdjl/articles/1274312.html


    对于动态规划,每个刚接触的人都需要一段时间来理解,特别是第一次接触的时候总是想不通为什么这种方法可行,这篇文章就是为了帮助大家理解动态规划,并通过讲解基本的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)
    

    附录

    附:金矿模型代码:

    /*
    =========程序信息========
    对应题目:01背包之金矿模型
    使用语言:c++
    使用算法:动态规划
    算法运行时间:O(people * n) [people是人数,n是金矿数]
    */
    
    #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;
    }
    

    附:0-1背包问题递推分析:

    m为背包容量,n为物品数,w[i]为第i个物品占空间,c[i]为第i个物品价值,f[i]为容量为i的背包所能表现的最大价值,初始化f[i]中都为零 
    
    for i为从1正到n 
        for j为从m反到w[i] 
            f[j]=max{(f[m-w[j]]),(f[j])} 
    
    最后f[m]即为容量为m的背包能表现的最大价值了 
    
        for i in 1 to n: 
            for j in m downto w[i]: 
                if f[j-w[i]]+c[i]>f[j]: 
                    f[j] = f[m-w[i]] + c[i] 
        write(f[m]); 
    这个题和二维数组的方法基本是一样的,要理解这段代码的话先来看一下下面这个公式,它是从金矿模型例子里面搬过来的: 
    f(people,mineNum) = Max{f(people-peopleNeeded[mineNum], mineNum-1) + gold[mineNum],f(people, mineNum-1)} 
    

    写成背包形式的就是:

     f[i,j]=Max{f[i-1,j-w[i]]+c[i] , f[i-1,j]},
    

    f[i,j]表示给定前i个物品和j的容量可以获得的最大价值

    观察一下就会发现,我们在求f[i,*]时仅会用到f[i-1,*],而不会用到f[i-2,*],f[i-3,*]等等

    这就表示,任何时刻我们都可以仅用两个数组来保存f的值,而不用n个,

    公式就可以简化为:

        f_2[j] = Max{ f_1[ j - w[i] ] + c[i] , f_1[j]} 
    

    在求f_2[j]时f_2[j-w[i]]的值可以是任意值而不会影响到f_2[j]的正确性,那么我们就可以用f_2[j-w[i]]的来保存f_1[j-w[i]]的值,
    公式可以改为:

         f_2[j] = Max{ f_2[ j - w[i] ] + c[i] , f_2[j]} 
    

    再仔细观察可以发现,上一个公式中等号左边f_2的下标是一定大于小于等号右边f_2的下标,也就是说如果我们把f_2以大下标到小下标的顺序进行更新,那么自然就可以把f_1和f_2和为一个数组,当求到f[j]时,f[1]、f[2]、……、f[j-1]属于f_2, f[j]、f[j+1]、……、f[m]属于f_1·

    展开全文
  • 1、问题描述 定义栈的数据结构,并在该类型中实现一个能得到栈中最小元素的min函数。要求min,push,和pop操作的时间复杂度O(1)O(1)O(1)。...以下面这个具体例子来解释思路1: 步骤 操作 数据栈 辅助栈 ...

    1、问题描述

    定义栈的数据结构,并在该类型中实现一个能得到栈中最小元素的min函数。要求min,push,和pop操作的时间复杂度为O(1)O(1)

    2、解题思路

    • 思路1:可以借助一个辅助栈,每次在对数据栈做压栈操作时,同时也把数据栈中的最小元素压入辅助栈;而对数据栈做弹出操作时,同时也将辅助栈中的栈顶元素弹出。
    • 以下面这个具体例子来解释思路1:
    步骤 操作 数据栈 辅助栈 最小值
    1 压入3 3 3 3
    2 压入4 3,4 3,3 3
    3 压入2 3,4,2 3,3,2 2
    4 压入1 3,4,2,1 3,3,2,1 1
    5 弹出 3,4,2 3,3,2 2
    6 弹出 3,4 3,3 3
    7 压入0 3,4,0 3,3,0 0

    表1:栈内连续压入3,4,2,1之后两次弹出栈顶元素再压入0时数据栈、辅助栈、以及最小值的状态

    3、代码实现

    # -*- coding:utf-8 -*-
    class Solution:
        datastack = []
        minstack = []
        def push(self, node):
            # write code here
            if len(self.minstack) == 0 :
                self.minstack.append(node)
            else:
                if node < self.minstack[-1]:
                    self.minstack.append(node)
                else:
                    self.minstack.append(self.minstack[-1])
                    
            self.datastack.append(node)
                    
        def pop(self):
            # write code here
            if len(self.datastack) > 0 and len(self.minstack) > 0:
                self.datastack.pop()
                self.minstack.pop()
                
        def top(self):
            # write code here
            if len(self.datastack) > 0:
                return self.datastack[-1]
            else:
                return 
        def min(self):
            # write code here
            if len(self.datastack) > 0 and len(self.minstack) > 0:
                return self.minstack[-1]
            else:
                return 
            
    
    展开全文
  • 抽象,就是由具体例子到更一般的情况,抽象对计算机学科是非常重要的。以我们学习的函数例,实际就是观察到有些操作反复使用,我们将其抽象成一个功能模块,使其只写一次就可以多次调用。可以参见 ...

         抽象,就是由具体的例子范化到更一般的情况,抽象对计算机学科是非常重要的。以我们学习的函数为例,实际就是观察到有些操作反复使用,我们将其抽象成一个功能模块,使其只写一次就可以多次调用。可以参见

    http://en.wikipedia.org/wiki/Abstraction_principle_(computer_programming)

        现在我们有一组数,int arr[N] = {1, 2, 3, 4, 5}; 希望输出格式如下

        1 2 3 4 5

        OnlineJudge的题目一般要求5后面没有空格,然后换行。所以下面的代码不行:

     

     1 #include <stdio.h>
     2 #define N 5
     3 int main(void)
     4 {
     5     int i, arr[N] = {1, 2, 3, 4, 5};
     6     for(i = 0; i < N; i++)
     7         printf("%d ", arr[i]);
     8     printf("\n");
     9     return 0;
    10 }

    我写过下面的代码,第一个元素单独处理,随后的元素前面都有一个空格,最后再来一个换行。

     1 #include <stdio.h>
     2 #define N 5
     3 int main(void)
     4 {
     5     int i, arr[N] = {1, 2, 3, 4, 5};
     6     printf("%d", arr[0]);
     7     for(i = 1; i < N; i++)
     8         printf(" %d", arr[i]);
     9     printf("\n");
    10     return 0;
    11 }

    是不是感觉不清爽,没错,小小的一个功能居然分了三种情况。也许,最后一个元素才应该被区别对待,看下面的代码

     1 #include <stdio.h>
     2 #define N 5
     3 int main(void)
     4 {
     5     int i, arr[N] = {1, 2, 3, 4, 5};
     6     for(i = 0; i < N - 1; i++)
     7         printf("%d ", arr[i]);
     8     printf("%d\n", arr[N - 1]);
     9     return 0;
    10 }

    确实少了一个printf,只有两个情况。 能不能再统一呢? 注意到空格和换行都是字符,可以得到如下的抽象:

    每输出一个元素后都希望接一个分隔字符

    1 #include <stdio.h>
    2 #define N 5
    3 int main(void)
    4 {
    5     int i, arr[N] = {1, 2, 3, 4, 5};
    6     for(i = 0; i < N; i++)
    7         printf("%d%c", arr[i], i == N - 1 ? '\n' : ' ');
    8     return 0;
    9 }

    %c 是一个绝好的抽象,从具体的空格和换行符提升而来。我们很快意识到如果想输出

    1,2,3,4,5

    则只需要把空格换成逗号而已。这说明

    具体的字符可能会变的,而分隔符才是这个问题更高层次的抽象

     

    转载于:https://www.cnblogs.com/4bytes/p/4166213.html

    展开全文
  • 工厂模式:主要用来实例有共同接口的类,工厂模式可以动态决定应该实例那一个类。...我们来看一个具体例子:假设一家工厂,几生产洗衣机,有生产冰箱,还有空调等等…我们先所有产品定义...

    工厂模式:主要用来实例化有共同接口的类,工厂模式可以动态决定应该实例化那一个类。
    工厂模式的形态
    工厂模式主要用一下几种形态:
    1:简单工厂
    2:工厂方法
    3:抽象工厂

    简单工厂
    又叫静态工厂,是工厂模式三中状态中结构最为简单的。主要有一个静态方法,用来接受参数,并根据参数来决定返回实现同一接口的不同类的实例。我们来看一个具体的例子:
    假设一家工厂,几生产洗衣机,有生产冰箱,还有空调等等…
    我们先为所有产品定义一个共同的产品接口

    1. public interface Product{} 

    接着我们让这个工厂的所有产品都必须实现此接口
    1. public class Washer implements Product{ 
    2.    public Washer(){ 
    3.        System.out.println("洗衣机被制造了"); 
    4.    } 
    5.  
    6. public class Icebox implements Product{ 
    7.    public Icebox(){ 
    8.        System.out.println("冰箱被制造了"); 
    9.    } 
    10.  
    11. public class AirCondition implements Product{ 
    12.    public Icebox(){ 
    13.        System.out.println("空调被制造了"); 
    14.    } 

    接下来我们来写一个工厂类,有它来负责生产以上的产品
    1. public class SimpleFactory { 
    2.      
    3.     public static Product factory(String productName) throws Exception{ 
    4.         if(productName.equals("Washer")){ 
    5.             return new Washer(); 
    6.         }else if(productName.equals("Icebox")){ 
    7.             return new Icebox(); 
    8.         }else if(productName.equals("AirCondition")){ 
    9.             return new AirCondition(); 
    10.         }else
    11.             throw new Exception("没有该产品"); 
    12.         } 
    13.     } 

    好了,有了这个工厂类,我们就可以开始下定单了,SimpleFactory将根据不同的定单类决定生产什么产品。
    1. public static void main(String[] args) { 
    2.     try { 
    3.               SimpleFactory.factory("Washer"); 
    4.               SimpleFactory.factory("Icebox"); 
    5.               SimpleFactory.factory("AirCondition"); 
    6.             } catch (Exception e) { 
    7.         e.printStackTrace(); 
    8.     } 

    由上面的代码可以看出,简单工厂的核心就是一个SimpleFactory类,他拥有必要的逻辑判断能力和所有产品的创建权利,我们只需要向把定单给他,就能得到我们想要的产品。这使用起来似乎非常方便。
    但,实际上,这个SimpleFactory有很多的局限。首先,我们每次想要增加一种新产品的时候,都必须修改SimpleFactory的原代码。其次,当我们拥有很多很多产品的时候,而且产品之间又存在复杂的层次关系的时候,这个类必须拥有复杂的逻辑判断能力,其代码量也将不断地激增,这对以后的维护简直就是恐怖两个字...
    还有就是,整个系统都严重依赖SimpleFactory类,只要SimpleFactory类一出问题,系统就进入不能工作的状态,这也是最为致命的一点....
    以上的不足将在工厂模式的另外两种状态中得到解决。

    工厂方法
    上面的代码告诉我们,简单工厂并不简单,它是整个模式的核心,一旦他出了问题,整个模式都将受影响而不能工作,为了降低风险和为日后的维护、扩展做准备,我们需要对它进行重构,引入工厂方法
    工厂方法为工厂类定义了接口,用多态来削弱了工厂类的职能,以下是工厂接口的定义:
    1. public interface Factory{ 
    2.   public Product create(); 

    我们再来定义一个产品接口
    1. public interface Product{} 

    一下是实现了产品接口的产品类
    1. public class Washer implements Product{ 
    2.    public Washer(){ 
    3.        System.out.println("洗衣机被制造了"); 
    4.    } 
    5.  
    6. public class Icebox implements Product{ 
    7.    public Icebox(){ 
    8.        System.out.println("冰箱被制造了"); 
    9.    } 
    10.  
    11. public class AirCondition implements Product{ 
    12.    public Icebox(){ 
    13.        System.out.println("空调被制造了"); 
    14.    } 

    接下来,就是工厂方法的核心部分,也就是具体创建产品对象的具体工厂类,
    1. //创建洗衣机的工厂 
    2. public class CreateWasher implements Factory{ 
    3.     public Product create(){ 
    4.           return new Washer(); 
    5.     } 
    6.  
    7. //创建冰箱的工厂 
    8. public class CreateIcebox implements Factory{ 
    9.     public Product create(){ 
    10.           return new Icebox(); 
    11.     } 
    12.  
    13. //创建空调的工厂 
    14. public class CreateAirCondition implements Factory{ 
    15.     public Product create(){ 
    16.           return new AirCondition(); 
    17.     } 

    从上面创建产品对象的代码可以看出,工厂方法简单工厂的主要区别是,简单工厂是把创建产品的职能都放在一个类里面,而工厂方法则把不同的产品放在实现了工厂接口的不同工厂类里面,这样就算其中一个工厂类出了问题,其他工厂类也能正常工作,互相不受影响,以后增加新产品,也只需要新增一个实现工厂接口工厂类,就能达到,不用修改已有的代码。但工厂方法也有他局限的地方,那就是当面对的产品有复杂的等级结构的时候,例如,工厂除了生产家电外产品,还生产手机产品,这样一来家电是手机就是两大产品家族了,这两大家族下面包含了数量众多的产品,每个产品又有多个型号,这样就形成了一个复杂的产品树了。如果用工厂方法来设计这个产品家族系统,就必须为每个型号的产品创建一个对应的工厂类,当有数百种甚至上千种产品的时候,也必须要有对应的上百成千个工厂类,这就出现了传说的类爆炸,对于以后的维护来说,简直就是一场灾难.....

    抽象工厂
    抽象工厂:意的意图在于创建一系列互相关联或互相依赖的对象。<<Java设计模式>>
    我自己觉得抽象工厂是在工厂方法的基础上引进了分类管理的概念....
    工厂方法用来创建一个产品,它没有分类的概念,而抽象工厂则用于创建一系列产品,所以产品分类成了抽象工厂的重点,
    我们继续用上面的例子来说明:
    工厂生产的所有产品都用都用大写字母来标明它们的型号,比如冰箱,就有“冰箱-A",“冰箱-B",同样,其他的产品也都是遵守这个编号规则,于是就有了一下产品家族树

    冰箱:

    1.   
    2. 冰箱-A  
    3. 冰箱-B


    洗衣机:

    1.   
    2. 洗衣机-A  
    3. 洗衣机-B

    我们可以为冰箱和洗衣机分别定义两个产品接口,以对他们进行分类,
    1. //洗衣机接口 
    2. public interface Washer{ 
    3.  
    4. //冰箱接口 
    5. public interface Icebox{ 

    接着,我们分别创建这两个接口的具体产品
    1. //洗衣机-A 
    2. public class WasherA implements Washer{ 
    3.    public WasherA(){ 
    4.        System.out.println("洗衣机-A被制造了"); 
    5.    } 
    6.  
    7. //洗衣机-B 
    8. public class WasherB implements Washer{ 
    9.    public WasherB(){ 
    10.        System.out.println("洗衣机-B被制造了"); 
    11.    } 
    12.  
    13. //冰箱-A 
    14. public class IceboxA implements Icebox{ 
    15.    public IceboxA(){ 
    16.        System.out.println("冰箱-A被制造了"); 
    17.    } 
    18.  
    19. //冰箱-B 
    20. public class IceboxB implements Icebox{ 
    21.    public IceboxB(){ 
    22.        System.out.println("冰箱-B被制造了"); 
    23.    } 

    到此,产品部分我们准备好了,接下来我们来处理工厂部分,我们先来定义工厂行为接口
    1. public interface Factory{ 
    2.        public Washer createWasher(); 
    3.        public Icebox createIcebox(); 

    接下来我创造具体的工厂类,我们根据上面产品的接口,把型号A的产品分为一类,由一个工厂来管理,把型号为B的产品有另一个工厂管理,根据这个分类,我们可以实现如下的两个具体工厂类
    1. //创建型号为A的产品工厂 
    2. public class FactoryA implements Factory{ 
    3.        //创建洗衣机-A 
    4.        public Washer createWasher(){ 
    5.             return new WasherA(); 
    6.        } 
    7.  
    8.        //创建冰箱-A 
    9.        public Icebox createIcebox(){ 
    10.             return new IceboxA(); 
    11.        } 
    12.  
    13. //创建型号为B的产品工厂 
    14. public class FactoryB implements Factory{ 
    15.        //创建洗衣机-B 
    16.        public Washer createWasher(){ 
    17.             return new WasherB(); 
    18.        } 
    19.  
    20.        //创建冰箱-B 
    21.        public Icebox createIcebox(){ 
    22.             return new IceboxB(); 
    23.        } 


    这样,我们的抽象工厂就完成了。有上面可以看出,在运用上我觉得工厂方法和抽象工厂,都有自己的应用场景,并没有什么优劣之分,但在应用抽象工厂之前,要先对创建的对象进行系统的分类,这点很重要,好的产品分类规则能为具体工厂类的选择调用和以后的扩展提供清晰的思路.

    展开全文
  • 1.什么是接口 接口可以理解自己给使用者来调用自己功能方法的入口。 2.什么要用接口 (1).... ...(2).降低了使用者的使用难度,使用者只...3.接口的例子 class File:#定义接口 def read(self): #定接口函...
  • JAVA 抽象

    2019-04-28 08:55:30
    抽象类在不断抽取过程中,将共性内容中的方法声明抽取,但是方法不一样, 没有抽取,这时抽取到 的方法,并不具体,需要被指定关键字 abstract 所标示,声明为抽象方法。 抽象方法所在类一定要标示为抽象类,也就是...
  • JAVA之抽象

    2020-07-03 19:01:34
    数据抽象为外界提供了仅有的基本信息,在表示基本特征的过程中不包括实现细节。举个真实世界的例子,比如 一本书。当你听到是书时,你不知道具体的细节,如页数颜射或者大小,但你明白书的概念、大概模样。这就是 ...
  • 抽象工厂模式和工厂模式很相似, 是把工厂模式中的工厂的创建方式抽象化了. 抽象工厂的成员 抽象工厂 具体工厂 抽象产品 具体产品 指挥者(用来生产工厂的) 我们还是用食物来举个例子 1,抽象产...
  • 在c#中,抽象类,接口的主要作用是,对代码进行抽象化,让别人在使用我们的代码的时候不需要关心具体的实现,而只需要关心这个函数实现了什么功能就够了。当然如果仅仅是为了实现这个功能,用函数封装就够了,根本没...
  • 抽象工厂模式

    2016-04-04 16:58:51
    创建一组相关或者是相互依赖的对象提供一个接口,而不需要指定它们的具体类   三.抽象工厂模式的使用场景(还是没看懂) 例子:Android,ios,Window,Phone下都有短信软件,拨号软件,两者都属于Software软件的...
  • 抽象工厂模式:创建一组相关或相互依赖的对象提供一个接口,并且无需指定他们的具体类。 我们继续延续我们之前说过的那个例子,工厂生产手机和电脑的例子。 随着产品投入到市场中,消费者反响...
  • B接口有两个产品实现类,B1,B2,现在有一个工厂接口F,有两个实现这个接口的工厂类,F1,F2,这两个类覆写工厂接口中的方法,分别实例A产品的方法和实例B产品的方法。这是要向得到产品实例,调用工厂1,就...
  • 可以在抽象类中定义抽象方法,以供派生类写具体方法。 派生类也可以保留抽象方法,但该类必须为抽象类。 也可以在抽象类中写非抽象方法。 例子抽象类 public abstract class AbstractClass { public ...
  • 抽象类: (abstract) 不能实例。 可以在抽象类中定义抽象方法,以供派生类写具体方法。 派生类也可以保留抽象方法,但该类必须为抽象类。 也可以在抽象类中写非抽象方法。 例子抽象类 public abstract class ...
  • 抽象类中,接口表示一种概念(如形状)而不是具体的对象(如圆)。 在C++中,抽象类只能用作其他类的基类,不能创建抽象类的实例。 一、纯虚函数 C++通过提供纯虚函数来支持创建抽象类。通过初始虚函数0,来将其...
  • 抽象工厂模式:创建一组相关或相互依赖的对象提供一个接口,而且无需指定他们的具体类 区别在于产品,如果产品单一,最合适用工厂模式,但是如果有多个业务品种、业务分类时,通过抽象工厂模式产生需要的对象是...
  • 注意: 抽象工厂模式 和 工厂方法模式不要混肴了,抽象工厂模式扩展性更强,工厂...举个例子抽象工厂模式源于以前针对不同操作系统的图形解决方案,如Android和os中控件TextView、Button等控件,虽然都有这个对象,
  • 但是在现实生活中,一个工厂只创建单个产品这样的例子很少,因为现在的工厂都多元了,一个工厂创建一系列的产品,如果我们要设计这样的系统时,工厂方法模式显然在这里不适用,然后抽象工厂模式却可以很好地解决一...
  • 类是抽象的模版,而实例是根据类创建出来的一个个具体的对象。每个对象都从类中继承相同的方法,但是属性数值可能不同。如学生的类,我们有个对象Shawn,他的方法是身高和体重,对应的数值是178和60 3.定义类的方法...
  • 抽象类、虚函数、接口、多态概念与关系的理解(转) ...抽象类: 不能实例。 可以在抽象类中定义抽象...派生类也可以保留抽象方法,但该类必须为抽象类。 也可以在抽象类中写非抽象方法。 例子抽象类 public abstrac
  • 类中包含属性和具体的方法体。 (2)抽象类:由abstarct修饰的class;不能被实例;可以有自己的属性,也可以有抽象的和非抽象的方法。 (3)接口:关键字interface;不能实例;声明的方法需要子类实现,成员变量...
  • Abstract Factory抽象工厂模式: 创建一组相关或相互依赖的对象...大致意思是说:我们在创建这些对象的时候,并不需要指定它们的具体类,这些具体类的对象是由工厂对象负责实例的。 例子: view plain
  • 1.什么是Saga? 第一次看到这个单词的时候一脸懵逼,因为字典上查到的意思完全驴头不对马嘴。。。 ...最初这篇论文是为了解决分布式系统中的LLT...这么说有点抽象,我们来举个具体例子: 假如你在一个在线订票系统...
  • 大致意思是说:我们在创建这些对象的时候,并不需要指定它们的具体类,这些具体类的对象是由工厂对象负责实例的。下面是《Design Patterns Explained》一书的例子,有关计算机系统的显示和打印程序,用来显示和...
  • 1.定义  简单工厂模式:是由一个工厂对象决定创建... 抽象工厂模式:创建一组相关或相互依赖的对象提供一个接口,而且无需指定他们的具体类。 2.实例  用工人种蔬菜的例子来说明,蔬菜植物的产品器官有根、茎...
  • 1.什么是Saga? ... 最初这篇论文是为了解决分布式系统中的LLT(Long Lived Transaction),也就是长时运行事务的数据一致性问题的。这么说有点抽象,我们来举个具体例子: 假如你在一个在线订票系统上订了一张...
  • 介绍: 工厂方法模式属于创建型模式。定义一个用户创建对象的接口,让...ConcreteProduct(具体产品类):实现抽象产品的某个具体产品类。 Factory(抽象工厂类):工厂模式方法核心,返回一个Product类型的对...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 178
精华内容 71
关键字:

化抽象为具体例子