C++动态规划及九种背包问题

一，动态规划

一），动态规划的定义

二），动态规划其他的相关概念（也是使用条件）

1，重叠子问题

2，最优子结构

3，无后效性

三），动态规划的优势

四），动态规划的使用流程：

二，背包问题

（一）0/1背包

经典题面：

解决方法

1.二维数组

（核心代码）

2.滚动数组

3.一维数组

详细代码

总结：

（二）完全背包问题

经典题面：

状态方程：

未优化版：

优化版本：

状态转移方程

最终代码：

（三）多重背包

经典题面：

解决方法：

转化！！

1，01背包法：

2，完全背包法：

3，二进制优化。

例题：

题目要求

代码

（四）混合背包

经典题面：

例题：编辑

（五）二维费用背包

经典题面：

分析：

例题：

代码

（六）分组背包

经典题面：

分析：

代码

一，动态规划

一），动态规划的定义

动态规划（Dynamic Programming，简称DP）是运筹优化的一个重要方法，它是求解具有重复子问题和最优子结构性质的问题的方法。通常通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

那么上面那两坨是什么呢？当然不止有这两坨东西

二），动态规划其他的相关概念（也是使用条件）

1，重叠子问题

重叠子问题是指在对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。‌ 这种性质在‌动态规划问题中得到了利用，通过只计算一次每个子问题并将其结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只需查看表格中的结果，从而提高了效率。‌

2，最优子结构

最优子结构是一个重要特点，它表示问题的最优解可以通过解决问题的子问题得到。具体来说，如果一个问题的最优解包含了其子问题的最优解，那么这个问题就具有最优子结构。

3，无后效性

是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。【说白了，就是当前选择不影响未来】

三），动态规划的优势

1.存放子问题答案，保证求解的正确性。

2.用递推方法，解决重复子问题的干扰。

3.按性质划分集合，减少子问题的数量。

4，时间复杂度低（更高效）：动态规划本质上就是递推的过程，对于重复的子问题非常的高效。而DP将子问题规模缩小（相同性质的子问题合并视为一个）将复杂度大大降低。

四），动态规划的使用流程：

1，划定子问题，描述状态

2，确定状态转移方程

3，确定初始值

4，确定遍历顺序

二，背包问题

说到动态规划，就不可避免地提到背包问题。

（一）0/1背包

经典题面：

有n件物品，v的背包空间。依次有物品价值为w1，质量（体积）（占用背包空间）p1。求出可以装下的价值最高的总价值。（也有题目改为时间、精力等等，原理一样）

【用通俗易懂（人话）说就是在有限的空间下尽可能装更值钱的物品（财宝）】所以就要合理利用背包空间。

解决方法

1.二维数组

建立dp数组。dp[i（第i件物品）][j（当前可以使用的背包空间）]也就是在只选择前i件物品时，背包空间不超过j的最大价值。

对于每一个点，都可以选择不装当前物品，保持之前所装的最大价值，也可以选择装下来。因为是最大价值，所以就可以使用一个max(不变，拾取当前物品）求出现在的最大值再进行更新。最后输出最后一个点（dp[n][v])就是最终答案

（核心代码）

【空间复杂度：nv】

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

这个过程其实就是一个填表格的过程，但是仔细想就会发现，每个点只与自己上一行左侧的点有关联，其余的点都没有被再次更新。节省空间，启动！！！

2.滚动数组

只与上一行有关联那就见一个dp[2][i]的数组就好了啊，那这样新的maxn就赋值在i%2的行里面了。

这样空间复杂度就被更新到2v

3.一维数组

还可以节省，只是用一个一维数组就可以解决了。如果从左往右更新显然也是不行的。每个点都与自己的左上点有关联，如果从左往右就会先将左边更新了就不行了。那就从左往右，此时左边的还保存着上个阶段（i-1）时的数据，直接使用不会出问题，而且当不需要更新，就直接使用原来的数据也不会有问题。这样空间复杂度（单个dp数组）就压缩到了O（n）

