第一次遇见动态规划（C++）

目录一、什么是动态规划二、线性DP1、数字三角形2.最长上升子序列LIS2.1、最长上升子序列LIS不同方向遍历的含义不同3.最长公共子序列LCS三、背包1.0/1背包2.完全背包3.多重背包4.分组背包5.混合背包问题6.背包问题求具体方案7.背包问题求方案数8.二维费用的背包问题9.有依赖的背包问题后续请期待……一、什么是动态规划动态规划是对问题的各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解的算法思想。“状态”、“阶段”、“决策”是构成动态规划算法的三要素。问题能用动态规划求解需要满足三个基本条件1、子问题重叠性动态规划算法是把原问题视作若干个重叠子问题的逐层递进每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后动态规划才会执行下一阶段的计算。2、无后效性动态规划算法要求已经求解的子问题不受后续阶段的影响。3、最优子结构性质动态规划是用来求解最优化问题。所以下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。类似于贪心策略在求解过程中我们如果能将问题形式化为状态空间进一步抽象出其“状态转移方程DP”,问题就得到了极大的解决。以下以例题代码注释的形式向读者展现动态规划的思想在实战中的应用请读者自行思考其韵味。二、线性DP1、数字三角形​#include iostream using namespace std; const int N105; int a[N][N]; int dp[N][N];//dp[i][j]表示走到ij时的总和 int main() { int n;cinn; for(int i1;in;i) for(int j1;ji;j) cina[i][j]; for(int i1;in;i) for(int j1;ji;j) dp[i][j]a[i][j]max(dp[i-1][j-1],dp[i-1][j]); //点ij是从上一步i-1j-1或i-1j选取最优的策略即值最大走到的 if(n1) coutdp[n][n/21]; else coutmax(dp[n][n/2],dp[n][n/21]);//最后肯定是走到最后一行的中间 return 0; }2.最长上升子序列LIS#include iostream using namespace std; const int N1e35; int a[N]; int dp[N];//dp[i]表示以a[i]结尾的比a[i]小的最多有几个a[j](ji) int main() { int n,ans;cinn; for(int i1;in;i) cina[i]; for(int i1;in;i) { dp[i]1; for(int j1;ji;j) { if(a[i]a[j]) dp[i]max(dp[i],dp[j]1); //对于每个以a[i]结尾的dp[i]依次遍历dp[j](ji),寻找符合条件的 } ansmax(ans,dp[i]); } coutans; return 0; }2.1、最长上升子序列LIS不同方向遍历的含义不同#includeiostream using namespace std; const int N1e35; int w[N],f[N],g[N]; int main() { int n;scanf(%d,n); for(int i1;in;i) scanf(%d,w[i]); for(int i1;in;i) { f[i]1; for(int j1;ji;j) { if(w[i]w[j]) f[i]max(f[i],f[j]1); } } for(int in;i1;i--)//此处g[i]的含义是指从起始到a[i]的最大下降子序列的长度 { //而从后扫描的g[i]的含义是从a[i]到终点的下降子序列的长度所以变换扫描顺序后的g[i]的含义发生了变化 g[i]1; for(int jn;ji;j--) { if(w[i]w[j]) g[i]max(g[i],g[j]1); } } int res0; for(int i1;in;i) resmax(res,f[i]g[i]-1); printf(%d,res); return 0; }3.最长公共子序列LCS#include iostream using namespace std; const int N1e39; int a[N],b[N]; int dp[N][N];//dp[i][j]表示a[1~i]序列和b[1~j]序列中的最长公共子序列的长度 int main() { int n,m;cinnm; for(int i1;in;i) cina[i]; for(int j1;jm;j) cinb[j]; for(int i1;in;i) { for(int j1;jm;j) { if(a[i]b[j]) dp[i][j]dp[i-1][j-1]1; //当a[i]b[j]时可以将他们作为公共元素插入到LCS的后面使得长度变长1 else dp[i][j]max(dp[i][j-1],dp[i-1][j]);//这已经包含了dp[i-1][j-1] //当a[i]b[j]时说明此时LCS不会延长那就从dp[i-1][j]和dp[i][j-1]中取大的作为最长的元素 } } coutdp[n][m]; return 0; }通过这三个基本例题相信大家已经能够明白用动态规划求解问题的三个基本条件三、背包任何背包问题都有01背包的影子甚至均可以化为01背包的问题(特殊性)而任何背包都是多重背包的特殊情况01背包和完全背包分别是多重背包分组个数的极端情况即多重背包具有普遍性可以说只要理解了多重背包其它的背包问题也就跟着解决了我也会通过代码注释的形式帮助读者理解这句话1.0/1背包//朴素版代码 // #include iostream // using namespace std; // const int N1e39; // int dp[105][N]; // int n,m; // int main() // { // cinnm; // dp[0][0]0; // for(int i1;in;i) // { // int w,v;cinwv; // for(int j0;jm;j) // { // //不选 // dp[i][j]dp[i-1][j]; // //选 // if(jw) // dp[i][j]max(dp[i][j],dp[i-1][j-w]v); // } // } // coutdp[n][m]; // return 0; // } //优化代码 #include iostream using namespace std; const int N1e39; int dp[N]; int n,m; int main() { cinnm; for(int i1;in;i) { int w,v;cinwv; for(int jm;jw;j--) dp[j]max(dp[j],dp[j-w]v);////不选时dp[i][j]dp[i-1][j] } coutdp[m]; return 0; }2.完全背包当空间优化成一维之后只有完全背包问题的体积是从小到大循环的//朴素版代码 // #include iostream // using namespace std; // const int N1e310; // int dp[N][N]; // int main() // { // int n,m;cinnm; // for(int i1;in;i) // { // int w,v;cinwv; // for(int j0;jm;j) // { // //第i类物品不选 // dp[i][j]dp[i-1][j]; // //第i类物品选 // for(int k1;k*wj;k) // { // dp[i][j]max(dp[i][j],dp[i-1][j-k*w]k*v);//第i类物品可以选多次取最大的一次 // } // } // } // coutdp[n][m]\n; // return 0; // } //优化代码: //因为dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v,dp[i-1][j-2*w]2*v……dp[i-1][j-k*w]k*v……) // dp[i][j-w]vmax(dp[i-1][j-w]v,dp[i-1][j-2*w]2*v,……dp[i-1][j-k*w]k*v……) //所以: dp[i][j]max(dp[i-1][j],dp[i][j-w]v) //也说明了j需要从小到大循环这是与0/1背包最大的不同j需要当前第i层循环的j-w来更新 #includeiostream using namespace std; const int N1e39; int dp[N]; int main() { int n,m;cinnm; for(int i1;in;i) { int w,v;cinwv; for(int jw;jm;j) { dp[j]max(dp[j],dp[j-w]v);//不选时dp[i][j]dp[i-1][j] } } coutdp[m]; }3.多重背包根据数据规模选择合适的优化方法10^2/s : 化为01背包10^3/s : 二进制优化将一个一个遍历变为一群一群遍历10^4/s : 单调队列优化求滑动窗口内的最大值//朴素版代码 // #include iostream // using namespace std; // const int N103,M203; // int f[N][M]; // int n,m; // int main() // { // cinnm; // for(int i1;in;i) // { // int v,w,s;cinvws; // for(int j0;jm;j) // { // f[i][j]f[i-1][j]; // for(int k1;ks;k) // { // if(jk*v) // f[i][j]max(f[i][j],f[i-1][j-k*v]k*w); // } // } // } // coutf[n][m]\n; // return 0; // } //优化版本 //思路一:化为01背包 //时间复杂度O(n*m*s) #include iostream using namespace std; const int N103,M203; int f[M]; int n,m; int main() { cinnm; for(int i1;in;i) { int v,w,s;cinvws; ////多重背包化为01背包把每种物品的s件一一摊开视为s个相同属性的物品即化为01背包 while(s--)////对每个物品循环s[i]次其余同01背包 for(int jm;jv;j--) { f[j]max(f[j],f[j-v]w); } } coutf[m]\n; return 0; } //思路二二进制优化 //时间复杂度O(n*m*log s) #includeiostream using namespace std; const int N2005; int f[N]; int n,m; int vv[20],ww[20]; int main() { cinnm; for(int i1;in;i) { int s,v,w;cinvws; int cnt0; for(int k1;ks;k1) {//有二进制优化的方法将原来思考一的一个一个地枚举变为一群一群地枚举 vv[cnt]v*k; ww[cnt]w*k; s-k; } if(s) { vv[cnt]v*s;//将这一群的物品看成一个物品 ww[cnt]w*s; } for(int k1;kcnt;k) { for(int jm;jvv[k];j--) f[j]max(f[j],f[j-vv[k]]ww[k]); } } coutf[m]\n; return 0; } //思路三滑动窗口单调队列 //时间复杂度O(n*m) #include iostream #includecstring using namespace std; const int N103,M203; int f[M],g[M],q[M]; int n,m; int main() { cinnm; for(int i1;in;i) { int v,w,s;cinvws; memcpy(g,f,sizeof f);//存一下上一层的元素 for(int j0;jv;j) { int hh1,tt0; for(int kj;km;kv) { if(hhtt(k-q[hh])/vs) hh;//如果窗口大于s个单位,则窗口前移 while(hhttg[q[tt]]-(q[tt]-j)/v*wg[k]-(k-j)/v*w) tt--;//运用单调队列优化求滑动窗口中的最值 q[tt]k;//入队队列存贮的是体积大小hh、tt只是q数组下标用于模拟队列和控制滑动窗口 if(hhtt) f[k]max(f[k],g[q[hh]](k-q[hh])/v*w);//窗口内的最大值进行状态转移 } } } coutf[m]\n; return 0; }4.分组背包分组背包组内的每一种选择均互斥这是与多重背包的本质区别#includeiostream using namespace std; const int N110; int f[N],v[N],w[N]; int n,m,s; int main() { cinnm; for(int i1;in;i) { cins; for(int j1;js;j) cinv[j]w[j]; for(int jm;j0;j--) for(int k1;ks;k) if(jv[k]) f[j]max(f[j],f[j-v[k]]w[k]);//对于同i组的物品分别考虑每一物品的选与不选这里与01背包很像 } coutf[m]\n; }5.混合背包问题这题能非常清晰地看出01背包、完全背包、多重背包的关联。#includeiostream using namespace std; const int M1005; int f[M]; int vv[M],ww[M]; int n,m; int main() { cinnm; for(int i1;in;i) { int v,w,s;cinvws; if(s0) { for(int jv;jm;j)//完全背包 f[j]max(f[j],f[j-v]w); } else { if(s-1) s1;//01背包是多重背包s1时的特殊情况 int cnt0; for(int k1;ks;k1)//二进制优化的多重背包 { vv[cnt]v*k; ww[cnt]w*k; s-k; } if(s) { vv[cnt]v*s; ww[cnt]w*s; } for(int k1;kcnt;k) { for(int jm;jvv[k];j--) f[j]max(f[j],f[j-vv[k]]ww[k]); } } } coutf[m]\n; return 0; }6.背包问题求具体方案#includeiostream using namespace std; const int N1005; int f[N][N]; int n,m; int v[N],w[N]; int main() { cinnm; for(int i1;in;i) cinv[i]w[i]; for(int in;i1;i--)//f[i][j]表示从i到n的选择情况 { for(int j0;jm;j) { f[i][j]f[i1][j]; if(jv[i]) f[i][j]max(f[i][j],f[i1][j-v[i]]w[i]); } } int jm; for(int i1;in;i)//因为最后一件物品存储的是最终状态所以从最后一件物品进行循环 {//我们不能正着寻找答案因为从0到1我们对于最优解中的第一件物品不知道选的是第几个物品从而无法确定他的初始体积多少但反着来我们一定会知道它的最后体积必为m if(jv[i]f[i][j]f[i1][j-v[i]]w[i]) { couti ; j-v[i]; } } return 0; }7.背包问题求方案数//思路一体积恰好为i #includeiostream #includecstring using namespace std; const int N1005,mod1e97; int f[N],g[N];//f[i]表示体积恰好为i的最优解g[i]表示最优解的方案数 int n,m; int main() { cinnm; memset(f,-0x3f,sizeof f); //从这个状态表示我们就该想到它与普通01背包的区别了我们需要在开始将所有的f都初始化为负无穷 //那么不能使体积恰好为j的情况就会被淘汰指不会被递推过去 g[0]1; f[0]0; for(int i1;in;i) { int v,w;cinvw; for(int jm;jv;j--) { int maxvmax(f[j],f[j-v]w); int cnt0; if(maxvf[j]) cntg[j]; if(maxvf[j-v]w) cntg[j-v]; g[j]cnt%mod; f[j]maxv; } } int res0; for(int i0;im;i) resmax(res,f[i]); int ans0; for(int i0;im;i) { if(resf[i]) ans(ansg[i])%mod; } coutans\n; return 0; } //思路二体积不超过i #includeiostream using namespace std; const int N1005; const int mod1e97; int f[N],g[N];////f[i]表示体积不超过i的最优解g[i]表示最优解的方案数 int n,m; int main() { cinnm; for(int i0;im;i) g[i]1;//不论是哪个体积下总有一个对应的最大价值方案数为1 for(int i1;in;i) { int v,w;cinvw; for(int jm;jv;j--) { if(f[j-v]wf[j]) { f[j]f[j-v]w; g[j]g[j-v];//一条路 } else if(f[j-v]wf[j]) g[j](g[j]g[j-v])%mod;//两条路 } } coutg[m]\n;//体积不超过m的最大价值方案数 return 0; }8.二维费用的背包问题理解二维费用的背包问题代码中的多重循环能更好地理解背包问题中循环递推的过程。//f[i,j]表示总体积和总重量分别不超过i,j的最优解这与单个物品的体积和重量毫不相关就不是同一个概念 //因此多重循环并没有割裂单个物品的体积和重量 #includeiostream using namespace std; const int N105; int f[N][N]; int n,V,M; int main() { cinnVM; for(int i1;in;i) { int v,m,w;cinvmw; for(int jV;jv;j--) { for(int kM;km;k--) { f[j][k]max(f[j][k],f[j-v][k-m]w); } } } coutf[V][M]\n; return 0; }9.有依赖的背包问题后续请期待……