理解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]=0dp[i][j]=⎧⎩⎨⎪⎪dp[i+1][j](j=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]=0dp[i+1][j]=⎧⎩⎨⎪⎪dp[i][j](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的物品，求所有方案中价值最大的。每个物品可以挑选任意多件。 input n = 3 (w,v) = {(3,4),(4,5),(2,3)} W = 7 output 10 (0号选1件 2号选2件) 令dp[i+1][j]从前i种物品中挑选总重量不超过j时的价值最大值，那么递推关系为: dp[0][j]=0dp[i+1][j]=max(dp[i][j−k∗w[i]]+k∗v[i])(k>=0) 按这个思路我们有朴素的如下代码： int dp[MAX][MAX]; int solve(){ for(int i=0;i=1部分的计算已经在dp[i+1][j−w[i]]的计算中完成了，由此我们有如下变形: dp[i+1][j] =max(dp[i][j−k∗w[i]]+k∗v[i])k>=0 =max(dp[i][j],max(dp[i][j−k∗w[i]]+k∗v[i]))k>=1 =max(dp[i][j],max(dp[i][(j−w[i])−k∗w[i]]+k∗v[i])+v[i])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 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 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>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<= 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 #include 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>value>>cost>>m; if(m == 233){ completePack(cost,value); } else if(m == 1){ zeroPack(cost,value); } else{ multiPack(cost,value); } } cout<

关键字：