背包九讲

文章目录

背包九讲
- 01背包问题
- 完全背包问题
- 多重背包问题
- - 多重背包问题 I(二进制优化)
  - 多重背包问题 II(单调队列优化)
- 混合背包问题
- 二维费用的背包问题
- 分组背包问题
- 有依赖的背包问题
- 背包问题求方案数
- 背包问题求具体方案

脉络图
$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pEGLzdJj-1642346398405)(H:\codes\算法\背包九讲.assets\背包-16420904352541.png)]$

01背包问题

题目：

N件物品、容量背包是 V。第 i 件物品的体积是 v_i，价值是 w_i。每件物品只能使用一次。

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

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<v_i,w_i≤1000

代码：

#include <bits/stdc++.h>using namespace std;const int N=1010;
int n,m;
int f[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=m;j>=v[i];--j)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m]<<endl;return 0;        
}

完全背包问题

题目：

N件物品、容量背包是 V。第 i 件物品的体积是 v_i，价值是 w_i。每件物品可以使用多次。

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

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<v_i,w_i≤1000

代码：

#include <bits/stdc++.h>using namespace std;const int N=1010;
int n,m;
int v[N],w[N];
int f[N];int main()
{scanf("%d%d",&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)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[m]<<endl;return 0;
}

多重背包问题

题目：

N件物品、容量背包是 V。第 i 件物品有s_i个，体积是 v_i，价值是 w_i。每件物品使用次数不超过s_i。

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

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 件物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100
0<v_i,w_i,s_i≤100

代码：

#include <bits/stdc++.h>using namespace std;const int N=110;
int n,m;
int v[N],w[N],s[N];
int f[N][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<=s[i]&&k*v[i]<=j;++k)f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);cout<<f[n][m]<<endl;return 0;
}

多重背包问题 I(二进制优化)

题目：

N件物品、容量背包是 V。第 i 件物品有s_i个，体积是 v_i，价值是 w_i。每件物品使用次数不超过s_i。

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

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 件物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000
0<V≤2000
0<v_i,w_i,s_i≤2000

代码：

#include <bits/stdc++.h>using namespace std;const int N=12010,M=2010;
int n,m;
int v[N],w[N];
int f[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(s>=k){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;}}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;
}

多重背包问题 II(单调队列优化)

题目：

N件物品、容量背包是 V。第 i 件物品有s_i个，体积是 v_i，价值是 w_i。每件物品使用次数不超过s_i。

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 件物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000
0<V≤20000
0<v_i,w_i,s_i≤20000

代码：

#include <bits/stdc++.h>using namespace std;const int N=20010;
int n,m;
int f[N],g[N],q[N];int main(){cin>>n>>m;for(int i=0;i<n;++i){int v,w,s;cin>>v>>w>>s;memcpy(g,f,sizeof f);for(int j=0;j<v;++j){int hh=0,tt=-1;for(int k=j;k<=m;k+=v){if(hh<=tt&&q[hh]<k-s*v)hh++;while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w)tt--;q[++tt]=k;f[k]=g[q[hh]]+(k-q[hh])/v*w;}}}cout<<f[m]<<endl;return 0;
}

混合背包问题

N件物品、容量背包是 V。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 s_i次（多重背包）；

每种体积是 v_i，价值是 w_i。

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

s_i=−1 表示第 i 种物品只能用1次；
s_i=0 表示第 i 种物品可以用无限次；
s_i>0 表示第 i 种物品可以使用 s_i 次；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<v_i,w_i≤1000
−1≤s_i≤1000

代码：

#include <bits/stdc++.h>using namespace std;const int N=1010;
int n,m;
int f[N];int main(){cin>>n>>m;for(int i=0;i<n;++i){int v,w,s;cin>>v>>w>>s;if(!s){for(int j=v;j<=m;++j)f[j]=max(f[j],f[j-v]+w);}else {if(s==-1) s=1;for(int k=1;k<=s;k*=2){for(int j=m;j>=k*v;--j){f[j]=max(f[j],f[j-k*v]+w*k);}s-=k;}if(s){for(int j=m;j>=s*v;--j){f[j]=max(f[j],f[j-s*v]+s*w);}}}}cout<<f[m]<<endl;return 0;
}

二维费用的背包问题

题目：

N件物品、容量背包是 V、背包能承受的最大重量是 M。第 i 件物品的体积是 v_i，价值是 w_i，重量是 m_i。每件物品只能使用一次。

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

输入格式

第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 NN 行，每行三个整数 v_i,m_i,w_i，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000
0<V,M≤100
0<v_i,m_i≤100
0<w_i≤1000

