[动态规划](1)背包问题
01背包
引言:
[ 0 -1 背包 ] 是较为简单的动态规划问题，也是其余背包问题的基础
动态规划是不断决策求最优解的过程，[0 - 1背包]既是不断对第 i 个物品的做出决策，[0-1]正好代表选与不选的两种决定
模板题：2. 01背包问题 - AcWing题库
思维导图:
思路：
状态fi定义：前 i 个物品，背包容量 j 下的最优解(最大价值)
- 当前状态依赖于之前的状态，可以理解蔚初始状态 f0=0 开始决策，有N件物品，则需要N次决策，每一次对第i件物品的决策，状态 fi 不断由之前的状态更新而来。
- 当前背包容量不够( j < v [i] ) , 没得选，因次前 i 个物品最优解既为 前 i - 1 个物品最优解：fi = f i-1
当前背包容量够，可以选，因此需要决策 选 与 不选 第 i 件物品：
- 选：fi = fi-1] + w[i]
- 不选：fi = fi - 1
代码:
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];//体积以及价值
int f[N][N];//j 体积下 前 i 个物品的最大价值
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
//f[0][0-m]=0 由于全局变量不需要初始化
//代表 在 0个体积下 所有的状态全为0
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];//通用最优解
if (j >= v[i])//在背包体积能装下第 i 件物品时,则决策是否选择第i件物品
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}优化：
我们可以发现，其状态只与他的上一维有关系，那么我们就可以采用 [ 滚动数组 ] 的方式来对其进行优化
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];//体积以及价值
int f[2 * N];//j 体积下 前 i 个物品的最大价值
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
//f[0][0-m]=0 由于全局变量不需要初始化
//代表 在 0个体积下 所有的状态全为0
for (int i = 1; i <= n; i++)
for (int j = m; j >= m; j++)
f[j] = max([j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}完全背包
完全背包在 01背包 的基础上 增加了 每件物品可以无限次使用的限制，我们则需要在01背包的基础上枚举 使用 k 件第 i 件物品的情况
模板题3. 完全背包问题 - AcWing题库
思维导图：
代码(三维)
//状态表示:f[i][j]:从前i个物品,背包容量为j的情况下,选取所有选法的最大值
//朴素版:枚举1-n个物品在0-m的容量挑选0-k个第i个物品
#include<iostream>
#include<cstring>
using namespace std;
#define N 1010
int n,m;//物品个数,背包容量限制
int f[N][N];//状态转移数组
int v[N],w[N];//物品体积,物品价值
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];//处理输入物品体积和价值
for(int i=1;i<=n;i++)//枚举1-n个物品
for(int j=0;j<=m;j++)//枚举0-m的背包容量
for(int k=0;k*v[i]<=j;k++)//枚举0-k个物品,k 限制为 当前 k 个 i 物品体积 小于等于 j
f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
//状态方程取到:max(包含第k个物品的最大值)
cout<<f[n][m]<<endl;
return 0;
}
优化(时间二维)
我们列举以下更新次序的内部关系:
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
//在 j 的容量下选取 i 个 物品 的最大价值
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-2*v]+2*w , .....)
//在 j - vi 的容量下 选取第 i 个物品 的最大价值
由上两式，可得出如下递推关系:
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
//逐渐添加第 i 个物品 选取最大值我们可以通过上述方程之间的关系发现:
- 在 容量 为 j 的条件下找 最大价值的方案，更新到 容量 j 的时候，j - v 体积时最大的方案已经存在了
- 所以只需要对比 j 体积的第一个方案和 j - v 体积的最大方案 + w 哪个大就可以了
总结来说：就是在 容量 大于 v[ i ] 的情况下 去试着 加入一个 [ 第 i 个物品 ] 看是否会比原有的大
//三维优化成二维:我们没必要枚举每一个k取到最大值,而是可以通过当前状态不断添加k个i物品来更新最大值
#include<iostream>
using namespace std;
#define N 1010
int n,m;
int f[N][N];
int v[N],w[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){//枚举0-m的背包容量
f[i][j]=f[i-1][j];//选0个第i个物品(不选第i个物品
if(j>=v[i])//每当j能装得下第i个物品的时候,尝试添加一个第i件物品
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}优化(空间一维)
同样，上述代码也可用 01 背包 的思路优化，能用 滚动数组 来进行优化，需要注意的是 由于是 二维的状态是在 [ 前 i 个物品 ] 中进行枚举，其状态也是由当前 第 i 个 物品 中的集合 转移过来的，是由所以不用逆序
//可以利用滚动数组来优化空间
#include<iostream>
using namespace std;
#define N 1010
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)//与01背包不同的是更新状态用的是当前的状态,所以需要从小到大枚举
f[j]=max(f[j],f[j-v[i]]+w[i]);//删去一维对方程作等价变形
cout<<f[m]<<endl;
return 0;
}多重背包
多重背包问题增加了物品数量的限制，每种物品只能用 s 件，其思路跟完全背包很像
思维导图：
https://nullcode.fun/admin/write-post.php?cid=150###
代码
//多重背包朴素版本和完全背包近乎一致
//枚举每一种物品的不同数量即可
#include<iostream>
using namespace std;
#define N 1010
int n,m;
int f[N][N];
int v[N],w[N],s[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k*v[i]<=j&&k<=s[i];k++)
f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
cout<<f[n][m]<<endl;
return 0;
}5. 多重背包问题 II - AcWing题库
由于每组物品的数量都不同，所以是不能采用完全背包的优化方式，则我们可以使用二进制对其进行优化，将每组物品的数量拆分出来，用01背包的思路既能解决
假设有一组商品，一共有11个，我们知道，十进制数字11可以这样表示
11 = 1011(B) = 0111(B) + (11 - 0111(B)) = 0111(B) + 0100(B)
朴素做法中，我们要求出含这组商品的最优解，我们要枚举11次( 枚举)，现在如果我们把这组商品分别打包成含商品个数为1个，2个，4个，4个(分别对应0001，0010，0100，0100)的四个"新的商品",将问题转化为01背包问题，对于每个商品，我们都只枚举一次，那么我们只需要枚举四次，就可以找出这11中商品的最优解，这样就大大减少了枚举次数
这种优化对于大数的效果极为明显，例如有1024个商品，在正常情况下要枚举1025次，优化后转换为01背包只需要10次
//多重背包采用二进制方法优化,不用枚举1-s[i]的每一个数,而是将这些数字拆分为logs[i]个数
//例如:200=1+2+4+8+16+32+64 + 73(除73外其余全是2的整次幂,这些数字能组成1-200任何数)
#include<iostream>
using namespace std;
#define N 2010000
int n,m;
int f[N];
int v[N],w[N];
int main(){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
int a,b,s;
cin>>a>>b>>s;
int k=1;//从一件物品开始分割
while(k<=s){//分割物品
cnt++;//新的物品数量
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s>0){
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
//将所有物品分割完毕后 采用01背包即可
n=cnt;
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
}分组背包问题
分组背包问题将 物品 从 个体 变为了 一组 ，且每组只能选一个物品 例如 水果这一组 选了苹果就不能选 西瓜
思维导图:
代码
#include<iostream>
#include<algorithm>
using namespace std;
#define N 10010
int n,m;
int f[N][N],v[N][N],w[N][N],s[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=1;j<=s[i];j++)
cin>>v[i][j]>>w[i][j];
}
for(int i=1;i<=n;i++)//枚举n种
for(int j=0;j<=m;j++){//枚举背包容量
f[i][j]=f[i-1][j];
for(int k=1;k<=s[i];k++){//枚举组内每一种物品
if(j>=v[i][k])
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);//每组每个物品只能选一种,即上一组物品的状态加价值(背包减去容量)
}
}
cout<<f[n][m]<<endl;
return 0;
}
*/
//优化空间版本,可用滚动数组优化
#include<iostream>
using namespace std;
#define N 1100
int n,m;
int f[N],v[N][N],w[N][N],s[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=1;j<=s[i];j++)
cin>>v[i][j]>>w[i][j];
}
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=1;k<=s[i];k++)
if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
cout<<f[m]<<endl;
return 0;
}