00:00
同学们,我们刚才对背包问题做了分析和图解,那下面呢,我们用代码把背包问题给大家实现一下,打开我们的eclipse,新建一个包,Dynamic动态算法。Dynamic,然后呢,我们新建一个类叫背包问题对吧。背包。Napsdack。Stack,这样写的吧,Sack,然后呢,Problem。对,背包问题。我们。来开始编写,首先呢,同学们,我们把这个全拼一下啊,我们先把先建一个数组保存我们物品的。重量。143没问题吧。我写个注释。这是物。物品的重量。
01:00
第二个,我们是不是还要一个数组来记录物品的价值,这个物品的价值我用value表示。那么我们知道第一个物品的价值是1500。第二个物品的价值是3000对吧,3000,第三个物品的价值是2000,我写个注释,这是物品的价值。没问题吧,好,紧接着呢,我们有个M,第一个M是表示背包的。注意听背包的什么样容量。紧接着我们再定一个变量N,这个N呢,我们表示物品的个数,那物品的个数其实我们可以通过value。Value来求一下就可以了,点认这个就是我们物物品的个数。好的。那有了这些过后呢?我们还得有一个特别重要的二维数组,大家还记不记得我们这个二维数组是用V表示的?
02:04
这个V呢。他如果有两个下标,就代表我们的一个就是。D在前挨个物品中能够装入容量为J的背包的最大价值,那待会我们在写的时候单个的V,那么我们就用value表示了啊,同学们单个的V就就就用这个value表示了,能理解我的意思吧,这个地方跟我们公式稍微有点变化,我说一下啊,这里我我做一个说明这里的value。I。就是。就是我们前面讲的,前面讲的这个VI能理解哈,因为我我这门含义发生变化了,那现在呢,我们就来开始写。先创建什么呢?A,创建一个二维数组。创建二维数组干什么呢?表示我我先把它写出来吧,比如说我们写了一个。
03:00
这样的二位数组V6INT,首先它有多少行呢?行应该按N加一,列是多少呢?列是M加一,为什么?因为N加一代表你有多少个商,你N是物品的个数,加一嘛,就代表行,因为我们在做的时候,有一行是零,这个占一行,还有列呢,列有几列是不是你的背包的这个重量加上一个一,因为零有一个零,列是记录全零是不是这样子的,诶这就是这样子,那么待会我们说明这个VJ的含义。这个地方大家一定要搞清楚,否则待会写代码你看不懂表示什么意思,同学啊,表示。表示我们前面写的这个意思。小镇。我就把这句话粘过来啊,它这个表示在前。I个物品中能够装入容量为洁的背包的最大的一个价值,是不是刚才也是这样说的呀?
04:05
好,现在呢?我们完成初始化任务,初始化第一行和第一列。第一列。那么第一行和第一列就是同学们看到的这一行和这一列,其实你可以不不去处理,因为你不处理呢,它默认也为零,对不对,你可以不去处理,但是呢,我们这写上这一个地方代表我们,是我们什么意思呢?就是如果将来你这地方有别的含义,你也可以去修改,你不去改,你不去,现在不去设置也是可以的啊,注意这里。这里我们体现出有这个过程就行了。这里在本在。在本程序中,本程序中可以不去不不写。不去处理。不去处理,因为因为什么呢?因为默认就是零,但是你写上代表有有这么一个过程,明白吧,好,那我就写了NI0I小于,就快速写啊认识I加加。
05:08
那I加加过呢,我们这边写上VI0这个我就不不再解释了,好吧,零这个地方处理的是什么呀?这个地方是处理的将第一行还是第一列。后面这个是代表的列嘛,所以说把第一列设置为。设置为零没问题吧,紧接着我们再写一句话,Anti ti等于零,I小于什么呢?同学们,那这个时候I就小于。少一个V 0.ni加加,对I加加,然后这边写上什么呀?零在前边了,那么I在后边,这个也是为零,表示处理的是第一列。对不对处理的列,将D。一。哦呃,第一行了,这是行了,因为零没有变化对吧?将第一行设置为零没有问题吧,同学们。
06:07
还是比较简单的,那这边设置完了过后呢,同学们,我们现在可以输出一下,输出一下这个V,看看目前是什么情况,看看目前的情况啊,当然后面我们还要调整。还要去处理,现在只是让他看看一下这个情况。我们v.I。I加加。爱加加好的,那就或循环NT节。J等于零,J小于什么呢?V来一个I点认识。节加加没有问题吧,同学们,我输出一把,输出的时候呢,我就不换行了啊,那就VIJ。再加一个空格,这样好看,待会儿。加一个空格,那这边做完了之后,每输出一行,我们输出一个换行的符号。
07:02
好,目前的情况这样子的,我们运行一把,那运行过后呢,应该是全零正确的,这这块全零,也就是说目前呢,我们这块还没有做处理,现在呢,我们开始按照公式来进行这个迭代处理,来写段代码。根据根据前面得到的公式啊公式来来动态规划处理。规划处理。好的,非常的简单,那就开始写代码了,同学们for循环n ti等于一,为什么从一开始呢?大家想啊,各位同学,因为第零第零第就是第一行不处理了,第零第一行呢,它对应的下边为零,所以说我就跳过,跳过下边为零的第一行,那I小于什么呢?I小于我们V点认识对不对?I加加注意啊,我这里I等于一除以的相当于说。跳过。
08:01
跳过叫做不处理,这样写不处理DE1第一行,第一行应该是全零嘛,再不循环NT节等于一解,小于什么呢?各位同学,那节就应该小于,我们找一个零点认。哦,OK,解加加解加加。那为这个地方代表的是列嘛,我用V0 V0代表一行,它有这一行有多少多长,就代表有多少列,是不是这个叫代表不处理列。哦,不处理第一列。第一。第一列看清楚没有,因为我的I和节都是从一开始的,也就是说I是从一开始的。从1I。是从一开始的。开始的,那么结呢?结是从一开始的。
09:00
这点大家要看清楚好了,有了这个代码过后呢,我们就套用公式。我们这个公式其实前面已经写写的很清楚了,第一个我们把它打开。这句话已经处理过了,现在呢,是wi。大雨节的时候,我们就走下一个代码,也就是说理论是这样写,怎么处理呢?处理的方案是不是我们前面已经有过了,跟着老师思路啊,是不是他。是不是这样写的?但是这样写,你们觉得老师写的对吗?对不对,这里面是有问题的,大家看,因为我这个原先在推导公式的时候,这个I是从零的,从零开始来推的,但是你现在这个是从一开始的,因为你你看啊,你如果说你真的不去做修改,那么上来过后这个I就等于。一那相当于说找到谁了,找到。第二,一个物品的重量是不是因为下边要从零开始嘛,所以说这个地方我们要去减一,因为我们的程序。
10:03
程序的这个I是从一开始的。开始的,因此原来的这个公式中的这个W。W,这个I呢,要修改成什么呀?同学们修改成wi减一,这个大家能理解吗?要减一啊,没有问题,减一就对了。其他的不需要做改动啊,其他的不需要做改动,这个就完事了,Else if else else,就是说嗯,如果不是这样一个情况,咱们应该怎么去处理呢?就按照这个流程。对不对,实际上就是。就是这因为你前面这个条件不满足嘛,就是说你这个条件不满足,那反过来就是满足下面这个情况,下面这个情况我们是用的一个公式来推导的,大家看是不是这样子,来老师给他写一遍,打开它写,那这么咱弄过来肯定是错的,这根本就没大括号是吧,所以说这边改成小括号,这个能理解吧。
11:07
感效果,而而且呢,这个max呢,Max它是在max这个包下面的,因为我要引一下。这就可以了,但是这样写完过后还是错的,你们知道为什么吗?大家知道为什么,你看啊,这个VIJ这个是对的,VI减一这个也不用动它,但是你们想一想,原先这个VI我刚才讲过。这个value I才是前面讲的VI了,因此你这方要改成这个能理解吧,哎,要改成这个,这样改了过后还还有一个问题要改,同学们,你们知道哪个地方要改吗?大家看。你现在这个value I。是不是也是从一开始的呀,而实际上我们value呢,应该是从零开始,因为你你现在这个你现在I是从一开始嘛,所以说你这个地方也要减掉一个一能理解不,另外一个这这个地方这个I是不是也要减掉一个一啊,这才这才是对的呢。
12:09
好,我这里做个说明。说明一把,说明一下啊,还是因为因为因为我们的这个I,注意听是是从。从一开始的,在这个程序里面是从一开始的,因此公式要调整成下面的情况,因此公式需要调整成下面这段代码。这大家看看能不能理解啊,其实也不难,因为你想嘛,你你如果不减,如果你这样不减,不减一个一,你这个I上来就是1Y61是谁呀。是3000了,那直接跳过第一个了,就没去考虑它了,同样这个W也是一样的道理嘛,所以说这个简易是必须的啊,同学们好,我把它给大家格式化一下。好,这就写完了,同学们。
13:00
一个简单的背包问题就处理完了,那是不是这样子呢,我运行一下。OK,同学们,可以看到我们现在已经输出我们要的结果了,看到没有,诶,对不对,有要的结果,但是这个结果大家肯定很不满意,为什么呢?他只是把我们这个分配这个表给打出来了,是不是,也就是说它相当于把这个表给我们输出了,但是。你没有告诉我最后到底怎么放啊,其实我们最后这个方案应该是他吗。是不是这个方案是这个,你得告诉我,你把第几个商品放进去了,把第几个方商品放进去了,对不对,你放的是哪几个商品,你得告诉我呀,不然的话,我拿到这个结果,我看到这个表我们圈了,诶我知道,呃,最大值是3500,但是是哪里个商品呢,不知道。因此呢,我们这个代码还要做一点稍稍的调整,就是要记录我们的这一个。存放的路径,来,同学们,老师在这稍微修改一把啊,快速给演示一下。
14:01
好,现在呢,为了注意听,为了记录记录我们这个放入放入商品的一个情况,我定我们定义。定。定一个什么呢?二维数组。而这个二维数组呢,跟这个Y跟这个V的这个数组呢,大小一样,就是当我们什么情况下,我们放进去就完事了啊,我写到这来,那怎么写呢,我写一个。好的,也是一个二位数组吧P,比如说我们记得是一个路径,那么六一个int,它的大小仍然是N1,这边是M加一。对吧,我得记录你是一个怎样的存放情况,看清楚没有,那什么时候把它放进去呢,大家看。你现在没有机会放进去了,因为你什么什么时候放,你是用的一个max求职,因此这个地方代码在这玩不了了,就是如果你想记录我们商品保存的一个情况,到这个二维数组里面去,你靠这个简单的这个公式没有机会往里面存,因为你到底你这方只是拿到一个结果VI级它的一个值,但是他到底走的是这条线。
15:20
还是这条线你是不清楚的,是不是,所以说代码呢,我要修改一下,我要用一个简单的if else,注意听啊,因为为了为了记录记录商品。就是商品存放到包背包,背包。背包的情况啊,我们不能简单的,不能简单。简单的使用这个公式啊,一个简单公式,呃,不能使用上面的这个公式了。上面的公式需要干什么呢?诶需要使用if else来替代来来处理,也就是说公司还不能简单的使用,还是使用这个公司了,就是不能直不应该说不能直接使用啊。
16:16
不能直接使用上面的公式,应该用if else来体现,来体现这个公式。大家知道我在说什么吧?嗯,可能不太清楚是吧,我写了啊,衣服。写了。如果说。呃,原先这个情况。是不是这个情况啊,这个情况还是成立的,那么这个else里面我就要这样写了,同学们看我的代码啊。这个代码是不是,呃,应该怎样写呢?就是这两个值的大小,谁大谁小嘛,对吧,我把这个写到这来。如果这个哥们儿它小于后面这个哥们的值。大家知道这是什么意思吧,好,这个时候是不是我们记得是他呀?
17:01
是不是记得是他好,这时呢,我们注意听VI节。VI杰。他其实就是。这个字。是这样子吗?同学们是这样子的。应该是这样子,好,这个时候咱们就可以把这个记录下来了,把什么呢?把当前的这个情况记录到哪里呢?Pass,很简单一句话啊,Pass。好,这个时候我把它的I和解就拿到了。对不对,拿到了,那么我就得到一个一。就行了,其他情况不要说,为什么其他情况不要呢?你想一想,因为你只有在这种情况下,我们才会去,才会去往这个pass里面存,因为你最优的一最优的情况是从这个地方拿到的,对不对?最优的情况是从这一幕拿到的,所以说我们把这个情况写上其实就可以了,就是当这个条件满足,我们把放去这个情况是最优的,我们就把情况记录下来,记录下来过后呢,下面这个代码我们再运行,你会发现呢,没有任何影响,仍然是诶一样的。
18:08
哎,对了,我这边还少了一句话啊,因为还少了一个S,因为如果不是这个情况的话呢,我们怎么玩的呀。好,如果不是这个情况的话呢,我们。这个就不需要记了,我们直接用哪个做的呀?VIJ等于哪个呢?等于这个值。是不是?好,我们其实只要记录上面这个就可以了,因为上面这个情况是最优的,好把这个情况记录下来过后,我们下面就可以来输出最终。最后。最后我们是放入的。对,放入的哪些商品。大家知道怎么取吗?可能有些东西他说我遍历一下pass就可以了。好,我们我们先尝试这样写一下,你们看看看看能不能理解啊,假如我们便利我们便利这个pass,你看跟你想的一一不一样啊,我给他写一遍。
19:09
For循环it,呃,我给你写一下啊。I小于,我们这个pass点认I加加轴for循环NTJ等于零,J小于,注意听小于pass,我们这个I点认识好J加加,我现在输出啊同学们我输出。老师说哪一句话呢?我说我用格式化来写,好吧,我就说D这么个商品放入了。放入到哪里呢?放入到背包。是不是放个背包,我把哪个输出来呢?同学们I就可以了,因为我们这个地方存放在I才是表示第几个商品,是不是这样子,同学们是不是表示第几个商品,而且都不用再加一了,因为我处理的时候是从一开始的,所以说这个地方不需要再加一,但是你们你们注意,当我们输出这个情况的时候呢,跟我们想的有一点差距。
20:12
来我们看一下运行。运行诶你看他诶就没换行啊,不好意思,没有换行,喜欢。来看一下,你们看他打多少多少,打了这么多。打了这么多,显然我们并不需要这么多是吧,也就是说我们其实根本不需要这么多的数据,不需要这么多数据,那怎么办呢?你完全没有需要这么多数据的可能,那就其实这个地方是要这样写的,加个条件就是只有pass。I。解,等于一的情况下,我们才去处理,才输出,是这样子吧,同学们,那我现在再输出,你看跟我们想的还是不一样,你看诶,他说第一个放到背包,第一个放到背包,第一个放到,第二个放到背包,第三个放到,也就是说他。
21:07
你你你在做这个工作的时候是不是。有,不仅仅只有最后这个情况。不仅仅是,只有最后这个情况才有可能出现,我们这个if是不是同学们在听我说啊,也就是说现在为什么会输出这么多信息呢?为什么输出这么多信息,是因为你你这个一附条件的成立,不一定就是最后一次,他可能有好好些次都进到这里面来了,是这样的吧。那因此其实你真正要的真最终放进去的那个有效的那个结果应该是。从从后往前便利明白我在说什么,也就是最后的那个才是有效的,因此这个算法呢,这样输出是不对的,这样输出有冗余的数据。啊,我就写这样。
22:02
这样输出会。会把所有。所有的放入情况都便利,都得到,但其实呢,其实我们只需要朱婷,我们只需要最后的。最后的这个放入情况。是不是我们是需要最后放入的,放入的那个情况就是你放了好几次,其实最终的那一次才是我们要的嘛,那现在怎么来便利呢?这个要动脑筋啊,同学们要动下脑筋,动脑筋,我给大家写一写。动脑筋非常的简单,你要动脑筋就很快就能写出来来,我先写个I,大家看我的代码。稍微有点麻烦啊。点N减一,我先求出,我先求出这个pass数组的这个有多少行。再求出pass路径,再来看一个啊,同学们,我写一个。
23:00
零点刃。点N再减一,这个呢是求出它有它最大的列,就是它的列的那个下标最大值,这个应该这样写啊,就是行的最大下标。下面这个是列的最大。最大下标能理解吧,好,现在这个就比较好解决了,我就写个Y循环,大家看能不能看懂,只要I大于零,大家看我这个I和解已经到最大下标了,也就是说我其实要逆向去便利。因为你逆向便利才会拿到先拿到最后的嘛,你不能从从前面便利,前面便利,那有可能那前面他不是最后的结果呀,是不是,所以说我要逆向便利,这写个情况啊,叫从后。应该是从数这个pass数组的pass的最后开,最后开始开始找。
24:01
开始啊,开始找好,那么只要I大于零,并且解它也大于零的情况下,我就可以一直去找。那怎么找怎么找呢?来看一下。我在这写的代码你们就明白了,好,那如果说这个pass它I节注意听啊,I节它是不等于啊,它是等于一的,说明你这个点放放置曾经放置过。背包放这个数据,好,我现在就可以输出了。这个时候我们就可以输出刚才这句话,诶,就是输出这句话啊。那说完了过后有一个特别重要的动作,我看大家能不能理解就节呢,就要减掉。W。I减一,为什么呀?因为你你最后这个放的放完了过后,你按照这个背包的容量来讲,它应该要减。因为你是从后,你是从后放吗?那后面放,假设我们放了一个I这样的物品,那么它的它所占的重量。
25:08
是不是就是这么这么大一个重量啊。这么这么大一个重量,那么再完这个最这么大一个重量,重量过后你再往下面走啊,这么大一个重量啊,这么大一个重量,你放完了过后,那这个结它的背包容量还有多大,是不是要调整了,你不调整肯定是不行的,那到时间找的就不对了,好处理完了过后这个地方。I要减减,因为你已经找到一个存放商品了,I就减减,再找下一个。好值,这个情况就能拿到我们最终的结果来运行一把,同学们看走起来。哦,我再检查一下啊,对的没问题,对的没问题,I减1I减一减减没问题,没问题,好OK,好的运行。好,我们看到最后结果就已经出来了,你看第三个商品放到背包,是不是我们打印出来也是这样一个,你就是从后从后嗯往前看的一个效果,第三个商品是不是我们最后去处理的时候,是把电脑,电脑是放到这里面去的,然后再把这个第一个又重新变变进去了,所以说最后这个结果呢是呃,第三个商品放入背包,第一个商品也放入包,这是最后的这个结果。
26:27
代码就写完了。啊,代码就写完了,其实也不是很难,对不对。这说的再简单一点,其实就是把我们这统计的这个公式进行了一个灵活的处理,写到了我们这个代码里面去,仅此而已。那当我们把这个代码写完,你们就可以去随意玩了,比如说这个物品的重量,你可以多写几个。然后当然这个要对应啊,你这有几个物品的重量,那么下面就应该有几个价,价格跟它有一个对应的关系。跟它有个对应的关系,这样呢我们这个代码才能正确的运行,这就是我们讲的背包问题的求解,大家理解一下。
我来说两句