理解DP(一) 2019-06-30

理解DP(一)

author:thy from BUAA

初见

想写一篇给初学者的人人都看得懂的DP文章dynamic programming(可以理解为动态刷表法 其实这里的programming并不是编程而是规划、设计表格的意思) 关于动态规划的概念,算法导论已经说得很清楚了这里再说一点个人理解。首先动态规划解决的问题具有如下三个特性:1.最优子结构: 如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。2.无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。3.有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。这三个性质在之后的讲解中会不断提到。

背包

记忆化搜索与动态规划——以01背包为例

n个重量和价值分别为wi,vi的物品,从中挑选出总重量不超过W的物品,求所有方案中价值最大的

input:n = 4 (w,v) = {(2,3),(1,2),(3,4),(2,2)}W = 5

output:7 (select 0 1 3)

朴素方法

首先我们从最朴素的想法,看一看每个物品是否放入背包进行递归搜索:

int n,W;int w[MAX],v[MAX];//从第i个物品开始挑选总重小于j的部分int rec(int i,int j){ int res; if(i == n){//没有剩余的物品了 res = 0; }else if(j < w[i]){//无法挑选当前物品 跳过 res = rec(i+1,j) }else{//可以选 那么选不选都试试 res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); //rec(i+1,j) 不选 跳过选下一个 //rec(i+1,j-w[i])+v[i]选择当前的 占用了w[i]的体积 获得了v[i]的价值 } return res;}

递归深度为n,每一层需要两个分支搜索,最坏情况是O(2^n )。

记忆化搜索

我们可以看到,圈中的地方有重复的计算,那么我们不妨记录一下每次递归的结果,如过需要重复计算直接拿来用。

int n,W;int w[MAX],v[MAX];int dp[MAX][MAX];//初始化为-1//从第i个物品开始挑选总重小于j的部分int rec(int i,int j){ if(dp[i][j] >= 0){ return dp[i][j]; } if(i == n){//没有剩余的物品了 res = 0; }else if(j < w[i]){//无法挑选当前物品 跳过 res = rec(i+1,j) }else{//可以选 那么选不选都试试 res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); //rec(i+1,j) 不选 跳过选下一个 //rec(i+1,j-w[i])+v[i]选择当前的 占用了w[i]的体积 获得了v[i]的价值 } return dp[i][j]=res;//记录结果}

递归只有在第一次调用时会被执行,而i和j的组合一共只有nW种,故而只需O(nW)的复杂度即可解决,这种方式称为记忆化搜索。

抽化为动态规划

根据记忆化搜索的启示,不妨看一下记忆化数组。根据我们的递归搜索,记dp[i][j]为从第i个物品开始挑选总重小于等于j时,总价值的最大值。于是,有

[ dp[n][j]=0\dp[i][j]=left{egin{aligned}&dp[i+1][j]quad(j < w[i])\&max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])quad (其他)\end{aligned}ight.]

公式看出选不选第i个物品是受到第i+1个物品影响的故而填表的时候是逆序的

ij012345
0023567
1022466
2002446
3002222
4000000

int dp[MAX][MAX];int solve(){ for(int i=n-1;i>=0;i--){ for(int j=0;j<=W;j++){ if(j < w[i]) dp[i][j] = dp[i+1][j]; else dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]); } } return dp[0][W];}

由此 我们已经有了从记忆化书所中抽象出的动态规划表格了,但是我们定义的dp数组是逆推的,更为常见的定义如下:

[ dp[i+1][j]从0到i+1物品中选取总重不超过j的物品时最大的价值\dp[0][j]=0\dp[i+1][j]=left{egin{aligned}&dp[i][j]quad(j < w[i])\&max(dp[i][j],dp[i][j-w[i]]+v[i])quad (其他)\end{aligned}ight.]

int dp[MAX][MAX];int solve(){ for(int i=0;i<n;i++){ for(int j=0;j<=W;j++){ if(j < w[i]) dp[i+1][j] = dp[i+1][j]; else dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]); } } return dp[n][W];}

空间上的优化

(dp[i][j])是由(dp[i-1][j])(dp[i][j-w[i]])两个子问题递推来的,这就要求我们倒序地以(j:Wightarrow w[i])的顺序

来进行内层循环(如果是顺序的进行的话就相当于(dp[i][j])(dp[i][j-w[i]])推导而来与题意不符合)

至此,我们就得到了01背包的抽象过程

def ZeroOnePack(dp,v,w){ for j from W to w[i] dp[j] = max(dp[j],dp[j-w]+v)}dp[0...W] memset to 0for i from 1 to n ZeroOnePack(dp,v[i],w[i])

