00:00
各位,我们用动态规划算法呢来解决背包问题,问题的描述刚才已经给大家讲过了,这里就不再多说,我直接给他说一下我们整个。动态规划算法解决背包问题的一个思路和图解,把这个呢给大家聊一聊。OK,我们来分析一下这个背包问题。背包问题呢,主要是指。是指一个给定的容量的背包,若干具有一定价值和重量的物品,如何选择放入背包,其价值最大,使其价最大,那这个背包问题又分为零一背包和完全背包。零一背包就是说我们放的东西呢,不能够重复,而完全背包呢,指的是每一种物品可以无限件的可用,就是你可以放多件进去。我们现在刚才这一个提出的问题,它是属于0101背包的,及每个物品最多放一次,那么有些同学说,老师那那这个无限背包问题好不好解决呢?无限背包可以转成零一背包,所以说你只要把零一背包学明白了,无限背包其实它也是比较容易去求解的。
01:11
好,这是对背包问题的一个解释,那么现在呢,我们就来分析一把,就是这个。目前我们所说的背包问题,他的一个主要思想是什么?我们永远在做一件事情,就是你一定先有有一个思想。对,你如果在解一个题的时候没有思想,那么你就会出现别人给你说一个说的这个题他并不是很难,就很也很好理解他的提议,但是你就写不出来,你首先要有思想,把这个思想呢,往往是会把它提成一个公式。或者叫规律,有可能不是公式,你可能是一个规律。对,有了这个东西过后呢,你再去代码。所以说我们第一件事情要把思想说清楚,然后再推导出这个公式,最后代码就水到渠成了,其实代码其实挺简单的,真的代码挺简单,但是呢,这个分析的过程它是比较麻烦的,就是看你这个人聪不聪明。
02:10
你能不能想到,而且我可以告诉大家。这个跟数学也没有什么太多关系,不是说你数学学的好啊,你就一定能把这个题解决是不是,但是数学学的好呢,肯定是有优势的,因为他数理逻辑比较强的人呢。他一般来讲,他他的他的那个思路就比较开阔一些,好,我们接着往下看吧。嗯,那么这个要讲的背包问题呢,利用动态规划来解决,首先我要说的第一次,第一个事情是每次便利得到的第二个物品。就说就说这句话,就说我们这个物品呢,是一个一个往里面放的。现实生活中也是这样子的,比如说我现在有一个物品,两个物品,三个物品,这是我们的一个背包,你是不是也是先尝试着把第一个放进去,再看看第二个能不能放进,第三个能不能放进去,然后还要估量一下价值呀。
03:04
是,就是这样子的吗?说白了你是在不停的测试,所以说我们呢,第一个事情是每次便利得到第个物品,那么根据wi和VI来确定是否需要将该物品放入到背包中,那这里首先我要解释一下何为wi,先听一下啊,所以wi就代表第个。商品或者叫物品的重量。听清楚没有,待会我还写一遍,VI呢,代表的是第第二个商品的它的价值,明白好呃,决定过后,然后即对给定的N个物品。我们现在物品假设有N个,现在是第个设VI。Wi分别为第个物品的价值和重量。刚才我已经说过了,C假定是我们背包的最大容量。或者叫背包的容量,那么再令VJ这大家看是一个二维数组,看到没有?
04:05
它实际上这能用用的是一个二维数组来表示什么呢?注意听V节,表示的是在前挨个物品中能够装入容量为洁的背包的最大价值。这句话怎么理解呢?就是说假设现在我已经放了有挨个物品到背包里边去,而当前这个背包的容量呢?为节。那么我能够放进去的最大的容量用VI节来表示,听清楚没有?那有些同学可能会想,诶,老师在不对啊,这个容量怎么是个变量呢?是的,我们刚才讲过,背包的容量C确实确实是给定的,比如说前面我们给的背包的容量是四,为什么这个地方是个结,是个变量呢?因为你这个容量其实是在不停的测试的。就说我在假定背包容量为一,为二为三的时候,我能放什么?所以它是动态的在变化。
05:05
OK,那现在呢,嗯,这样讲可能大家很难理解老老师在说什么,这样子我们呢。刚才已经讲过了,背包问题,它可以通过填表的方式逐步推导,那现在呢,我这里已经给各位同学。已经画了一个思路的推导图,也就是说我们先把这个东西,我们先不去用代码,不去考虑算法,你自己来玩,你会怎么玩呢?填一张表。把这个表拿到以后,把这个填的表拿到以后呢,诶,我们再把它推导成一个,找到它的规律,这个规律呢,我们就把它总结成一个公式就可以了,这就公式已经有了,但这个公式你现在看不懂。所以说我们先来看它的一个规律吧,打开。PPT上面的一个文档,我们打开,我已经准备好了,我们一起看一遍好不好,看一遍我们也可以自己填一填。
06:02
好,我跟大家一起一起来走一走,好吧,现在呢,为了让大家听的比较明白,我呢这样子同学们,我用Excel文件Excel表一边讲一边画,好不好,把这个课件打开,然后把图件打开来看一下。目前别人已经给了我们一些条件的。我们来说一下背包的一个填表过程。写到这里来。背包。背包的一个填表。填表的一个过程来,首先呢,同学们,你先要知道你目前。这个物品有哪些,是不是这是我们的物品呢?也就是说现在呢,我统共有这种三个物品。这三个物品呢?我要填到哪里去呢?各位同学跟上我的思路,下面呢,我们有一张表,看到没有解决类似的问题,可以分解成一个一个小问题解决,假如假设存在的背包的容量分别为1234。
07:05
这就是刚才我们所说那个节。OK,那现在这个表呢,我已经有了,我们来一起来填一填。好吧,跟上老师思路啊,这个并不难,然后我把这个表呢,给各位同学放到这边来。很简单的一张表。好,这个表呢,我这已经有了啊,我们来一起填这张表,大家可以看到呢,呃,这这个地方代表它的行。也就是说,也也就是说你们待会看到这个行,就是像在这一行行的列是用哪个表示呢?这边代表列OK。那么我就形成了一张表,看到没有,好,我们来一起填一填。假定。假定目前。假定目前如果说啊,听我说,假定这个物品一个都没有。第一行是代表一个物品都没有,那么显然那这地方就没有不可不可能存在价值了,就全部写零,这个是为了将来那个I刚好跟。
08:03
他第几个商品数量对应,所以说我这里设置了一个全零的一行和全零的一列,也也就现在老师高亮的这一部分呢,你可以理解成当我们一个商品都没有的时候,那不管你的背包。的这个呃,容量是多大?那么它的价值都为零,明白了吧?那么这列代表什么意思呢?列代表就是说如果你这一个包包它的容量为零,棒,那你不管是什么商品你都装不进去,所以说它的价值也为零,所以说大家现在看到这一行为零和这一列为零的原因就是这样子的,那我为什么要这样设计呢?因为待会我想I和解啊,刚好就能够表示是第几个商品,明白了吧。好,现在呢,我们就可以往里面填了,来,朋友们。如果是只有吉他,注意听啊,注意听这句话,假设现在呢,那这个地方。我可以这样写啊,写一句话。
09:02
哦,我写一下,大家可能理解的更清楚一点。好,第一步,假如注意听啊,假,假如。假如现在呢?只有。只有这个吉他可以往里面放。只有吉他这个商品,同学们你想一想。诶,怎么回事,这个现在假如只有吉他是不是,此时此刻你不管你的你的这个背包的容量有多大,你也只能放一把吉他进去,是这样子吧,同学们,那这时。这时不管不管背包背包容量多大。多大只能放?放什么呢?一把吉他,一个吉他,好吧,吉他。及。特尔,他吉他没问题吧,同学们,那这样子就比较简单了,这个他。
10:00
鸡汤。好,那现在就比较简单,那这边就是1500,就是我的思路啊,那就1500这边写个G。这边写个G。把这个换一下,那后面也是一样的道理,同学们后边呢,也不管你这个是什么情况是不是。我这边呢,也只能放这个玩意儿,这个也是,这个也是好,写完了第一个就完成了,来同学们现在紧接着呢,刚才是吉他啊,现在紧接着呢,我们到这来了,就说现在呢,我们有两种商品可以放,一种是吉他,一种是音响。那你会怎么放呢?来,现在我们接着看第二步。嗨,这个怎么回事,这。第二步啊,第二步,现在假如。假如有吉他。吉他。和什么呢,和这个音响。音响好,那这个时候大家想我们可以怎么放呢?
11:01
如果是对于商品,如果说对于现在容量呢,诶只有一半,那你没办法,你肯定也只能放个吉他进去,因为大家知道我们我们这边还有一张可以参照的表,因为你现在这个音响呢,它的重量是四个棒。它的它的重量是释磅,所以说你是没有办法放进去的,因此呢,在这个情况下,同学们注意听啊,待会我们就就有公式就出来了,在这种情况下,你的背包只有一包,是你只能放个放一把吉他进去,当有两包的时候,因为你这个音响它释放已经大于了你。你注意听这句话啊,你的音响的这一个重量都已经大于我当前这个背包的啊,嗯,这这个大家看看这个地方啊,往这看了,假设现在是两磅了,两磅你你你这个两磅的这个容量音响也比你大,所以说也不可能考虑放音响,也你也只能从上面这个粘下来,所以听这句话,你看我说的是从上面这个粘下来。
12:04
这个待会是有用的啊,这句话是有用的,我们再来看,当我们的物品,当我们的背包的容量变成了呃,三磅,但是这个三磅呢,还小于你你新加的这个商品的重量,所以说这个时候你也只能从上面这个把它粘下来。我我说的这些话将来都会形成这个规律和公式的啊,同学们好,紧接着我们再来看释放,诶释放就可以了,现在呢,我们发现我们。准加入的这个新的商品呢,它。它的这个容量大于大于等于失放了,因为你是我也是失败啊,这个时候我就要考虑考虑什么呢?我的这一个新加的这个商品,它的价值有没有比上面这个高,注意听这句话啊,待会就就比较,就我发现诶,如果我放一个释磅的音响进去,它有300。
13:00
3000块钱,它大于上面这个格呀,于是我就换成了什么呢3000。这个时候,我放的就不再是吉他了,而是什么呢?而是音响。好,注意听这句话很有用哈,待会儿我们要用到这些特点的,紧接着呢,我们又回来,下面往下走,看到没有,就是有个动作往下走的动作,同时你这是不是又回去了。又看这个一磅,哎,大家看这个时候你看你新加的这个电脑呢,它是三磅,你你三棒实际上在这种情况下,它是大于你当前背包的容量,你当前背包只有一半,那这个时候没有办法,你也只能从上面拷下来。大家有没有看到,大家有没有看到,我这个时候考的时候是从上面考的,而不是从这个中考的,那说明什么呢?我的这个求解的这个结果,它是依赖于你上次这个求解的结果了,明白我的意思吧,就是刚才我们所说的动态规划的,它的下一个子问题的解答是依赖于。上一次子问题的这个解的好,同样道理,我们再看两磅,两磅也没什么可说的,因为你电脑还有音响呢,都大于两磅,装不进去,这个时候你空着也只能空着。
14:11
为什么呢?因为因为你放不进去,而且我们这个地方不允许放两把吉他进去,所以你只能放从上面粘一个下来,好到了三棒情况就不一样了,到了三磅呢,这个时候我们发现三我新加的电脑它是大于等于三磅的,可以考虑尝试着装一下这个当前的这个商品,发现呢,2000诶2000装完了过后呢,我没有空余空余的空间了,因为。我两我注意听这句话啊,现在你有三棒,我先尝试着把这个新的放进去,放进去过后呢,我还要看看有没有空余的空间,有吗?你这有,你这背包三磅,但是我的空余的我也三磅,所以说当我装进去过后,这个背包其实没有没有空余空间了。
15:01
是吧,没有空余空间,也就空余空间为零,那就不要找了,好,这个时候我们就只直接把这个电脑放进去就可以了。这时候我们直接放入电脑,那就是2000。2000。这一个什么呢,L。电脑是L,好,同学们,这个规律我们又找到了,最后这个地方是最关键的,当然我这一直一直在移动啊四棒,当四棒来的时候,你应该怎么怎么考虑这个事呢?如果作为一个人来讲,不不不不去考虑程序,你会怎么讲,你是不是应该这样想,你先尝试着。把这个电脑放进去。把这个电脑放进去过后呢,看看你剩余的空间里面最大的那个量是多大。大家知道我在说什么吗?也就是说你先尝试着把这个2000放进去。2000放进去过后呢,你再看看你有没有剩余空间,因为你是四磅,我是三磅,还剩一还剩一磅,这个时候你你就要去找。
16:02
在剩余的一半里面。能够最大的是多少,只有1500,所以说这个时候呢,你就加上1500,就这样来的。这个,所以说这个就是一把吉他。这个就是一把吉他,而上面这个L呢,L它就是一个电脑。哎,它就是个电脑,就这样得到了这个这个解的。就这样得到这个解好,那么当我们得到这个解过后呢,我们整理一个公式给大家玩一把,同学们看,这个公式我们就其实已经出来了。这个公式呢,有点不好理解,我先在在这讲一讲啊,同学们。
我来说两句