背包问题整理
背包问题 借鉴文章 视频学习1 视频学习2
1: 01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
- 特点：每种物品仅有一件，可以选择放或不放。
dp[i][j]表示前i件物品放入一个容量为j的背包(每一件都可能放可能不放，但只记录放入的价值)可以获得的最大价值。
-
状态转移方程：dp[i][j]=max{dp[i-1][j],dp[i-1][j-v[i]]+w[i]}。
-
结果：max(dp[N][0~V])，如果dp数组均初始化为0，则结果直接是dp[N][V].
-
时间复杂度 O(N * V) 空间复杂度 O(N * V)
\’\’\’
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MAXN = 1005;
int w[MAXN]; // 价值
int v[MAXN]; // 体积
int dp[MAXN][MAXN]; // dp[i][j], 体积为j下前i个物品的最大价值
int main(){
int n, m;
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++)
{
dp[i][j] = dp[i-1][j];
if((j-v[i])>=0)//当前已装容量大于v[i],只有这样才证明可以装入第i件
dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
}
int ans = 0;
for(int i = 0;i<=m;i++){
ans = max(dp[n][i],ans);
}
cout << ans;
return 0;
}
\’\’\’
-
状态压缩 :只用一个数组dp[0..v]，使得第i次循环结束后dp[0..v]中表示的状态为dp[i-1][0..v]。这要求在每次主循环中我们以从v到0的倒序推导dp[v..0]，这样才能保证推dp[j]时dp[j-v[i]]保存的是状态dp[i-1][j-v[i]]的值。其中的
dp[j] = max(dp[j],dp[j-v[i]] + w[i])
相当于 dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i])
\’\’\’
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MAXN = 1005;
int w[MAXN]; // 价值
int v[MAXN]; // 体积
int dp[MAXN]; // dp[i][j], 体积为j下前i个物品的最大价值
int main()
{
int n, m;
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--){
dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
}
}
int ans = 0;
for(int i = 0;i<=m;i++){
ans = max(dp[i],ans);
}
cout << ans;
return 0;
}
\’\’\’
- “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-c[i]的背包中”，此时能获得的最大价值就是dp[i-1][j-v[i]]再加上通过放入第i件物品获得的价值w[i]。
2：完全背包问题
题目
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路
仍然按照解01背包时的思路，令dp[i][j]表示前i种物品恰放入一个容量为j的背包的最大价值 ：
dp[i][j]=max{dp[i-1][v-k * v[i]]+k * w[i]}
\’\’\’
for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
for(int k = 0;k*v[i]<=j;k++){
dp[j] = max(dp[j],dp[j-k*v[i]] + k*w[i]);
}
}
}
\’\’\’
- 时间复杂度
这跟01背包问题一样有O(N * V)个状态需要求解，但求解每个状态的时间则不是常数了，求解状态dp[i][j]的时间是O(j/v[i])，总的时间复杂度是超过O(N * V)的。
优化
-
简单优化
若两件物品i、j满足v[i]<=v[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。原因：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
-
更高效的O(N * V)的算法。
01背包中要按照v=V..0的逆序来循环。是因为要保证第i次循环中的状态dp[i][j]是由状态dp[i-1][j-v[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果dp[i-1][j-v[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在使用“加选一件第i种物品”策略，使用一个可能已选入第i种物品的子结果dp[i][j-v[i]]，所以就可以并且必须采用v= 0..V的顺序循环。
\’\’\’
for(int i = 1; i <= n; i++){
for(int j = v[i]; j <=m ; j--){
dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
}
}
\’\’\’
‘’‘
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
vector<int>dp(1010,0);
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++){
int v,w;
cin>>v>>w;
for(int j = v;j<=m;j++){
dp[j] = max( dp[j],dp[j-v]+w);
}
}
cout<<dp[m];
return 0;
}
’‘’
3: 多重背包问题
题目
有N种物品和一个容量为V的背包。第i种物品最多有s[i]件可用，每件体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取 s[i]件。令dp[i][j]表示前i种物品恰放入一个容量为j的背包的最大权值，则：
dp[i][j]=max{dp[i-1][j-k * v[i]] + k * w[i]|0<=k<=s[i]}
- 时间复杂度是O(V*∑n[i])。
\’\’\’
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
vector<int>dp(1010,0);
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int j = m;j>=v;j--){
for(int k = 1;k<=s&&(k*v)<=j;k++){
dp[j] = max(dp[j],dp[j-k*v]+k*w);
}
}
}
cout<<dp[m];
return 0;
}
\’\’\’
优化
二进制优化
将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,…,2(k-1),n[i]-2k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示。然后转化为01背包。
- 时间复杂度：将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为O(V*∑log n[i])的01背包问题。
\’\’\’
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct good{
int v;
int w;
};
int main(){
int n,m;
vector<good>goods;
vector<int>dp(21010,0);
cin>>n>>m;
for(int i = 1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int j = 1;j<=s;j*=2){
s-=j;
goods.push_back({v*j,w*j});
}
if(s>0) goods.push_back({v*s,w*s});
}
//01背包
for(auto good:goods){
for(int j = m;j>=good.v;j--){
dp[j] = max(dp[j],dp[j-good.v]+good.w);
}
}
cout<<dp[m];
return 0;
}
\’\’\’
O(N*V)的算法 单调队列解法
多重背包问题同样有O(N*V)的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。
4: 混合三种背包问题
问题
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 si 次（多重背包）；
每种物品体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
01背包与完全背包的混合
考虑到在P01和P02中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，时间复杂度是O(N*V)。
再加上多重背包
- 1.单调队列解法
- 2.二进制优化解法
本代码采用二进制优化的方法将每个这类物品分成O(logn[i])个01背包的物品的方法。
\’\’\’
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct good{
int v;
int w;
int s;
};
int main(){
int n,m;
vector<int>dp(10100,0);
vector<good>goods;
cin>>n>>m;
for(int i = 1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
if(-1 == s){
goods.push_back({v,w,-1});
}
else if(0 == s){
goods.push_back({v,w,0});
}
else{
//多重背包转化为二进制优化
for(int k = 1;k<=s;k*=2){
s-=k;
goods.push_back({v*k,w*k,-1});
}
if(s>0) goods.push_back({v*s,w*s,-1});
}
}
for(auto good:goods){
if(-1 == good.s){
//01背包
for(int j = m;j>=good.v;j--){
dp[j] = max(dp[j],dp[j-good.v]+good.w);
}
}
else{
//无穷背包
for(int j = good.v;j<=m;j++){
dp[j] = max(dp[j],dp[j-good.v]+good.w);
}
}
}
cout<< dp[m];
return 0;
}
\’\’\’
5: 二维费用的背包问题
问题
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。每件物品只能用一次。体积是 v[i]，重量是 m[i]，价值是 w[i]。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
算法
费用加了一维，只需状态也加一维即可。设dp[i][j][k]表示前i件物品付出两种代价分别为m和w时可获得的最大价值。状态转移方程就是：
dp[i][j][k]=max{dp[i-1][j][k],dp[i-1][j-v[i]][k-m[i]]+w[i]}
\’\’\’
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
int n,totalV,totalM;
vector<vector<int>> dp(10010,vector<int>(1010,0));
cin>>n>>totalV>>totalM;
for(int i = 1;i<=n;i++){
int v,s,w;
cin>>v>>s>>w;
for(int j = totalV;j>=v;j--){
for(int k = totalM;k>=s;k--){
dp[j][k] = max(dp[j][k],dp[j-v][k-s]+w);
}
}
}
cout<<dp[totalV][totalM];
return 0;
}
\’\’\’
6: 分组背包问题
问题
有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设dp[i][j]表示前i组物品在体积j能取得的最大价值，状态转移方程：
dp[i][j]=max{dp[i-1][j],dp[i-1][j-v[i]]+w[i]|物品i属于第k组}
\’\’\’
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
vector<int> dp(1010,0);
vector<int> v(110,0);
vector<int> w(110,0);
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++){
int group;
cin>>group;
for(int k = 0;k<group;k++) cin>>v[k]>>w[k];
for(int j = m;j>=0;j--){
for(int k = 0;k<group;k++){
if(j>=v[k]) dp[j] = max(dp[j],dp[j-v[k]]+w[k]);
}
}
}
cout<<dp[m];
return 0;
}
\’\’\’
7: 有依赖的背包问题 树状dp+分组背包
简化的问题
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。
算法
这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于6中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
再考虑6中的一句话：可以对每组中的物品应用2中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c[i]所有这些值时相应的最大价值f\'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费用为c[i]+k的物品的价值为f\'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为 V-c[i]+1个物品的物品组，就可以直接应用6的算法解决问题了。
更一般的问题
更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01 背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。
事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。
8: 泛化物品
定义
考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。
更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0..V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)。
这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0..V]，给它费用v，可得到价值h[V]。
一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/cw，其它函数值均为0。如果它是多重背包中重复次数最多为n的物品，那么它对应的泛化物品的函数有h(v)=v/cw仅当v被c整除且v/c<=n，其它情况函数值均为0。
一个物品组可以看作一个泛化物品h。对于一个0..V中的v，若物品组中不存在费用为v的的物品，则h(v)=0，否则h(v)为所有费用为v的物品的最大价值。P07中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。
泛化物品的和
如果面对两个泛化物品h和l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0..V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)。也即f(v)=max{h(k) +l(v-k)|0<=k<=v}。可以看到，f也是一个由泛化物品h和l决定的定义域为0..V的函数，也就是说，f是一个由泛化物品h和 l决定的泛化物品。
由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足f(v)=max{h(k)+l(v-k)|0<=k<=v}，则称f是h与l的和，即f=h+l。这个运算的时间复杂度是O(V^2)。
泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，则答案就是s[0..V]中的最大值。
背包问题的泛化物品
一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说，给定了所有条件以后，就可以对每个非负整数v求得：若背包容量为v，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品——或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息。一般而言，求得这个泛化物品的一个子域（例如0..V）的值之后，就可以根据这个函数的取值得到背包问题的最终答案。
综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。
9: 背包问题问法的变化
要求的是“总价值最小”“总件数最小”，只需简单的将上面的状态转移方程中的max改成min即可。
输出方案数
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。
参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。
以01背包为例，方程为
dp[i][j]=max{dp[i-1][j],dp[i-1][j-v[i]]+w[i]}
再用一个数组g[i][j]，设g[i][j]=0表示推出dp[i][j]的值时是采用了方程的前一项（也即dp[i][j]=dp[i-1][j]）,否则g[i][j]表示采用了方程的后一项（dp[i-1][j-v[i]]+w[i]]）。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品。
‘’‘
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
vector<int>dp(10010,-1e9);
vector<int>g(1010,0);
int mod = 1e9+7;
int n,m;
cin>>n>>m;
dp[0] = 0;
g[0] = 1;
for(int i = 1;i<=n;i++){
int v,w;
cin>>v>>w;
for(int j = m;j>=v;j--){
int res = max(dp[j],dp[j-v]+w);
int s = 0;
if(res == dp[j]) s+= g[j];
if(res == (dp[j-v]+w)) s += g[j-v];
g[j] = s%mod;
dp[j] = res;
}
}
int maxw = 0;
for(int i = 0;i<=m;i++){
maxw = max(maxw,dp[i]);
}
int ans = 0;
for(int i = 0;i<=m;i++){
if( maxw == dp[i]) {
ans +=g[i];
}
}
cout<<ans;
return 0;
}
’‘’
输出字典序最小的最优方案 借鉴
这里“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。
假设存在一个包含第1个物品的最优解，为了确保字典序最小那么我们必然要选第一个。那么问题就转化成从2～N这些物品中找到最优解。之前的dp(i,j)记录的都是前i个物品总容量为j的最优解，现在将dp(i,j)定义为
从第i个元素到最后一个元素总容量为j的最优解
接下来考虑状态转移：
dp(i,j)=max(dp(i+1,j),dp(i+1,j−v[i])+w[i])
两种情况，第一种是不选第i个物品，那么最优解等同于从第i+1个物品到最后一个元素总容量为j的最优解；第二种是选了第i个物品，那么最优解等于当前物品的价值w[i]加上从第i+1个物品到最后一个元素总容量为j−v[i]的最优解。
计算完状态表示后，考虑如何的到最小字典序的解。首先dp(1,m)肯定是最大价值，那么我们便开始考虑能否选取第1个物品呢。
如果dp(1,m)=dp(2,m−v[1])+w[1]，说明选取了第1个物品可以得到最优解。
如果dp(1,m)=dp(2,m)，说明不选取第一个物品才能得到最优解。
如果dp(1,m)=dp(2,m)=dp(2,m−v[1])+w[1]，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。
\’\’\’
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int n,m;
vector<vector<int>>dp(1010,vector<int>(1010,0));
vector<int> v(1010,0);
vector<int> w(1010,0);
cin>>n>>m;
for(int i = 1;i<=n;i++) cin>>v[i]>>w[i];
for(int i = n;i>=1;i--){
for(int j = 0;j<=m;j++){
dp[i][j] = dp[i+1][j];
if(j>=v[i]) dp[i][j] = max(dp[i][j],dp[i+1][j-v[i]]+w[i]);
}
}
int nowV = m;
for(int i = 1;i<=n;i++){
if(nowV>=v[i]&&dp[i][nowV] == dp[i+1][nowV-v[i]]+w[i]){//选了第i个
cout<<i<<\' \';
nowV-=v[i];
}
}
return 0;
}
\’\’\’