如果要求背包必须装满,那么初始化时候可以吧dp[1...n]数组初始化为-1(即负无穷),dp[0]=0,因为按照我们的定义,只有容量为0的背包在什么都不装的且价值为0的状态下被“装满“,其他都属于无解的非法状态

满背包代码

memset(dp,-1,sizeof(dp));dp[0] = 0;for(int i=0;i<n;i++){ for(int j=p;j>=cost[i];j--){ if(dp[j-cost[i]]!=-1 && dp[j] < dp[j-cost[i]]+value[i]) dp[j] = dp[j-cost[i]]+value[i]; }}

输入规格问题

如果输入的背包重量很大,极有可能造成数组过大MLE,复杂度O(nW),也有可能TLE,因此如果背包的容纳重量很大,但是物品总价值max_n*max_v很小,可以考虑对dp数组变形:

(dp[i+1][j])前i个物品挑选价值总和为j时的最小重量,不存在时为INF

(dp[i][j+1]=min(dp[i][j],dp[i][j-v[i]]+w[i]))

最终答案是[dp[n][j]<=W]的最大的j这里就不给出代码了 读者自行验证即可。

完全背包

n个重量和价值分别为wi,vi的物品,从中挑选出总重量不超过W的物品,求所有方案中价值最大的。每个物品可以挑选任意多件。

inputn = 3(w,v) = {(3,4),(4,5),(2,3)}W = 7output10 (0号选1件 2号选2件)

(dp[i+1][j])从前i种物品中挑选总重量不超过j时的价值最大值,那么递推关系为:

[dp[0][j] = 0\dp[i+1][j] = max(dp[i][j-k*w[i]]+k*v[i]) quad (k>=0)]

按这个思路我们有朴素的如下代码:

int dp[MAX][MAX];int solve(){ for(int i=0;i<n;i++){ for(int j=0;j<=W;j++){ for(int k=0;k*w[i]<=j;k++){ dp[i+1][j] = max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]); } } } return dp[n][W];}

这构成了一个三重循环。k最多是从0到W,因此复杂度为O(nW^2),这样并不是我们所期待的。

ij01234567
000000000
100044488
200045589
3003467910

我们观察表格结合代码注意到,在(dp[i+1][j])中选择k个的情况,已经在(dp[i][j-w[i]])的计算中选择k-1个是相同的,所以在(dp[i+1][j])的递推中k>=1部分的计算已经在(dp[i+1][j-w[i]])的计算中完成了,由此我们有如下变形:

[quad dp[i+1][j] ][= max(dp[i][j-k*w[i]]+k*v[i])quad k>=0][= max(dp[i][j],max(dp[i][j-k*w[i]]+k*v[i]))quad k>=1][=max(dp[i][j],max(dp[i][(j-w[i])-k*w[i]]+k*v[i])+v[i])quad k>=0(相当于k+1代替k)][=max(dp[i][j],dp[i+1][j-w[i]]+v[i])]

这样一来,就无需k的循环了,可以在O(nW)时间内解决问题

int dp[MAX][MAX];int solve(){ for(int i=0;i<n;i++){ for(int j=0;j<=W;j++){ if(j < w[i]) dp[i+1][j] = dp[i][j]; else dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]); } } return dp[n][W];}

空间上的优化

只需要将01背包的内层循环倒过来即可。

仔细思考一下不难发现,之所以01背包要倒序进行内层循环,正是为了保证每个物品只能选择一次。而完全背包可以不限次数地选择,所以考虑加选第i件物品时,就有可能用上[dp[i][j-w[i]]]这个子结果,事实上,从上面减小时间复杂度的推导中也不难看出,我们用到了相同i循环下j循环之前的结果(即(dp[i+1][j-w[i]]+v[i])),故而要求内层循环j从(w[i])到W。

int solve(){ for(int i=0;i<n;i++){ for(int j=w[i];j<=W;j++){ dp[j] = max(dp[j],dp[j-w[i]]+v[i]); } } return dp[W];}

于是我们也有了完全背包的抽象过程

def CompletePack(dp,v,w){ for j from w to W dp[j] = max(dp[j],dp[j-w]+v)}dp[0...W] memset to 0for i from 1 to n CompletePack(dp,v[i],w[i])

多重背包

n个重量和价值分别为wi,vi的物品,从中挑选出总重量不超过W的物品,求所有方案中价值最大的。每个物品可以选择的件数不一,给出输入数组m,mi为第i件物品的件数。

此题和完全背包非常类似,同样地从朴素的方法出发,对于第i件物品有mi+1种策略,不取,取1件…取mi件,由此我们有:

(dp[i+1][j]=max(dp[i][j-k*w[i]]+v[i])quad 0<=k<=m[i])

