C++动态规划（背包问题）

目录

一.动态规划是什么

二.动态规划的运用

（1）.用动态规划解决重复子问题

（2）.动态规划使用的条件与流程

Ⅰ.动态规划的使用条件：

Ⅱ.动态规划的使用流程

（3）.背包问题

三.背包问题：

（1）.0/1背包

Ⅰ.朴素方法：

Ⅱ.滚动数组优化 ：

Ⅲ.一维数组：

（2）.多重背包

（3）.完全背包

（4）.混合背包

（5）.分组背包

（6）.二维费用背包

一.动态规划是什么

计算机相对于人类来说的优势有三点，一点是他的运行速度，第二点是准确性，第三点则是处理问题的时候逻辑十分清晰。所以我们一般在编程时用的有两种方法，一是运用计算机的快速计算能力进行暴力枚举法、另一个则是将一个大问题分成小问题，求出所有小问题的答案再组合在一起得出正确答案的分解问题法。其中分解问题法需要能熟悉的掌握分解题目的方式以及能够熟练的运用递归，分治和贪心等算法。但他们各有他们的劣势。就比如贪心算法，在三角形中寻找最短的边的时候，他会在每一个节点是选择边较长的那一个。但是他不会考虑到较短的那条边连接的下一条边是否更长，所以贪心算法虽然时间复杂度较低，但他得出来的是较优解，而不是最优解。

举个例子：

货币面额有1,2,5,10,20,50,100，每种数量都无限多，现在给出金额n(1<=n<=1e6)，求出构造金额n的最少货币数量

贪心策略：分成若干次选择，每一次选择比n小且最接近n的货币。

但是如果当n=7是，货币金额分别为3、1、4、5时，如果先选择5的话就没法凑出7。

如果我们将构造某个金额所需要的最少货币数量作为一个问题，并且用数组储存答案。那么在求解某个原问题的时候，我们只需要考虑原问题由哪一个子问题推出能得到更优解即可。

如本题：我们用f[i]表示金额为i的最少需要的硬币的总数量。

明显可以发现：f[1]=1 / f[2]=2 / f[3]=2 / f[4]=2 / f[5]=1 / f[6]=3 ......

而f[7]有多种组成，比如：

f[7]=f[6]+f[1]=f[5]+f[2]=f[4]+f[3]=f[5]+f[1]+f[1]......，我们从中选择一个解使得f[7]最小即可。像这样我们把每个子问题的解储存下来，最终可以知道原问题的解一定可以由子问题推出。将求解变成一个递推，与普通递推不一样的地方在于原问题可能会由多个子问题推出，我们选最优的即可。

这就是动态规划(DP)的基本思想，以空间换时间，存放各子问题的解以便能推出原问题。这样可以充分保证求解的正确性。具体讲解放在下一部分。

二.动态规划的运用

（1）.用动态规划解决重复子问题

动态规划其实和分治算法的想法相同，保证可以通过子问题来推出原问题的最终答案，而且在处理重复子问题的时候非常的高效。我们在进行搜索剪枝的时候，对于无法避免的较多重复的子问题，我们通常采用记忆化的方式进行处理。但由于其使用了递归的方法，对于规模比较大的问题，他依旧会超时。但如果使用动态规划的话，因为其本质为递推，所以对于重复子问题可以进行高效的处理。另外我们还知道，子问题越多那么复杂度越高，如果我们将子问题的规模缩小（多个有相同性质的子问题合并视作一个)，那么复杂度将会大大减小。

像上一道题一样，我们将所有金额为7的组合视作一个集合。集合的值为最少货币数量显然，集合的允许加入条件越宽松，那么重复子问题就越多，要处理的节点也就越少。

（2）.动态规划使用的条件与流程

Ⅰ.动态规划的使用条件：

1.重复子问题：存在大量子问题进行了重复计算。

2.具备最优子结构：后面阶段的状态可以通过前面子问题状态推导出来。

3.无后效性：已经求解的子问题，不会再受到后续决策的影响。即从关系图上而言是一个DAG。

Ⅱ.动态规划的使用流程

1.划分子问题。即定义集合，描述状态。

2.确定状态转移方程。即子问题的解如何推出原问题

3.确定初始值

4.确定遍历顺序，保证求某问题时，其涉及到的子问题的解已经全部求出。即从小到大填出dp表

（3）.背包问题

背包问题‌是一个经典的动态规划问题，它描述了一个旅行者有一个最多能装m公斤的背包，现在有n件物品，每件物品有各自的重量和价值。他的要求是选择装入背包的物品，使得背包内物品的总价值最大，同时不超过背包的容量限制。这个问题通常被称为0/1背包问题，因为每个物品只有两种选择：装入背包或不装入背包。

背包问题与动态规划算法是密不可分的，该算法通过构建一个表格来记录每个子问题的解，最终找到最优解。具体来说，对于每个物品i和背包的当前承重j，算法会考虑两种情况：将物品i放入背包（如果它的重量不超过j）或不放入背包。通过比较这两种情况下的价值，算法可以确定在当前承重下应该如何选择物品以达到最大价值。

三.背包问题：

（1）.0/1背包

就如上面所说，0/1背包就是在动态规划的基础上进行选与不选。每加入一物品，dp[i]的值可能会产生变化。根据上一阶段的状态，从小到大进行更新当前阶段的状态，因此dp可以增加一个维度为：dp[i][j]表示第i个阶段，时间不超过j的最大价值。更新过程就是一个填表的过程。时间复杂度O(nT)。0/1背包时整个背包问题的基础，其他背包问题大多数都是基于0/1背包的基础上的。

例题：采药

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

请输出可以采到的草药的总最大值。

