00:00
它的公式呢,已经出来了,这个V0等于V0,解等于零,这句话我先解释一下,这句话就代表什么呢?表示。表示注意听,表示刚才的那张表就是填入,填入的那张表,注意听啊,它的第一行。第一行和第一列,第一列是什么呀?是零。四零。是是这样子的,我们上来过后是不是先把。第一行和第零列全部制成了零的呀,是不是这样子的?好,那么我们再来看第二个,这个地方表示什么意思呢?各位同学。这句话应该表示是当我们注意听啊,当我们要去增加一个I这个商品的时候。如果这个新增加的I的这个商品,它大于当前这个背包的容量,那么这个时候我们直接就把它上一个格子的那个装入情况付给他就行了,大家知道我在说什么吗?就是说当。
01:06
准备准备加入的新的,新的就是又给我们增加一个商品,准备准备新增的啊,准备加入新增的这样写。新增的商品。商品注意听,商品它的容量大于大于什么呢?大于当前背包。注意,听这句话有点不好理解啊。当前背包的容量十。就直接直接使用上一个单元格的,上一个单元格的一个综述情况。那上一个上一个单元格的那个装入策略装入。装入策略。大家知道我在说什么吧,就是刚才我们不是讲过,诶你看刚才我们在在装这个电脑的时候,装电脑这个电脑呢,它是三档,但是我现在我现在当前这个当前我们这个才一磅,那你就装不进去,装不进去就直接从上面这个粘下来了。
02:15
你装不进去就直接,因为上面这个已经是比较优的嘛。所以你就直接把它拿下来就完事了,下面这个情况有点不好,不好讲面这个情况要好好的理解一下啊。下面这个情况应该是什么呢?注意听当。当什么呢?当这个,呃,就是这样说的,当。准备加入的,加入的新增的商品。商品的。这个容量是干什么呢?小于等于什么呀?当前背包的容量说明什么问题?说明什么呢?说明你这个新增的商品是可以尝试着往里面装一装的。
03:00
因为我不知道你新的商品来了过,是不是已经变成最大的了,对不对。所以在这种情况下呢,我们可以求一个最大值,就应该等于什么呢?大家看这里,大家看这样子,那么这个是应该安装的策略,就这样子的,那么装入的策略。装入的这个这个方式应该是怎样的呢?求一个最大值,求什么最大值呢,大家看。这个大家看看是什么意思。这个大家看出来没有,这个就是他,诶我我写一个这个就是。就是上一个单元单元格的单元格的那个装入策略。装入装入的最大值。是不是装置策略就是最大值嘛,也就是说有一种可能性就是。我把这个新的东西装进去过后呢,还不如原先那个。多,这是一种策略,还有一种策略就是我要干什么呢,大家看这个地方。
04:03
大家还看看这个VI表示什么意思,同学们注意听啊,这个VI是不是表示表示当前商品的价值啊?商品当前商品的价值,这个看出来了吗?VI啊,当然有些同学老师这个写到后面我看不到,好,我把这个调到前面去,这个公式呢,把它写在前面去,应该更好看一点。呃,更好理解一点。好,这个就就看懂了吧,VI表示一个意思,大家看懂了吧,下面这个大家看。这个你们往往这边走啊。这大家大家再看一下这个表是什么意思,能看出来吗?这个这个表示的是。这个表示的是什么呢?就是剩余的空间。就是剩余的空间。你看啊。这个V减I是表示。
05:00
装了A减一个商品到剩余的这个空间时候的最大值就是装入。装入什么呢?装入这个I减一个商品。挨减一个商品到哪里呢?到剩余空间。剩余空间,因为你你现在新商品新增加了嘛,所以说我这可能有剩余空间,剩余空间其实就是这个这个节俭。Wi。大家看到没有,这是不是剩余空间结,是不是当前的这个背包的容量?Wi代表的是什么呀?Wi是不是代表的是你这个装入I这个商品过后的一个要占用的空间,那么解减去WS是不是就是我剩余的空间?对,所以说这个这个整个这个表示装入I减一个商品到剩余空间的最大值。最大值,好,这个就说完了,大家看理不理解?
06:02
那在然后再在这里面求个最大值,就是我们当结大于等于,当结大于大于等于I I wi的时候呢。的一个中枢策略,好,最后我们得到这个公式就出来了,就是什么呢?就这个公式。这个公式就出来了。好,这个是不是有点绕啊,是不是有点绕,听起来好像有点绕,我再我再给他捋一捋啊,我再给他捋一捋啊,不着急啊,不着急,我再捋一捋啊,嗯,第一个我相信同学们没有问题。很好理解,这个也很好理解,你你准备装的这个商商品的它的容量都已经大于你背包的容量了,你肯定没法装嘛,你只能按照上次的这个策略来装是吧,这个也好,利益关键是下面这个,下面这个是就说当你现在这个背包的容量。它已经大于,它大于你的这个准备新加的这个商品的时候,你就有有可能把这个新增加的商品装进去,但是你不知道装完过后到底大不大,怎么办呢?你就这样求的。
07:08
你你就求,假如我们假设还小,我就还采取前面那个策略,但是这只是一种假设,还有一种可能性是什么呢?还有一种可能性就是这个VI,就是我我把这个当前这个商品装进去,再加上一个什么呢?因为你装完了过后,你不是还有剩余的空间吗?然后再把这个剩余的。空间占用的最大值放进去,这个就是剩余空间对应的那个最大值,就是这样写啊。这个地方。这句话。这句话就是装入埃及一个商品的时候。那么这个I减一个商品,到底是不是把I减一个商品全部装进去,这个不一定。明白我的意思吧。这个不一定啊,就是装入埃减一个商品的时候,到剩余空间的最大也就上一次。
08:02
我们我们上一次那个内部,并且还要满足装的这个剩余空间的时候,最大的这个值就是这个意思,我再说一遍啊,这个你这个这虽然写的是I减一这个,但是你不一定把这个I减一的商品全部都装进去的,不一定。因为你上一次到底有没有全部装进去,这个不好说明白吧,诶这点大家知道了,所以说这个就可以理解什么呢?就是用当前商品的价值加上你剩余空间能够装入的最大值啊,最大的这个价值,所以说这个就就很好理解了,对吧?好,这这个地方我再捋一捋思路。好,捋捋这个思路就就完事了啊呃,VI就是这个,把这往这写一下。往这儿来一下啊。就这么几个逻辑,大家看理不理解,我把这个标成一个纯色,大家看起来应该清晰一点,好把它放小一点,主要是对这几句话的理解,我觉得就是要把它理清楚就可以了。
09:01
好,大家看明白了啊,Vig表示什么意思?表示当前商品,Vig表示装入I减一个商品到剩余空间的最大值啊,不一定装进装进去了,所以说当I等于等于,当结大于等于wi的时候呢,我们就要求一个最大值就行了。好的,那同学们,呃,关于这一个基本的思想,我就说到这,就说到这,那么大家看看理不理解。啊,这样子,如果我不理解,我们按照这个公式再来给大家,呃,这不是刚好有一个比对的公式吗?我们把这个公式拿过来给大家再再验一下。这个公式很重要,就说你现在能不能把这个写出来,关键是这个公式能不能写出来,其实代码并并不难,代码并不难,来,我们把这个公式给大家拿过来,我们验一下。看看是不是按照这个流程来玩的。好简单的,给同学们验证一把我们这个思路。
10:02
好,我就找一个吧。我就找。呃,我我这样走啊。我找一个微。V。V1V1,这这个来验一下好吧,我们来验证一下这个公式。验证。验证公式,验证这个公式。好,现在VIVI。V1V1,那么现在是我们实际是1500,是这样子吧,1500没有问题吧,同学们好,如果按照这个公式来讲的话呢。这个我们要去判断wi和J的关系,所以说我先把I写出来,这个时候我们来分析一下,现在I呢是等于一,节呢也等于一,就现在你的容量呢也是一,好,这是第一步,我们推出来了,第二个我们来看此时此刻wi是多少wi。We其实就是你这对应的W是这样子吧,同学们,那we是多少呢?诶we是不是就代表第一个商品的。
11:10
重量是一就推出来了,好的,我们再来看第三步,那么你现在这个节也有了,对吧,结也有,结也有了,我们看它们的关系就是W。I。和wi和J的关系是一个什么样的关系呢?Wi的wi呢是一,所以说实际上就是wi。W1W1是等于一的,解呢,OK,解也是等于一的,因此它满足哪个条件,满足第二个条件,哎,满足这个条件解大于等于wi,所以说它这个公式呢,就应该是这样写的,我把这个公式拿过来好吧。这个公式就应该按这个推导。按这个推导不着急啊,同学们。
12:01
好,这个东西讲起来稍微有点费劲,好我们看一下,那现在这个V1。J1,它应该等于多少呢?朋友们,我们来写一下max。OK,那这边就应该是I减去一个一,OK ii减去一个一的话。I减去一个一是多少呀?I减去一个一,I减去一个一,那就是零呢?是零吧,零节是什么呢?节是一,它就是一,OK。好,那这边还有一个V1。在。加上一个V,大家看I减去一又是零对不对,又是零,好的,那下面这个节是几节,是一减去一个wi wi就是你刚当前这个你你放进去它要占的空间吗?它要占的空间。呃,刚才已经说了,是一好,现在我们就可以得到这个结果了,就是Mac是什么呢,同学们看。
13:02
V01V001,那当然是零了,好,这个。就这个值零一嘛,零一就这个值嘛,好,那就是第一个是零,第二个呢,我们看V1 V1就是一千五呀。是不是1500,一千五再加上。后面这个V0V00肯定还是零嘛,所以最后这个值最大值就是1500,看出来了没有,好我们再建一个啊,同学们不着急,同学们,因为这个地方呢,稍微有点麻烦,我们验验清楚,好还有一个我们来验一个大一点的就这个。这个应该是几了呢?同学们是不是应该是三四,因为按下边来说这个是0123,按这个下边来说是01234,好,我们来验一下三四这个对不对,注意听啊,同学们稍微的有一点点麻烦,不着急,四等于来我们仍然按照这个套路来走。
14:00
好,我们来做一个说明。第一点,我们看现在I等于几,I等于三没有问题吧,解等于几?同学们解是不是等于等于四啊,很好理解,因为你I等于ii就是三八节就是好,我们主要是要拿到wi wi呢。Wi其实就是W3了,是这样的吗?同学们W3,那同学们W3等于几啊,是不是电脑啊,W3是不是它的容量就三了,这个能看出来吗?W3嘛,就是你第三个商商品,它的重量就三嘛,好就写完了,那么企业现在呢,已经是四了。各位,此时此刻是不是结?等于四,它是大于等于这个W。那个I这个I wi,它是它是三嘛,因为四大于三。就是四是大于等于三乘以的,好,现在呢,我们仍然要用这个公式,是不是同学们还用这个公式再继续来玩一把,一下就出来了啊,来同学们看一下,现在呢。
15:07
这边就是三,这边就是四。好,呃,它前面这个公式仍然是I减一,I减一显然是二,就是上一个格子,上一个格子四还是四,是不是这个就是上一个格子的那个最大的,嗯,上一个格子的一个策略,好,紧接着再写VI减一,现在是三减掉一个是V2。是不是V2啊。哎哎,这不对啊,是这个直接是VI了,不要减不要减,就是当前这个啊,再加上后面这个。后面这个应该是多少呢?I减一,好,I减应该是二,没有问题吧,就在这个这个这么多商品的情况下,然后呢,剩余空间是多少呢?解是等于四的减掉一个wi ws等于等于三的好。
16:02
那这样算下来不就是一吗?好,现在我们接接着往下面改,后面这几个数字不着急啊,同学们,那现在你。呃,24V24是多少?同学们查一下V242下标为零,124,就它,你看上面这个格子就3000。是不是3000,同学们说你这第一个值3000。没有问题吧,同学们好,3000找到了,然后呢,V3 V3是哪一个呢?就是我们的第三,相当于是我们的。V3的话。呃,微商就是我们第三个商品的这个价值,第三个商品价值是2000,是这样子吧,2000。好,再加上我们这个V21 V21是多少呢?V2应该是在这上面啊。012嘛,一这个是不是一千五啊,好,我们就加上一个1500,同学们1500,因为我找到这个值了,找到这个值,那么现在说白了就是从这个3000和三千五里面找一个最大的。
17:13
诶,这个就不用写那么多了,其实已经看到了这个结果就应该是2000加1500,因为它是最大的,而我们这个结果呢,也是2000加一千五组成的。好,同学们,这个就是一个公式的一个讲解,不知道大家听懂了没有?当然这个呢,我也给他走了一圈对不对,这里面最主主要的问题就是要理解这个公式,他怎么来的,说白了就是,嗯,就是如果我能,我这个新的商品装不进去,我就采用原先的这个安装呃装入的策略,如果我这个新的商品能够呃装到这个背包里面过后呢,我就要看哪一个更大,是原先的这个策略更大呢,还是说我把这个新加的商品加进去以后,再去加上我剩余空间对应的这个最大值。
18:05
两个的和,看哪个更大,如果这个后者大,我就用后面的方案,如果前者大呢?我仍然用前者的方案,讲完了。理解了吗?好,这就是整个动态规划算法背包问题的一个思路的图解,那一会呢,我们代码实现。
我来说两句