详细代码

	for(int i=1;i<=n;i++){//循环模拟n件物品cin>>w[i]>>v[i];//输入代价和价值for(int j=t;j>=w[i];j--){//从背包末尾到当前代价模拟dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//当前点的价值就是原先当前下标的价值和左边点的价值加上该物品的价值求最大值。}}

总结：

0/1背包时间复杂度为O（nv）（重复遍历n件物品，每次遍历背包空间）

空间复杂度最低O（v）

（二）完全背包问题

经典题面：

有N件物品和一个能背重量为W的背包，第i件物品的重量为w(weight)[i],价值为v(value[i])。每件物品有无数个，求怎样可以使背包物品价值总量最大。【人话：可以无限取同一个物品（当然是价值最高的），使自己背包价值最大】

状态方程：

$f[i,j]=max\left\{\begin{matrix} && \\ f[i-1][j] & &\\f[i-1][j-v_{i}] & &\\f[i-1][j-k*v_{i}]+k*w_{i} \end{matrix}\right.$

我们需要模拟该物品是否要选，如果要选那么选择几个。

边界是f[0][0]

目标是f[N][M]

未优化版：

for(int i=1;i<=n;i++) {//模拟物品 for(int j=0;j<=m;j++){//模拟背包空间 for(int k=0;k*v[i]<=j;k++){//模拟选择第i件物品选择的数量。 f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);//更新最大价值 }}
}

可以发现，因为为优化的朴素版本使用了三层循环嵌套，所以时间复杂度比较高。还是按照01背包优化的方法将f数组设为1维数组。这样不仅降低了空间复杂度，也降低了遍历时的时间复杂度。

优化版本：

状态转移方程

就是：f[j]=max{f[j],f[j-k*c]+k*w}（0<=k*c<=v）

最终代码：

for(int i=1;i<=n;i++){//模拟n件物品 for(int j=v[i];j<=m;j++){//模拟背包空间 f[j]=max(f[j],f[j-v[i]]+w[i]);//按照公式进行更新 }
} 
cout<<f[V];//统计表格的最后一个位置

（三）多重背包

经典题面：

给定n种物品，以及一个容量大小为m的背包，然后给出n个物品的体积、价值及个数，求背包最大价值是多少，也就是选择总体积不超过m的物品，然后使总价值最大。【就是在想着怎么获取最多钱数的同时还有拿取的数量限制】

解决方法：

多重背包可以进行亿点点的转化，因为01背包和完全背包的状态方程都是：F [j]=max(F [j], F [ j- v [i] ]+ w [i])。

转化！！

1，01背包法：

将多个重复的小物件进行整合，使其变成一个大物体，这样只需要考虑是否选择这个大的物体就变成了01背包。假设原小物体的体积为wi，价值为vi，数量为si。设将k件该物体进行组合，就得到了一个大小为k*w1，价值为k*vi的物体，这个时候就考虑是否选择这个新的大物体。

2，完全背包法：

当同一种物体的总体积连背包里都塞不下了，也就是si*wi>M这个时候就可以考虑随便拿，我们连 s 件物品都不可能拿完背包就已经塞不下了。这样只需要特判一下就可以使用完全背包来做了。

3，二进制优化。

如果要拿512件物品，按照转化成01背包的方法做，需要从拿1件枚举到拿512件的，而二进制优化就一些倍增思想，我们把拿多少件物品分为拿1 2 4 8 16 ... 256 512 ... 2^n 件，我们枚举的时候就枚举9次就到了512件了。而且无论是多少件，我们总能用一些数的组合来表示。这样就可以节省时间。

例题：

题目要求

这道题就是典型的多重背包问题，按照上面的思路进行DP即可。

代码

#include<bits/stdc++.h>//万能头文件 
#pragma GCC s//日常优化 
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fastusing namespace std;
const int N=1e4+5,M=4e4+5;
int n,m,a,b,c,cnt=0,v[N],w[N],f[M];
long long read() {//快读压时间 int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}int main(){n=read();m=read();for(int i=1;i<=n;i++){b=read();a=read();c=read();int t=1;while(c>=t){w[++cnt]=t*a;v[cnt]=t*b;c-=t;//总数量减去合成数量 t*=2;//t倍增 }if(c){//如果还有剩余的，就将剩余件数合成为新的个体 w[++cnt]=c*a;v[cnt]=c*b;}}for(int i=1;i<=cnt;i++)for(int j=m;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+v[i]);//转化完成后就按照01背包进行DP printf("%d",f[m]);//输出最后一个位置得到的最大值。 
}

（四）混合背包

顾名思义，就是将上面的三种背包问题掺和在一起，根据物品的数量si进行选择。

经典题面：

给定n种物品，以及一个容量大小为m的背包，然后给出n个物品的体积、价值，求背包最大价值是多少，也就是选择总体积不超过m的物品，然后使总价值最大。
区别：本题的物品分为三种，1、只有一个；2、有无限多个；3、有x个

这种类型的背包问题就结合一道例题来进行分析

例题：

分析：因为是01、完全和混合背包这三种杂在一起的，所以根据可以选择的物品数量进行选择。

代码：

#include<bits/stdc++.h>
#pragma GCC s
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fastusing namespace std;
long long read() {int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}int main(){int n,m;cin>>n>>m;int v[1010]={},w[1050]={},s[1050]={},f[1100]={};//体积，价值，数量 for(int i=1;i<=n;i++){cin>>w[i]>>v[i]>>s[i];//首先按照题目要求的：体积，价值，数量进行输入 if(s[i]==-1){//在题目中说道，当si是-1的时候，就按照01背包来进行DP，那么就将它的数量转换成1用多重背包进行DP。 s[i]=1;}}for(int i=1;i<=n;i++){//从1到n模拟物品的编号 if(s[i]==0){//按照题目要求特判一下是否需要用到完全背包 for(int j=w[i];j<=m;j++) {//按照完全背包的模板进行更新 f[j]=max(f[j],f[j-w[i]]+v[i]);}}else {//不是完全背包就是多重背包 for(int l=1;l<=s[i];l++)for(int j=m;j>=l*w[i];j--) {f[j]=max(f[j],f[j-w[i]]+v[i]);}}}printf("%d",f[m]);//最后输出将背包价值最大化的最大值 return 0;
}

（五）二维费用背包

这种背包就是一个物品受两个因素制约：例如：重量、体积；长度、宽度。等等

经典题面：

给定n nn个物品，以及一个容量大小为m mm、能承受质量为W WW的背包，然后给出n nn个物品的体积、价值及质量，求背包最大价值是多少，也就是选择总体积不超过m mm的物品，然后使总价值最大。

分析：

费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。
　　状态转移方程就是：f [i][v][u] = max { f [i-1] [v] [u] , f [i-1] [v-a[i]] [u-b[i]] + c[i] }。

还是按照之前优化的方式将第一维优化掉。

例题：

代码

#include<bits/stdc++.h>
const int N=1e4+5;
using namespace std;
int v[N]={0},w[N]={},m[N]={},f[N][N]={};//因为数组比较大，所以要放在外面 
long long read() {//快读 int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}int main(){int n,V,h;n=read();V=read();h=read();//背包容积，背包最大承重 for(int i=1;i<=n;i++){cin>>v[i]>>m[i]>>w[i]; //体积，重量，价值 }for(int i=1;i<=n;i++){//模拟物品 for(int j=V;j>=v[i];j--){//模拟体积 for(int k=h;k>=m[i];k--){//模拟质量 f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);//在原来的一维数组的基础上增加到二维。状态转移放长也要适当修改 }}}cout<<f[V][h];//不光是体积的V了，还要质量的最大h，这样就是可以拿到的受两个条件制约的最大价值 
}

（六）分组背包

经典题面：

给N组物品，然后每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，容里为M的背包，用这个背包装物品，使得物品价值总和最大.

分析：

其实就类似于01背包，对于一个物品有两种决策选或不选，但是分组背包是在01背包的基础上对物品进行了分组，并且每一组最多只能选择一个物品，所以不妨用01背包的思想去思考分组背包.

状态转移方程：if(j>=w[i][k]) f[j]=max(f[j],f[j-w[i][k]]+w[i][k]);
例题：

代码

#include<bits/stdc++.h>
using namespace std;
int c[1005]={},v[1005][1005]={},w[1005][1005]={},f[10006]={}; 
long long read() {int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}int main(){int n,m;n=read(),m=read();for(int i=1;i<=n;i++){c[i]=read();for(int j=1;j<=c[i];j++){w[i][j]=read(),v[i][j]=read();}}f[0]=0;for(int i=1;i<=n;i++){//模拟n件物品 for(int j=m;j>=0;j--){//模拟背包空间 for(int k=1;k<=c[i];k++){//模拟每个分组的c【i】件物品 if(j>=w[i][k]){//如果剩余空间大于新物品的体积 f[j]=max(f[j],f[j-w[i][k]]+v[i][k]); //按照状态转移方程进行更新 }}}}cout<<f[m];
}

未完待续！！！！！！！！！！！！！！！！！！！