代码：

#include <bits/stdc++.h>using namespace std;const int N=110;
int n,V,M;
int f[N][N];int main(){cin>>n>>V>>M;for(int i=0;i<n;++i){int v,m,w;cin>>v>>m>>w;for(int j=V;j>=v;--j)for(int k=M;k>=m;--k)f[j][k]=max(f[j][k],f[j-v][k-m]+w);}cout<<f[V][M]<<endl;return 0;
}

分组背包问题

题目：

N件物品、容量背包是 V。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 v_ij，价值是 w_ij，其中 i 是组号，j 是组内编号。

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

输入格式

第一行有两个整数 N，V 用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 S_i，表示第 i 个物品组的物品数量；
每组数据接下来有 S_i 行，每行有两个整数 v_ij,w_ij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100
0<S_i≤100
0<v_ij,w_ij≤100

代码：

#include <bits/stdc++.h>using namespace std;const int N=110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];int main(){cin>>n>>m;for(int i=1;i<=n;++i){cin>>s[i];for(int j=0;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=0;k<s[i];++k)if(v[i][k]<=j)f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);cout<<f[m]<<endl;return 0;
}

有依赖的背包问题

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

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：
$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HDifyHiQ-1642346398407)(H:\codes\算法\背包九讲.assets\1_bb51ecbcd2-QQ图片20181018170337.png)]$
如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 v_i，价值是 w_i，依赖的父节点编号是 p_i。物品的下标范围是 1…N。

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

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 ii 行有三个整数 v_i,w_i,p_i，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 p_i=−1，表示根节点。 数据保证所有物品构成一棵树。

输出格式

输出一个整数，表示最大价值。

数据范围

1≤N,V≤100
1≤v_i,w_i≤100

父节点编号范围：

内部结点：1≤p_i≤N;
根节点 p_i=−1;

代码：

#include <bits/stdc++.h>using namespace std;const int N=110;
int n,m;
int v[N],w[N];
int h[N],e[N],ne[N],idx;
int f[N][N];void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u){for(int i=h[u];i!=-1;i=ne[i]){int son=e[i];dfs(e[i]);for(int j=m-v[u];j>=0;--j){for(int k=0;k<=j;++k){f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);}}}for(int i=m;i>=v[u];--i)f[u][i]=f[u][i-v[u]]+w[u];for(int i=0;i<v[u];++i)f[u][i]=0;
}int main(){cin>>n>>m;memset(h,-1,sizeof h);int root;for(int i=1;i<=n;++i){int p;cin>>v[i]>>w[i]>>p;if(p==-1) root=i;else add(p,i);}dfs(root);cout<<f[root][m]<<endl;return 0;
}

背包问题求方案数

N件物品、容量背包是 V。第 i 件物品的体积是 v_i，价值是 w_i。每件物品只能使用一次。

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

输出最优选法的方案数。注意答案可能很大，请输出答案模 10⁹+7 的结果。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示方案数模 10⁹+7 的结果。

数据范围

0<N,V≤1000
0<v_i,w_i≤1000

代码：

#include <bits/stdc++.h>using namespace std;const int N=1010,mod=1e9+7;
int n,m;
int f[N],g[N];int main(){cin>>n>>m;memset(f,-0x3f,sizeof f);f[0]=0;g[0]=1;for(int i=0;i<n;++i){int v,w;cin>>v>>w;for(int j=m;j>=v;--j){int maxv=max(f[j],f[j-v]+w);int cnt=0;if(maxv==f[j]) cnt+=g[j];if(maxv==f[j-v]+w) cnt+=g[j-v];g[j]=cnt%mod;f[j]=maxv;}}int res=0;for(int i=0;i<=m;++i) res=max(res,f[i]);int cnt=0;for(int i=0;i<=m;++i)if(res==f[i])cnt=(cnt+g[i])%mod;cout<<cnt<<endl;return 0;
}

背包问题求具体方案

N件物品、容量背包是 V。第 i 件物品的体积是 v_i，价值是 w_i。每件物品只能使用一次。

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

输出字典序最小的方案

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。

数据范围

0<N,V≤1000
0<v_i,w_i≤1000

代码：

#include <bits/stdc++.h>using namespace std;const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];int main(){cin>>n>>m;for(int i=1;i<=n;++i) cin>>v[i]>>w[i];for(int i=n;i>0;--i)for(int j=0;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]);}int j=m;for(int i=1;i<=n;++i)if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){cout<<i<<" ";j-=v[i];}return 0;
}