同样的三层循环,并不是我们想要的效果,必须要优化。

优化一

引用自崔添翼巨巨的背包九讲

将第i种物品分成若干件01背包中的物品,其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1; 2; 2^2 ; 2^(k-1);m[i]-2^k + 1,且k 是满足m[i]-2^k + 1 > 0 的最大整数。例如,如果m[i]为13,则相应的k = 3,这种最多取13 件的物品应被分成系数分别为1; 2; 4; 6 的四件物品。分成的这几件物品的系数和为m[i],表明不可能取多于Mi 件的第i 种物品。另外这种方法也能保证对于0到m[i]间的每一个整数,均可以用若干个系数的和表示。这里算法正确性的证明可以分0 ... 2^(k-1) 和2^k...m[i] 两段来分别讨论得出,希望读者自己思考尝试一下。这样将第i种物品分成了O(logm[i])种,复杂度转化为O(W∑logm[i])

代码如下:

#include<iostream>using namespace std;int v,n;int value;int cost;int m;int dp[30005];void zeroPack(int cost,int value){ for(int j=v;j>=cost;j--){ if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value; }}void completePack(int cost,int value){ for(int j=cost;j<=v;j++){ if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value; }}int main(){ int t; cin>>t; while(t--){ cin>>v>>n; for(int i=0;i<n;i++){ cin>>value>>cost>>m; if(cost*m >= v){ completePack(cost,value); continue; } int k=1; while(k < m){ zeroPack(k*cost,k*value); m = m-k; k *= 2; } zeroPack(m*cost,m*value); } cout<<dp[v]<<endl; } return 0;}

可行性问题

引用自崔添翼巨巨的背包九讲

当问题是“每种有若干件的物品能否填满给定容量的背包”,只须考虑填满背包的可行性,不需考虑每件物品的价值时,多重背包问题同样有O(nW) 复杂度的算法。设dp[i][j]表示“用了前i 种物品填满容量为j 的背包后,最多还剩下几个第i种物品可用”,如果dp[i][j] = -1 则说明这种状态不可行,若可行应满足0<=dp[i][j]<=m[i]递推求dp[i][j]的伪代码如下:dp[0][1...V] = -1;dp[0][0] = 0;for i from 1 to N for j from 0 to W if dp[i-1][j] >= 0 dp[i][j] = m[i]; else dp[i][j] = -1; for j from 0 to W-w[i] if dp[i][j] > 0 dp[i][j+w[i]] = max{dp[i][j+w[i]],dp[i][j]-1}最终dp[n][0...V ]便是多重背包可行性问题的答案。

组合背包

n个重量和价值分别为wi,vi的物品,从中挑选出总重量不超过W的物品,求所有方案中价值最大的。每个物品可以选择的件数不一,给出输入数组m,mi为第i件物品的件数,其中有的物品可以取一次,有的可以不限次数取,有的与可取数目限制。

有了前面的讲解,我们只需要封装好01背包,完全背包和多重背包的函数,再分类讨论即可

伪代码:

for i = 1 to N if 第i件物品属于01背包 ZeroOnePack(F,Ci,Wi) else if 第i件物品属于完全背包 CompletePack(F,Ci,Wi) else if 第i件物品属于多重背包 MultiplePack(F,Ci,Wi,Ni)

参考代码(233代表可以无限取):

#include<iostream>#include<cstring>using namespace std;int v,n;int value;int cost;int m;int dp[30005];void zeroPack(int cost,int value){ for(int j=v;j>=cost;j--){ if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value; }}void completePack(int cost,int value){ for(int j=cost;j<=v;j++){ if(dp[j] < dp[j-cost]+value) dp[j] = dp[j-cost]+value; }}void multiPack(int cost,int value){ if(cost*m >= v){ completePack(cost,value); return; } int k=1; while(k < m){ zeroPack(k*cost,k*value); m = m-k; k *= 2; } zeroPack(m*cost,m*value);}int main(){int t; cin>>t; while(t--){ cin>>v>>n; for(int i=0;i<n;i++){ cin>>value>>cost>>m; if(m == 233){ completePack(cost,value); } else if(m == 1){ zeroPack(cost,value); } else{ multiPack(cost,value); } } cout<<dp[v]<<endl; } return 0;}

To Be Continued...

参考文献

《算法导论》

《挑战程序设计竞赛(第二版)》

《背包九讲》

https://blog.csdn.net/caroline424/article/details/52016872

, 1, 0, 9);

Copyright © 2019 金沙澳门官网 All Rights Reserved
刘凤琴
地址:四川省成都市锦江区四川成都
全国统一热线:18895685624