背包九讲
- 例题为acwing 模板习题
- 主要用于加深自己的理解
01背包问题
-
特征：只有n中物品，每个物品只有选或者不选
-
状态表示
-
集合：f[i][j] 为在1~i个物品可选的情况下，背包容量为j的情况下所有情况的集合
-
属性：最大的价值
-
状态转移：
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); -
模板代码
-
未进行优化版本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int bag[N][N];
int weight[N];
int value[N];
int main(){
int n,v;
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++){
scanf("%d%d",&weight[i],&value[i]);
}
for(int i=1;i<=n;i++){
for(int k=1;k<=v;k++){
if(k>=weight[i]){
bag[i][k]=max(bag[i-1][k],bag[i-1][k-weight[i]]+value[i]);
}else{
bag[i][k]=bag[i-1][k];
}
}
}
cout<<bag[n][v];
}
-
空间优化版本
- 观察发现 第i行数据其实只与第ｉ-1行有关，而如果从一行的尾部倒序遍历容量，就可以保证更新的时候第i行而用到的数据是第i-1行的
int bag[N];
int value[N];
int weight[N];
int main(){
int n,v;
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++){
scanf("%d%d",&weight[i],&value[i]);
}
for(int i=1;i<=n;i++){
//只与第i-1行有关，倒序遍历容量
for(int j=v;j>=weight[i];j--){
// 右边是上一行的 对应 bag[i-1][j],bag[i-1][j-weight[i]]+value[i]
bag[j]=max(bag[j],bag[j-weight[i]]+value[i]);
}
}
printf("%d",bag[v]);
}
完全背包问题
-
特征：只有n种物品，每种物品都可以选无数个
-
状态表示
-
集合：f[i][j] 为在前1~i种物品可选的情况下，背包容量为j的情况下所有情况的集合
-
属性：最大的价值
-
状态转移：
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-v[i]*2]+w[i]*2,,f[i-1][j-v[i]*k]+w[i]*k) v[i]*k<=j<v[i]*(k+1); -
此处
f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2*v[i]],....f[i-1][j-v[i]*k]+w[i]*k)' -
所以转移方程可以写作
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]) -
模板代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N][N];
int n,vo;
int w[N],v[N];
int main(){
cin>>n>>vo;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=vo;j++){
if(j>=v[i])
dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
else
dp[i][j]=dp[i-1][j];
}
}
printf("%d",dp[n][vo]);
}
进行空间优化之后
int dp[N];
int n,v;
int weight[N],value[N];
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++) cin>>weight[i]>>value[i];
for(int i=1;i<=n;i++){
for(int j=weight[i];j<=v;j++)
// j<weight[i]时dist[i][j]=dist[i-1][j]即当前行和上一行相等，可以直接省略
//dp[j-weight[i]]=dist[j-weight[i]],dist[j-2*weight[i]]+value[i]) ....//递推下去可以得到
dp[j]=max(dp[j]/*不选 dp[i-1][j]*/,dp[j-weight[i]]+value[i]/*选k个*/);
}
printf("%d",dp[v]);
}
多重背包问题
-
特征：有n种物品，每种物品的个数是有限的si,
-
状态表示
-
集合：f[i][j] 为在前1~i种物品可选的情况下，背包容量为j的情况下所有情况的集合
-
属性：最大的价值
-
状态转移方程
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]),....f[i-1][j-v[i]*k]+k*w[i])(1<=k<=s&& k*v[i]<=j) -
之间按照状态转移方程得到的模板代码如下(此处不再单独写未空间优化的代码)
O(n*v*log(num))
#include<iostream>
#include<cstring>
#include<cstdio>
const int N=1010;
using namespace std;
int dp[N];
int weight[N];
int value[N];
int num[N];
int main(){
int n,v;
cin>>n>>v;
for(int i=1;i<=n;i++) cin>>weight[i]>>value[i]>>num[i];
for(int i=1;i<=n;i++){
//由于第i行只与第i-1行有关，容量从v到weight[i]进行倒序循环处理即可
for(int j=v;j>=weight[i];j--){
for(int k=1;k*weight[i]<=j&&k<=num[i];k++){
//dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]*k]+value[i]*k)
dp[j]=max(dp[j],dp[j-weight[i]*k]+value[i]*k);
}
}
}
cout<<dp[v]<<endl;
}
-
二进制优化
-
基本思路：由于此时每种物品的数量是确定有限的s个，而所有整数都可以用二进制来表示，我们可以把每种物品按数量的二进制拆分为log(s)个物品，最后把这个问题转化为一个01背包问题
-
eg: 一种物品有A 8个，每个的体积为3，价值为5，可以拆分为
-
(A) 3 5 （AA) 3*2 5* (AAAA) 3*4 5*4 (A) 3 5 由于此时剩下的不足以再按照二进制表示把剩下的合为一个物品
-
//进行二进制优化后
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010; //数组要开的足够大，因为一个数num[i]要分解成log(num[i])个数
int weight[N],value[N],dp[N];
int main(){
int n,v;
cin>>n>>v;
int a,b,num;
int cnt=0; //记录拆分后物品的总数
for(int i=1;i<=n;i++){
cin>>a>>b>>num;
//把num个物品拆分成一个个的不同物品
for(int j=1;j<=num;j<<=1){
cnt++;
weight[cnt]=a*j;
value[cnt]=b*j;
num-=j; //每次拆出来j个
}
if(num){
cnt++;
weight[cnt]=a*num;
value[cnt]=b*num;
}
}
for(int i=1;i<=cnt;i++){
for(int j=v;j>=weight[i];j--){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
printf("%d",dp[v]);
}
- 单调队列优化 没看明白，貌似是通过对递推公式的的扩展找出了一个滑动窗口数组
混合背包问题
-
特征可能有n种物品，其中一类只允许选一个或者不选，一类有无限个，另一类有有限个，
-
解法：对有限个的类型利用二进制优化的方式转化为01背包，并对其进行标记，与01背包按相同的方案处理，而无限个则利用完全背包的公式处理
-
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
const int N=20100;
using namespace std;
int weight[N],value[N],dp[N];
int num[N];
int main(){
int n,v;
cin>>n>>v;
int cnt=0;
int a,b,c;
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
if(c==-1||c==0){
weight[++cnt]=a;
value[cnt]=b;
num[cnt]=c;
}
else{
//将有限个物品差分为01背包的类型
for(int j=1;j<=c;j<<=1){
weight[++cnt]=a*j;
value[cnt]=b*j;
num[cnt]=-1; //拆分出来的按照零一背包的情况处理
c-=j;
}
if(c){
weight[++cnt]=c*a;
value[cnt]=c*b;
num[cnt]=-1;
}
}
}
for(int i=1;i<=cnt;i++){
if(num[i]==-1){
for(int j=v;j>=weight[i];j--){ //01背包 至于上一行有关
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
else{
for(int j=weight[i];j<=v;j++){ //完全背包与当前行和上一行都有关系
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
}
printf("%d",dp[v]);
}
二维费用背包问题
-
以01背包的情况为例
-
此时装入的代价为重量与体积
//无空间优化
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N][N/10][N/10];
int value[N];
int vol[N];
int weight[N];
int main(){
int n,v,m;
cin>>n>>v>>m;
for(int i=1;i<=n;i++){
cin>>vol[i]>>weight[i]>>value[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=v;j++){
for(int k=1;k<=m;k++){
dp[i][j][k]=dp[i-1][j][k];
if(j>=vol[i]&&k>=weight[i])
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-vol[i]][k-weight[i]]+value[i]);
}
}
}
cout<<dp[n][v][m]<<endl;
}
// //滚动数组空间优化之后
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1010;
int dp[2][N][N];
int vol[N];
int weight[N];
int value[N];
int cur=1,last=0;
int main(){
int n,v,m;
cin>>n>>v>>m;
for(int i=1;i<=n;i++){
cin>>vol[i]>>weight[i]>>value[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=v;j++){
for(int k=1;k<=m;k++){
dp[cur][j][k]=dp[last][j][k];
if(j>=vol[i]&&k>=weight[i]){
dp[cur][j][k]=max(dp[cur][j][k],dp[last][j-vol[i]][k-weight[i]]+value[i]);
}
// dp[cur][j][k]=max(dp[last][j][k],dp[last][j-vol[i]][k-weight[i]]+value[i]);
}
}
swap(cur,last);
}
cout<<dp[0][v][m]<<endl;
}
// 优化掉第一维之后
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1100;
int dp[N][N];
int vol[N];
int weight[N];
int value[N];
int main(){
int n,v,m;
cin>>n>>v>>m;
for(int i=1;i<=n;i++) cin>>vol[i]>>weight[i]>>value[i];
for(int i=1;i<=n;i++){
for(int j=v;j>=vol[i];j--){
for(int k=m;k>=weight[i];k--){
//只用到上一行，所以从尾部开始
dp[j][k]=max(dp[j][k],dp[j-vol[i]][k-weight[i]]+value[i]);
}
}
}
cout<<dp[v][m]<<endl;
}
分组背包问题
-
特征：有n组物品，每组物品中有K个，在只允许在每组物品中选一个求最大体积
-
解法：对每个容量循环组内的所有的物品，在选出该组中价值最大的一个选择。1
-
dp[i][j] 表示第1~i组在容量j的情况的方案集合 表示的最大价值 -
dp[i][j]=max(dp[i-1][j],dp[i-1][j-vol[k]]+value[k]) 1<=k<K
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=110;
int dp[N];
int vol[N];
int value[N];
int main(){
int n,v;
cin>>n>>v;
//循环组(物品)
for(int i=1;i<=n;i++){
int t;
cin>>t;
for(int i=1;i<=t;i++){
cin>>vol[i]>>value[i];
}
//容量为外层循环，每个对应的容量v只会选择一个组中的一个
//相同的v情况下可能的情况是 t+1中(不选,选一个,选第1个....选第k个)。
for(int j =v; j >= 0; --j){
//每个容量循环所有组内的物品，确定该组当前容量下能取得的最大价值
for(int k = 1; k <= t; ++k){ //循环决策
if(j < vol[k]) continue;
dp[j] = max(dp[j], dp[j - vol[k]] + value[k]);
}
}
}
cout<<dp[v]<<endl;
}
有依赖的背包问题
-
特征：n个物品中存在依赖 即 选A的前提是已经选了B和C
-
[HTML_REMOVED]
-
思路，利用依赖图，将对于每个节点，对其每个字树按照子节点作为分组标准，计算在每个容量下对应字树能获得的最大价值，思路类似分组。
-
先根据子节点按照分组循环
- 在对每个容量循环字树中的部分
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=110;
int n,v;
int dp[N][N]; //当容量为j选择节点x时最大可能获得的数量
int vol[N];
int value[N];
int h[N],e[2*N],f;
int ne[N],idx=0;
void add(int x,int y){
ne[idx]=h[x]; //记录下一个节点的id
e[idx]=y; //记录下一个节点的值
h[x]=idx++;
}
void dfs(int x)
{
//选上x节点，则以x为根节点的子树(体积为w[x]~c)的最小价值为v[x]。
for(int i = vol[x]; i <= v; ++i) dp[x][i] = value[x];
//根据子节点循环分组
for(int i = h[x]; i != -1; i = ne[i]){
int u = e[i];
//获取每个分组在对应的容量下的最大价值
dfs(u);
//j的范围为w[x] ~ c，不然x这个根选不进去
for(int j = v; j >= vol[x]; --j){
//k的范围为0 ~ j - w[x]，表示在j空间的基础上选了x剩余的空间
for(int k = 0; k <= j - vol[x]; ++k){
dp[x][j] = max(dp[x][j], dp[x][j-k] + dp[u][k]);
}
}
}
}
int main(){
int root;
cin>>n>>v;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
cin>>vol[i]>>value[i]>>f;
if(f==-1) root=i;
else add(f,i);
}
dfs(root);
printf("%d",dp[root][v]);
}
求背包问题的方案数
- 以01背包为例，求能达到最大价值的方案个数
- 在更新 dp数组时，顺带更新方案计数数组cnt[i]记录在容量为恰好j的情况下达到最大值的方案书
dp[j]=max(dp[j],dp[j-v[i]]+w[i]) max值为dp[j]，说明不选v[i]时能达到最大，s+=cnt[j](cnt[i][j]+=cnt[i-1][j])
若max为dp[j-v[i]]+w[i],说明选v[i]能达到最大值s+=cnt[j-v[i]](cnt[i][j]+=cnt[i-1][j-v[i]])
- 最后的cnt[j]为s
#include<iostream>
#include<cstring>
#include<cstdio>
const int N=1010;
int vol[N];
int value[N];
int dp[N];
int cnt[N]; //此处cnt[i]与dp[i]都是恰好用i的体积的方案数和最大值
const int Mod=1e9+7;
using namespace std;
int main(){
int n,v;
cin>>n>>v;
cnt[0]=1;
for(int i=1;i<=v;i++) dp[i]=-0x3f;
for(int i=1;i<=n;i++){
cin>>vol[i]>>value[i];
}
for(int i=1;i<=n;i++){
for(int j=v;j>=vol[i];j--){
int s=0,t=0;
t=max(dp[j],dp[j-vol[i]]+value[i]);
if(t==dp[j]) s=(s+cnt[j])%Mod;
if(t==dp[j-vol[i]]+value[i]) s=(s+cnt[j-vol[i]])%Mod;
cnt[j]=s;
dp[j]=t;
}
}
int maxn=0;
for(int i=0;i<=v;i++) maxn=max(maxn,dp[i]);
int res=0;
for(int i=0;i<=v;i++){
if(dp[i]==maxn){
res=(res+cnt[i])%Mod;
}
}
cout<<res<<endl;
}
求背包问题具体方案
-
要求：以01背包为例，要求输出达到最大价值的字典序最小的方案
-
由于要求字典序最小，在遍历物品是需要从后向前
-
因为按照
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])的思路，是在第n个物品出判定除了最大值，是先确定n然后反向确定其他的数 - 而要求字典序最小所以应该从1开始判断，推到n
#include<cstring>
#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
int v[N],w[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=n;i;i--){
//若正向求,从前一个到前n个,来确定最大，那么最早确定取不取的其实是最后一个
//因为只有到第n个才是第一次决定最终方案中到底取不取某一个
//正向 f[i][j]=max(f[i-1][j],f[i-1][j-v[i]+w[i]) //先确定第n个选不选再决定第n-1个选不选
for(int j=1;j<=m;j++){
f[i][j]=f[i+1][j];
if(j>=v[i]){
f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
}
}
//此时最大时f[1][m]
for(int i=1,j=m;i<=n;i++){
//判断最大方案是否选物品i的方法 f[i+1][j-v[i]]+w[i]是否不小于不选i的情况
if(j>=v[i]&&f[i+1][j-v[i]]+w[i]>=f[i+1][j]) {
printf("%d ",i);
j-=v[i];
}
}
}
完全背包的模板是不是写错了？