00:00
同学们,我们继续来学习下一个算法,下一个算法呢,要给大家介绍的是动态规划算法。还是老规矩,我们有一个应用场景,或者说一个具体的问题,来引出我们这个动态规划算法。那么这里有一个非常经典的问题,叫做背包问题。背包问题呢,他是这样描述的,OK,他说有一个背包,这个背包的容量呢为四磅。就是这个背包可以装四磅。重的,呃,物品,那么现在有以下一些物品,比如说吉他,吉他呢,用这个G表示的这个吉他呢,它有一磅重,它价值1500。还有一种物品叫音响,音响呢,用S表示的,它有四磅重。它的价值是3000块钱。还有一种商品呢,是电脑,电脑呢有三磅重,它的价值是2000块钱。
01:00
OK,大家可以看到这张表很清晰的描述了物品的一个重量和它的价格。那各位现在的要求呢,也非常的简单,他说要求达到的目标,为什么呢,装入的。背包的总价值最大。并且重量不要超出,也就是说,在不超出容量的前提之下,我们尽可能装入价值最大的这么一些物品。你可以组合。第二个他要求装入的物品不能重复,什么意思呢?比如说我们装入了。一部吉他,我们就不能装?再装一部吉他,也也就是说这个背包问题是零一背包问题,还有一种背包呢,叫完全背包,完全背包呢,它就不去限制你物品的。个数了,我们这儿。这有一个要求装入的物品呢,不能重复,也就是说是零一背包问题,同学们对这个问题是不是大家应该比较清晰了,也比较简单,这个问题对不对?说白了就是有一个背包里面装东西,东西怎么装,不要超出重,不要超出我们的容量,并且呢,价值最高,就是这么一个问题。
02:15
那么我们来看,对于这种问题,他一般是怎么来求解呢?是用一个叫做动态规划算法来求解的,注意听哈,这个还是很有意思的。那么动态规划呢?也叫dynamic programming。他的核心思想我们先聊一聊,他是将一个大的问题划分为小的问题进行解决。就是先把一个大的问题。分解成小的问题,从而一步一步获取最优的处理算法。那当然有些同学老师,诶,这个把大的问题分解成小问题,跟前面讲的分支算法好像很像,哦,对的,它是有相似的地方,但是也有不同地方,我跟他聊聊。动态规划呢?它跟分支算法很类似,其基本思想也是将待求解的问题分解成若干子问题,然后解决子问题,最后求子问,通过这些子问题得到原问题的解。
03:10
但是有不同的地方是,与分支算法不同的是,它适用于动态规划求解的问题。什么意思呢?就是说经分解得得到的子问题往往不是相互独立的,这点跟我们的分子法是有不一样的。分子法大家还记不记得我们最经典的这一个?这个汉诺塔你两个盘放过去,跟你有三个盘没有影响,是不是就说我两个盘就是两个盘,三个盘就是三个盘,那么这个动态规划算法不一样。它是它往往得到的子问题,往往并不是相互独立的,什么意思呢?即下一个,注意听这句话啊,下一个子阶段的求解是建立在上一个子阶段解的基础之上的。也就是说你要得到下一个解,那么其实你是要参考上一个得到的这个解的。
04:06
也就它是有,它是有一个关联的关系,而我们分支法呢,往往没有,你比如说我们。我们移动两个盘。和移动三个盘它没有关系,你把两个盘我移我你把两个盘移动过去了,和我把三个盘移动过去,它是比较独立的一个问题。对吧,它是独立的,问题是这样子,111个关系好了,那动态规划呢,它往往是通过填表的方式来逐步推进的。得到一个最优解。各位,那现在呢,我就把动态规划算法给大家聊了一下,下面呢,我们就准备给大家用动态规划算法来完成背包问题。同学们,那刚才讲解的动态规划算法先跟大家聊到这儿,一会儿呢,我们用代码来实现背包问题。
我来说两句