本文主要是介绍队内第一次集训——基础DP(讲义篇),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
之前比赛吃太多DP的亏了....好多题都看不出DP,还有的是看出来了但是动态转移方程推不出来,所以在此准备先恶补DP...
废话不多说,开始正题
DP其实就是,把一个大问题分解成若干子问题,通过解决若干子问题来获得最终结果,这样说起来有点像分治,但实际上并不是,因为DP需要每一步都保留目前的最优解,同时满足无后效性。无后效性就是过去已经考虑过的情况就不会对后面产生影响了,直接就不用理他们。通过每一步都保留当前最优解,来保证到最后的时候得到整个问题的最优解。
在这里主要讲解DP中最经典的入门题,背包问题
01背包
先简单介绍一下01背包。0和1分别代表着不取或者取这个物品。因为01背包问题通常是给你一个v体积的背包,然后给你i个物品,每个物品都有自己对应的体积和价值。然后问你如何放东西可以让背包的价值最大。
最最容易想到的当然是dfs,把所有情况都来一遍,可是在面对1e5的数据范围下,每种物品两种方式,那就相当于2^n次的巨无霸时间复杂度,是肯定要TLE的,所以这时候,DP就派上了用场。
DP是怎么看待这个问题的呢?首先回到概念本身,DP是将一个大问题分解成若干子问题。在这里,很明显就是分成每一个物品取或者不取。最优解又怎么理解呢?首先从二维数组的解法开始讲。dp[i][j]表示放到i个物品时,体积为j的情况下的背包最大价值是多少。刚开始所有dp数组对应的值都是0。然后放入第一个物品时,开始更新dp[1][j],如果j<物品的体积,也就意味着这个物品它放不进去,所以只能继承放0个物品的时候的最优解也就是0,到了>=j的时候,当然是放当前物品比较好,毕竟之前价值都是0,只要你能进去,你就是老大。所以这一次更新后,dp[1][j](0<j<v[i])还是0,放不进去没办法,剩下的都变成了第一个物品的价值。然后放入第二个物品,同样的,比自己体积小的时候,放不进去,那就看放一个的最好情况,就是当前的最好情况,谁叫自己放不进去只能靠第一个物品单打独斗呢..然后能放进去以后,就需要一番比较,这里咋比呢,就是比放入这个东西比较赚,还是不放入这个东西比较赚,不放入这个东西的价值很容易想到,就是p[1][j],现在开始放第二个物品了嘛,放之前的最好条件肯定是放第一个物品时候的情况。放入这个东西的价值呢?你想放入这个东西,前提就是,你有空间能放入这个东西,所以这里,就需要腾空一些体积放第二个物体,也就是a[1][j-v[i],放入一个物品的情况下,能放个第二个物品到达当前体积的体积就是我们需要的数据,看看这个时候,放入第二个物体好还是不放好。所以每过一个物品,当前dp都会存下放前面所有物品的最优解,所以以后都不用管前面放过的物品了,也就是所谓无后效性。
当然,二维数组,有一个维度还是放体积的,空间占用也太大了,如果有一道01背包题,不但体积大,而且数量多,如果用二维数组时间,肯定凉凉了,所以机智的人们又想到了一个牛B的办法,叫做滚动数组,在滚动数组的优化下,可以将二维数组压缩成一维。滚动数组的原理是什么呢?其实就是覆盖。仔细想想刚才我们的流程,是不是第i个物品,只需要考虑放完i-1个物品后的情况,再之前的因为无后效性根本就不用管了,放在那里浪费空间,所以我们需要的就是,更新这次以后,就不要过去的了,反正留着没用。那怎么做呢?先放一波代码:
for(int i=1;i<=n;i++){for(int j=v;j>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+c[i]);}
}
这是啥意思呢,i就是指放第几个物品,下面就是我们刚才说的那种覆盖,因为它判断的是当前的值或者dp[j-v[i]]+c[i]谁大,然而由于里面那层循环是从v到v[i],在回去的过程中,dp[j-v[i]]所对应的值没有被变过,一直是上一次更新的值,也就是dp[i-1][j-v[i]],所以就实现了我们需要的事情。
01背包初始化问题(完全背包和普通背包)
01背包如果前期dp全部初始化为0,那么就是不限定最终背包内容量的求最大价值,如果出了dp[0]=0,其他都是inf(无限大),那就是完全背包问题。
如何理解这个呢?
首先如果全是0,那么它可以从任意一个体积来推出当前状态,如果除了0都是inf,那么如果要更新值,一定是需要从0过来的,因为其他的无限大加价值比无限大还要大动不了,从0过来后不断更新,那些被更新的就是说踩在前物的基础上可以来到当前体积,那么dp[v]就是想到的值。
完全背包
完全背包就是说所有的物体都有无限个的时候背包最大价值是多少
如果二维实现就是先放一个该物体,再放俩,再放仨,直到背包全空都放不进这么多东西。其实完全背包你还要认识到一个本质问题,完全背包说是无限个物体,其实并不是纯粹的无限个物体,它是有限度的,也就是拼命塞该物体,一直到背包塞不下就停了,不是真的无限个在那里试。
这时候就要用一个很强的办法,也就是前面提到过的滚动数组。
单论代码两者特别相似,就只用把里面那层循环改成v[i]到v就可以了,为什么呢?因为你想,01背包的滚动数组实现,是因为dp[j-v[i]]始终是没改过的,如果是v[i]开始,那就是前面也被改了。如果背包够放两个了,由于前面已经被放一个更新了,你到该体积的时候判断的时候本身就是判断放两个会不会更好,也就是你这样遍历到v,就是能放多少该物体就放多少个看看会不会更好
这篇关于队内第一次集训——基础DP(讲义篇)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!