Ⅰ.朴素方法：

将所有信息输入到表格中，在循环中进行处理。空间复杂度（tn）

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,t,dp[1005][1005];
int main(){cin>>t>>n;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;for(int j=0;j<=t;j++){if(j<a) dp[i][j]=dp[i-1][j];else dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j]);}}cout<<dp[n][t];return 0;
}

Ⅱ.滚动数组优化 ：

因为我们在更新表格的时候仅需要上一行表格，所以我们只需要两个数组进行存储。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int f[2][10005],t,n,m;
int main(){cin>>t>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;for(int j=a;j<=t;j++){f[i%2][j]=f[(i-1)%2][j];f[i%2][j]=max(f[i%2][j],f[(i-1)%2][j-a]+b);}}cout<<f[m%2][t];
}

注：这是60分代码,本人目前还不知道哪错了，如有大佬知道错哪了，麻烦在评论区回复，万分感谢

Ⅲ.一维数组：

其实我们也可以用一维数组来表示，只需要从右侧开始这样的话在更新了后面的数据以后才会去修改前面的数据

代码实现：

#include<bits/stdc++.h>
using namespace std;
int t,m,dp[1005];
int main(){cin>>t>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;for(int j=t;j>=a;j--) dp[j]=max(dp[j],dp[j-a]+b);}cout<<dp[t];return 0;
}

（2）.多重背包

多重背包通常用于解决在限制了每个数字的使用次数的情况的题。我们可以将多重背包直接转化成多个0/1背包，再逐个解决。但是这样，时间复杂度会超时，所以我们通常在解决多重背包时我们通常使用二进制优化法。二进制优化法就是通过将每种物品的数量拆分成二进制的形式，将多个小数量物品组成一个大数量物品。他的时间复杂度为

  其中N指物品数量，V指背包的容量，ni则指第i种物品的最大数量。

例题：宝物筛选

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 W 的采集车，洞穴里总共有 n 种宝物，每种宝物的价值为 vi​，重量为 wi​，每种宝物有 mi​ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

我们可以将多重背包直接转化成多个0/1背包，再逐个解决。但是这样，时间复杂度会超时，所以我们通常在解决多重背包时我们通常使用二进制优化法。二进制优化法就是通过将每种物品的数量拆分成二进制的形式，将多个小数量物品组成一个大数量物品。他的时间复杂度w为

  其中N指物品数量，V指背包的容量，ni则指第i种物品的最大数量

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=4e4+5;
int n,m,v[N],w[N],dp[M],cnt;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;int t=1;while(c>=t){//转换成二进制形式w[++cnt]=t*b;v[cnt]=t*a;c-=t,t*=2;}if(c) w[++cnt]=c*b,v[cnt]=c*a;//转换成二进制形式（当c小于t时）}for(int i=1;i<=cnt;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//建立表格cout<<dp[m];return 0;
}

（3）.完全背包

完全背包就是每一个物品都可以进行无数次选择，求出在有限的条件下（通常为容量或重量）物品价值的最大值。0/1背包是逆序从大到小枚举容量j，完全背包则是正序从小到大枚举容量j，这样做就表示dp[j]从之前已经更新过的项目里直接进行转移，求出当前物品的任意选择的最大价值。

例题：疯狂的采药

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”请你帮助他。

代码：

#include<bits/stdc++.h>
using namespace std;
const int M=4e4+5;
int n,m,v,w,dp[M];
int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>v>>w;for(int j=v;j<=n;j++) dp[j]=max(dp[j],dp[j-v]+w);//正序枚举，直接从之前更新过的项目里转移}cout<<dp[n];return 0;
}

（4）.混合背包

顾名思义，就是将以上三种不同的背包问题混合在一起，通过分析数量来决定使用哪一种。

例题：樱花

爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 Ci​(0≤Ci​≤200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 Pi​(0≤Pi​≤100) 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 Ti​(0≤Ti​≤100)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,v[N],w[N],dp[N],c[N],cnt,t,f,t1,f1;
char ch;
int main(){cin>>t>>ch>>f>>t1>>ch>>f1;cin>>n;for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>c[i];m=(t1*60+f1)-(t*60+f);//计算现在与上学前的时间for(int i=1;i<=n;i++){if(c[i]==0) for(int j=v[i];j<=m;j++) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//完全背包问题else for(int l=1;l<=c[i];l++) for(int j=m;j>=l*v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//多重背包问题}cout<<dp[m];return 0;
}

（5）.分组背包

这种背包问题通常用来处理应对每组只能选一个物品的问题，只需要在0/1背包的基础上多套一层循环，枚举选这一组的哪一个即可。

例题：分组背包

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vi,j​，价值是 wi,j​，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,v[N][N],w[N][N],dp[N],c[N];//将v和w数组定义成二维数组，应为每一组都有多个v和w
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>c[i];for(int j=1;j<=c[i];j++) cin>>v[i][j]>>w[i][j]; }dp[0]=0;for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){for(int k=1;k<=c[i];k++){//枚举选取的数字if(j>=v[i][k]) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);}}}cout<<dp[m];return 0;
}

（6）.二维费用背包

这种背包通常用于在两种条件限制的情况下，选取最大值。

例题：二维费用背包

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

代码实现：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
int n,s,t,v[N],w[N],m[N],dp[N][N];
signed main(){cin>>n>>s>>t;for(int i=1;i<=n;i++) cin>>v[i]>>m[i]>>w[i];for(int i=1;i<=n;i++){for(int j=s;j>=v[i];j--){for(int k=t;k>=m[i];k--){//枚举背包重量dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+w[i]);}}}cout<<dp[s][t];return 0;
}

此文章为笔记型，会随着时间而更新，望原谅