背包 问题

1、背包问题

1.1、01背包

题目：

有n件物品和一个容量为m的背包，第i件物品的体积是v[ i ]，价值是w[ i ]，每件物品只有一件，求在不超过背包容量的前提下，可以放的物品的最大价值是多少

基本思路：

每个物品只有一件，考虑去或者不取

状态设计：

//二维
状态表示：f[i][j]集合：从前i个物品中选，总体积不超过j的物品的价值属性：max
状态计算：选第i个物品：f[i][j]=min(f[i-1][j-v[i]]+w[i],f[i][j]);不选第i个物品：f[i][j]=min(f[i-1][j],f[i][j]);//时间复杂度基本无法优化，空间复杂度可以优化
//一维：由于每一次状态计算时仅需考虑计算上一个物品后的状态，但需要从m~0枚举体积
状态计算：f[j]=max(f[j],f[j-v[i]]+w[i]);

代码：

//不优化：二维
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N=1100;
int f[N][N];
int w[N],v[N];
int n,m;
int res;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++){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]);}}for(int i=1;i<=m;i++)   res=max(f[n][i],res);cout<<res;return 0;
}
//优化·一维
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1111;
int f[N];
int n,m;
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];return 0;
}

1.2、完全背包

题目：

有n件物品和一个容量为m的背包，第i件物品的体积是v[ i ]，价值是w[ i ]，每件物品有无限多件，求在不超过背包容量的前提下，可以放的物品的最大价值是多少

基本思路：

由于每种物品有无限多件，所以对于每种物品有无限多种选择（选0个，选1个······选n个）

状态设计：

状态表示：f[i][j]集合：从前i个物品中选，总体积不超过j的物品的价值属性：max
状态计算：//朴素O(n^3)：枚举每件物品取多少件(k:0~j/v[i])f[i][j]=max(f[i][j],f[i-k][j-k*v[i]]+k*w[i])//优化：朴素版本时：f[i][j] =max{f[i-1][j], f[i-1][j-v[i]]+w[i], f[i-2][j-2*v[i]]+2*w[i]. ······ }f[i][j-v[i]] =max{           f[i-1][j-v[i]],      f[i-2][j-2*v[i]]+w[i]. ······ }由以上两个式子可知：不选第i个：f[i][j]=f[i-1][j]选第i个（不确定个数）：f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//优化为一维f[j]=max(f[j],f[j-v[i]]+w[i])

代码：

//朴素做法  会超时
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
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=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k*v[i]<=j;k++){f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i],f[i][j]);}}}cout<<f[n][m];return 0;
}优化版本（二维）
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
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=1;i<=n;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][j-v[i]]+w[i]);}}}cout<<f[n][m];return 0;
}//再优化版本（一维）
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
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++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

1.3、多重背包

题目:

有n种物品和一个容量为m的背包，第 i 种物品有s[ i ]件，每件体积是v[ i ]，价值是w[ i ]，求在不超过背包容量的前提下，可以放的物品的最大价值是多少

基本思路（二进制优化版本）：

任何一个数可以用二进制来表示，也就是2⁰、2¹、……、2ⁿ 其中一项或几项的和

对于每一种物品划分为k组，每组的数量为2的倍数

然后转换为01背包进行考虑
状态设计：

同01背包

代码

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;
const int N=25000;
int n,m;
int w[N],v[N];
int f[N];int main()
{cin>>n>>m;int cnt=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){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){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];
}

1.4、分组背包

题目：

有n件物品（可以被分成几组）和一个容量为m的背包，第i件物品的体积是v[ i ]，价值是w[ i ]，组号为p[ i ]，每组只能选一个物品，求在不超过背包容量的前提下，可以放的物品的最大价值是多少

基本思路：

对于每组物品考虑取（取哪一件）或者不取

状态设计：

状态表示：f[i][j]集合：从前i组中选，总体积不超过j的物品的价值属性：max
状态计算：第i组不选：f[i][j]=f[i-1][j]选第i组的第k个：f[i][j]=max(f[i-1][j-v[i][k]]+w[i][k])//优化为一维f[j]=max(f[j],f[j-v[i][k]]+w[i][k])

代码：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
int n,m;
int w[110][110],v[110][110];
int s[110];
//二维  int f[110][110];
int f[110];
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=1;j<=s[i];j++)  scanf("%d%d",&v[i][j],&w[i][j]);}/*二维for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];for(int k=0;k<=s[i];k++){if(j-v[i][k]>=0){f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);}}}}cout<<f[n][m];*/for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){f[j]=f[j];for(int k=0;k<=s[i];k++){if(j-v[i][k]>=0){f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}}cout<<f[m];return 0;
}

1.5、混合背包

题目：

将1.1、1.2、1.3三种背包混合起来，即有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。

基本思路：

同上，分情况考虑各物品

状态设计：

同上

例题+代码：

有N种物品和一个容量是 V的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N=1010;int n,m;
int v[N],w[N],s[N];
int f[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d%d%d",&v[i],&w[i],&s[i]);if(s[i]==-1)    s[i]=1;}for(int i=1;i<=n;i++){if(s[i]==0){for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}else{for(int k=1;k<=s[i];k*=2){for(int j=m;j>=k*v[i];j--){f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);}s[i]-=k;}if(s[i]){for(int j=m;j>=s[i]*v[i];j--){f[j]=max(f[j],f[j-s[i]*v[i]]+s[i]*w[i]);}}}}cout<<f[m];
}

1.6、二维费用的背包

题目：

对于每种物品有两个限制条件，即除了对体积有限制外，还有一个限制量

基本思路：

增加了一重限制，所以需要增加一维变量

状态设计：

状态表示：f[i][j][k]集合：从前i个中选，体积不超过j，重量不超过k的价值区间：max
状态计算：同上

代码：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N=1010;int n,M,W;
int v[N],m[N],w[N];
int f[110][110];int main()
{cin>>n>>M>>W;for(int i=1;i<=n;i++)   scanf("%d%d%d",&v[i],&m[i],&w[i]);for(int i=1;i<=n;i++){for(int j=M;j>=v[i];j--){for(int k=W;k>=m[i];k--){f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);}}}cout<<f[M][W];return 0;
}