Variant of Bag Problems
这篇文章详细分析背包问题的变形问题。
前言
在阅读篇文章之前你可能需要首先阅读01 背包问题,以对背包问题有一个基本的了解。
完全背包问题
前提
完全背包解除了物品数量的限制，使得所有的所有的物品都可以无限量供应。
试一试
递推
我们仍考虑是否要将第 i 个物品装入背包。默认仍不装入这个物品。
f[i][j] = f[i-1][j];接下来相比于 01 背包的改变是，当我们有机会装入第 i 个物品时，我们仍可以继续考虑装入第 i 个物品。
if(j >= weights[i]) f[i][j] = max(f[i][j] , f[i][j-weights[i]] + values[i]);所以在 f[i][j-weights[i]] + values[i] 中, i 并不需要减少。另外可以想见，在递推中所需求的位置是有解的。 
优化
根据先前的优化思路，我们仍可以将这个过程中的空间优化至一维。在 01 背包中，递推时需要的是对于 前 i -1 物品所构成的装填方案 的所有正确的解，所以我们要保留先前的解，这才从行的末尾向前递推。
而在完全背包中，递推一个新的位置需求的是 对于 前 i 物品所构成的装填方案 而将新旧行交替时，必须从左往右递推，逐步替代掉上一行的旧解。0 - weights[i] 这些位置不能装载第 i 个物品，所以直接保留上一行的解，从 weights[i]开始递推至行末尾即可。 
优化代码
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int weights[N] , values[N];
int f[N];
int main()
{
int N , V; cin >> N >> V;
for(int i = 1 ; i <= N ; i++)
cin >> weights[i] >> values[i];
for(int i = 1 ; i <= N ; i++)
{
for(int j = weights[i] ; j <= V ; j++)
{
f[j] = max(f[j] , f[j-weights[i]] + values[i]);
}
}
cout << f[V];
}多重背包问题
前提
多重背包的限制条件介于 01 背包和完全背包之间，为每种物品增加数量上限。
试一试
读入
多添加一个 nums 数组以存储数量信息。
int weights[N] , values[N] , nums[N];递推
相信已经轻车熟路，仍从不装入第 i 个物品开始考虑。
f[i][j] = f[i-1][j];接着我们考虑装入装入第 i 个物品的数量，通过枚举实现。这里有两个限制
- 数量不能超过给定的上限
- 总体积不能超过背包在当前子问题中的容量
for(int k = 1 ; k <= nums[i] && k * weights[i] <= j; k++)
{
f[i][j] = max(f[i][j] , f[i-1][j-k*weights[i]] + k * values[i]);
}说明
- 这里当第 i 物品的数量确定，就不能再选择，所以
f[i-1][j-k*weights[i]]此处 i 减了一。 - 装入第 k 个 i 号物品，要减去 k 份体积，加上 k 个价值。
从 k = 0 开始枚举时，这两种情况可以合并，写作
for(int k = 0 ; k <= nums[i] && k * weights[i] <= j; k++)
{
f[i][j] = max(f[i][j] , f[i-1][j-k*weights[i]] + k * values[i]);
}空间优化
这里递推时利用的上一行的信息，所以在使用滚动数组时，仍是从尾部向前计算新行。原理和之前类似，这里不再给出图解。
#include<iostream>
using namespace std;
const int N = 110;
int weights[N] , values[N] , nums[N];
int f[N];
int main()
{
int N , V; cin >> N >> V;
for(int i = 1 ; i <= N ; i++)
cin >> weights[i] >> values[i] >> nums[i];
for(int i = 1 ; i <= N ; i++)
{
for(int j = V ; j >= weights[i] ; j--)
{
for(int k = 0 ; k <= nums[i] && k * weights[i] <= j; k++)
{
f[j] = max(f[j] , f[j-k*weights[i]] + k * values[i]);
}
}
}
cout << f[V];
}时间优化
二进优化原理
对于这个问题，其计算复杂度为 O(N * V * K)。我们可以考虑在枚举 K 时实施二进制优化。枚举 K 的目的是一个怎样的过程？我们为了确定在当前的背包容量下的最佳装填方案是什么。而这个最佳装填方案对应了一个确定的 K 值，所以枚举所有可能的 K。
我们可以这样构造它的一个等价问题。假设我们所有第 i 个物品分为 1 , 2 , 4 , 8 ...... 这样的组。满足最后一个非 2 进制数组大于前一个组。 
现在思考这也一个问题，我们在考虑第 i 个物品时，必须考虑装入一个整个组，以此来求解f[i][j]的最大值。这是否和之前是一样的问题?
证明 它们是一样的问题。因为1 - nums[i]中的任何一个 K，都可以找到一种对应分组选择方案。可以递推这证明这一点。
- 1 , 2 可以表示出
[1 , 3]中任何一个数 [1 , 3]和 4 可以表示[1 , 7]中的任何一个数。[1 , 7]和 8 可以表示[1 , 15]中的任何一个数。[1 , 15]和nums[i] - 8可以表示出[1 , nums[i]]中的任何一个数。
现在构造并且求解这样的等价问题。
代码
#include<iostream>
#include<cmath>
using namespace std;
const int N = 2010 * 12;
int values[N] , weights[N] , group = 0;
int f[2010];
int main()
{
int N , V; cin >> N >> V;
for(int i = 1 ; i <= N ; i++)
{
int w , v , s;
cin >> w >> v >> s;
int k = 1;
while(s > k)
{
group++;
weights[group] = k * w;
values[group] = k * v;
s -= k;
k *= 2;
}
if(s)
{
group++;
weights[group] = s * w;
values[group] = s * v;
}
}
for(int i = 1 ; i <= group ; i++)
{
for(int j = V ; j >= weights[i] ; j--)
{
f[j] = max(f[j] , f[j-weights[i]] + values[i]);
}
}
cout << f[V];
}说明
- 分组会导致物品数量数量变多，在存储需要开辟额外的空间。
- 分完组之后，根据先前的推导，这个问题变成了一个 01 背包问题。
分组背包
前提
限制 为所有物品分组，限定只能从每组中拿出一个物品。
试一试
读入
使用额外的空间来记录每组内物品数量，将每组物品存入二维数组的行中。
const int N = 110;
int numInGroups[N]; // 保存每组有多少物品
int weights[N][N] , values[N][N]; // 每组物品的体积和价值
int f[N][N]; // dp表递推
考虑是否装入第i组的物品，如果装入，那么枚举得到子问题的最佳解。
f[i][j] = f[i-1][j]; // 不装入第i组的物品
// 枚举
for(int k = 1 ; k <= numInGroups[i] ; k++)
{
if(weights[i][k] <= j)
f[i][j] = max(f[i][j] , f[i-1][j-weights[i][k]] + values[i][k]);
}完整代码
#include<iostream>
using namespace std;
const int N = 110;
int numInGroups[N]; // 保存每组有多少物品
int weights[N][N] , values[N][N]; // 每组物品的体积和价值
int f[N][N]; // dp表
int main()
{
int N , V; cin >> N >> V;
for(int i = 1 ; i <= N ; i++)
{
cin >> numInGroups[i];
for(int j = 1 ; j <= numInGroups[i] ; j++)
{
cin >> weights[i][j] >> values[i][j];
}
}
for(int i = 1 ; i <= N ; i++)
{
for(int j = 1 ; j <= V ; j++)
{
f[i][j] = f[i-1][j];
for(int k = 1 ; k <= numInGroups[i] ; k++)
{
if(weights[i][k] <= j)
f[i][j] = max(f[i][j] , f[i-1][j-weights[i][k]] + values[i][k]);
}
}
}
cout << f[N][V];
}