【中等】保研/考研408机试-动态规划1（01背包、完全背包、多重背包）

背包问题基本上都是模板题，重点：弄熟多重背包模板

dp[j]=max(dp[j-v[i]]+w[i],dp[j])    //核心思路代码（一维数组版）

dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])//二维数字版

一、 0-1背包

一般输入两个变量：体积（亦或者是重量）v和价值w

初始化好像不是必须的，如果出bug自己又搞不懂是哪里再加上吧

[NOIP2005]采药  登录—专业IT笔试面试备考平台_牛客网

#include <iostream>
#include <vector>
using namespace std;
int dp[1000];
int p[101];
int t[101];
int main() {int v,n;cin>>v>>n;for(int i=0;i<101;i++){p[i]=0;t[i]=0;}for(int i=0;i<100;i++){dp[i]=0;}for(int i=0;i<n;i++){cin>>t[i]>>p[i];}for(int i=0;i<n;i++){for(int j=v;j>=t[i];j--){   //注意是大于等于，有等于！这里错过好几次dp[j]=max(dp[j],dp[j-t[i]]+p[i]);}}cout<<dp[v];
}

 P1507 NASA的食物计划NASA的食物计划 - 洛谷

来个二维数组版的例子。

#include <iostream>
#include <vector>
using namespace std;
int dp[500][500];
int h1[401];
int t1[401];
int k1[501];
int main() {int h,t,n;cin>>h>>t>>n;//初始化 for(int i=0;i<400;i++){h1[i]=0;t1[i]=0;}for(int i=0;i<500;i++){k1[i]=0;}for(int i=0;i<n;i++){cin>>h1[i]>>t1[i]>>k1[i];}for(int i=0;i<n;i++){for(int j=h;j>=h1[i];j--){for(int k=t;k>=t1[i] ;k--){dp[j][k]=max(dp[j][k],dp[j-h1[i]][k-t1[i]]+k1[i]);}}}cout<<dp[h][t];   
}

二、 完全背包

一般输入两个变量：体积（亦或者是重量）v和价值w

完全背包的意思就是每个物品可以取无限次，0-1背包是每个物品只能取走一次。

完全背包例题：3. 完全背包问题 - AcWing题库

#include <iostream>
#include <vector>
#include<bits/stdc++.h> 
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int main() {int n,v;cin>>n>>v;for(int i=0;i<n;i++){cin>>v1[i]>>w[i];}for(int i=0;i<n;i++){for(int j=v1[i];j<=v;j++){  //差别在这里dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);}}cout<<dp[v];
}

注意：可以看出，0-1背包和完全背包的问题的解决方案差别不大，主要就是在for(int j=v……部分的差别。

 三、多重背包问题

一般输入两个变量：体积（亦或者是重量）v、价值w和数量s

背包问题中最难的了，结合了0-1背包和多重背包的特点，简单来说就是某个物品可以取s次，有了次数限制。

常规思路就是拆分成份，重新构成0-1背包问题。

例题4. 多重背包问题 I - AcWing题库

#include <iostream>
#include <vector>
#include<bits/stdc++.h> 
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int s[1001];
int main() {int n,v;cin>>n>>v;for(int i=0;i<n;i++){cin>>v1[i]>>w[i]>>s[i];}for(int i=0;i<n;i++){while(s[i]!=0){ //监控数量for(int j=v;j>=v1[i];j--){  //0-1背包处理dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);}s[i]--;}}cout<<dp[v];
}

可以看到，for(int j=v……这部分的处理和0-1背包的处理逻辑一样。就是在外面增加一个while监控数量的变化即可。整体还是在for(int i=0;i<n;i++){框架下。

上述的微小改进只适用于处理小范围数据集，数据集一大（一两千）就会超时，此时就需要改进算法了，参考下题：

数据量大的情况：5. 多重背包问题 II - AcWing题库

二进制优化是基于这样的事实：

任意正整数可以表示为2的幂之和。

利用这一点，我们可以将每种物品的数量拆分成几个二进制的组件，从而将多重背包问题转换为0-1背包问题的多个实例。

二进制拆分挺麻烦的……要加里面，我写了一版有的用例没有过，还需要再背2024年5月6日

#include <bits/stdc++.h>
using namespace std;
int dp[2102];
int v1[2101];
int w[2101];
int s[2001];int main() {int n,v;cin>>n>>v;for(int i=0;i<n;i++){cin>>v1[i]>>w[i]>>s[i];}for(int i=0;i<n;i++){if(s[i]*v1[i]>=v){ //份数乘以重量 大于 容量，采取完全背包。 for(int j=v1[i];j<=v;j++){dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);}}else{// 二进制拆分，处理多重背包问题for(int k=1;s[i]>0;k=k*2){if(k>s[i]){// 当拆分块大于剩余数量时，调整k为剩余数量k=s[i];}int totalv=k*v1[i];int totalw=k*w[i];for(int j=v;j>=totalv;j--){//0-1背包处理 dp[j]=max(dp[j],dp[j-totalv]+totalw);}s[i]=s[i]-k;}}}cout<<dp[v];return 0;
}

四、分组背包问题 

分组背包问题：9. 分组背包问题 - AcWing题库

就是分组，每个组只能取一个背包。（这个模板没背过，下次记得背，2024年5月6日）

#include <bits/stdc++.h>
using namespace std;
int dp[102];
int v1[101];
int w[101];int main() {int n,v,z;cin>>n>>v;for(int i=0;i<n;i++){cin>>z;for(int j=0;j<z;j++){			cin>>v1[j]>>w[j];}for(int k=v;k>=0;k--){for(int j=0;j<z;j++){if(k>=v1[j]){dp[k]=max(dp[k],dp[k-v1[j]]+w[j]);	}}}}cout<<dp[v];return 0;
}