背包问题总结
背包问题是动态规划思想和方法的经典应用问题，本文将从0-1背包，完全背包和混合背包三个角度来分析简单背包问题的求解方法。
背包问题
背包问题本质上是规划型问题，问题的核心在于在满足约束条件下，找到一种选择方案，使得目标值达到最优。通过动态规划的方法，可以将此类问题限制在多项式复杂度的时间内求解。
0-1背包
0-1背包问题的描述
有N件物品和一个总容量为V的背包，第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可以使得装入的物品的价值总和最大。
0-1背包问题的动态转移
动态转移方程：
$$ f[i][v] = max{f[i-1][v], f[i-1][v-c[i]]+w[i]} $$
解释；对于每一个状态，在决策是否装入第i件时，选取装入与不装入该件物品的价值和的最大值。如果放入第i件物品，那么前i件物品最多只能占用v-c[i]的体积，则价值和为f[i-1][w-c[i]]，如果不装入第i件物品，那么价值和仍为前i-1件物品的价值和。
时间和空间复杂度分析
该算法时间复杂度为O(V*N)，如果只需要求解价值总和的最大值，由于只需要根据价值进行DP，空间复杂度可以优化到O(N)。
代码表述如下：
for(int i = 1; i <= n; ++i) {
for(int j = v; j >= c[i]; j--) {
f[j] = max(f[j], (f[j-c[i]] + w[i]));
/** 不优化空间的写法
* f[i][j] = max(f[i-1][j], (f[i-1][j-c[i]] + w[i]));
*/
}
}
回溯法推导0-1背包问题的最优方案
可以通过回溯的方法求解到底放入了那些背包，在这个求解过程中，不能进行空间的优化，因此，空间占用为O(V*N)。具体代码表述如下：
/**
* sum 值为之前DP求出的最大价值。
* used 数组用来标记每件物品是否装入。
* 如果第 i 件物品装入了，则 used[i] = true；
* 否则，used[i] = false。
*/
bool used[n] = {false};
for(i = n; i >= 0; --i) {
if(f[i][sum] > f[i-1][sum]) {
used[i] = true;
sum -= w[i];
}
}
另一种获取方案的方法
可以使用一个二维数组flag在更新f时对更新的trace进行记录，然后回溯，便可以得到方案：
int flag[n+1][v+1] = 0;
for(int i = 1; i <= n; ++i) {
for(int j = v; j >= c[i]; j--) {
if(f[j] < f[j-c[i]]+w[i]) {
f[j] = f[j-c[i]] + w[i]);
flag[i][j] = 1;
}
}
}
/**
* 顺序输出物品编号
*/
void output() {
int i = N, j = V;
while(i) {
if(flag[i][j] == 1) {
cout << i << " ";
j -= w[i];
}
i--;
}
cout << endl;
}
/**
* 逆序输出物品编号
*/
void output_reverse() {
if(i == 0 || j == 0) {
return;
}
if(flag[i][j] == 1) {
output_reverse(i-1, j-w[i]);
cout << i << " ";
}
}
完全背包
完全背包问题的描述
有N种物品和一个容量为V的背包，每种物品有无限件可用。第i件物品的费用为c[i]，价值是w[i]。求解将哪些物品装入背包可以使得装入的物品的价值总和最大，并且物品总费用不能超过背包容量。
完全背包问题的状态转移
显然，完全背包问题可以转换为0-1背包问题，通过总体积来限制背包个数即可。不难得出以下的状态转移方程：
$$ f[i][v] = max{f[i-1][v-k \times c[i]] + k \times w[i]} $$
其中，
$$ 0 \leq k \times c[i] \leq v $$
分析得知，此状态转移求解每个状态的时间已经不是常数了。分析完全背包问题的特点，可以作出优化。分析思路：如果两件物品 i,j 满足 c[i] <= c[j] 且 w[i] >= w[j] , 则将物品j去掉，不用考虑。优化的正确性在于任何情况下都可以用物美价廉的i替换j，至少不会比替换前的方案更差。但此优化在最坏情形下并不能改善问题的复杂度规模，因为在最坏情况下任何一件物品都不能忽略。
考虑到每种物品都有无限件可以选，因此，在选择第i件物品时，只要根据一个绝无已经选入第i种物品的子结果f[i-1][v-[i]]即可。在具体实现上，只要改变V的递推顺序就行。
代码表述如下：
for(int i = 1; i <= n; ++i) {
for(int j = c[i]; j <= v; ++j) {
f[j] = max(f[j], f[j-c[i]]+w[i]);
}
}
算法复杂度分析
优化后的时间复杂度为O(N*V)，空间复杂度为O(V)。
混合背包
混合背包问题的描述
有N种物品和一个容量为V的背包，第i种物品最多有n[i]件可用，每件费用为c[i]，价值为w[i]。求解选择方案使得物品价值总和最大，且总重量不超过背包容量，每件物品的数量也不超过其限制。
混合背包的朴素求解
同混合背包类似，完全背包问题也可以建模为0-1背包模型，但无法在常数时间内求解每个状态，其时间复杂度会达到O(n3)。
混合背包的二进制拆分求解
二进制拆分实际上是对朴素求解算法的优化。通过二进制拆分可以减少状态数。其原理基于每一个正整数都可以写成数个2的自然数次幂之和，并且，每两个幂的次数都不相同。此优化方案可以将时间复杂度优化到O(n2*log(n))。
代码描述如下：
for(int i = 1; i <= n; ++i) {
int s[mi][2], k = 1, t = 0;
while(true) {
if(m[i] <= k) {
s[t][0] = m[i] * c[i], s[t++][1] = m[i] * w[i];
break;
}
else {
s[t][0] = k * c[i], s[t++][1] = k * w[i];
}
m[i] = m[i] - k;
k = k * 2;
}
while(t--) {
for(j = v; j >= s[t][0]; j--) {
f[j] = max(f[j], (f[j-s[t][0]] + s[t][1]));
}
}
}
混合背包的单调队列优化
该算法的思想是根据当前体积模当前物品体积的余数进行分组，每一组的状态都可以有前面的任意一组转换而来。问题可以转化为固定长度区间求最值问题。采用单调队列，可以将时间复杂度优化到O(N*V)。
代码表述如下：
/**
* a, b 均为辅助队列，其中，b 是一个单调队列。
*/
for(int i = 1; i <= n; ++i) {
// 优化最多可用的物品件数
if(!n[i] || v/c[i] < n[i]) {
n[i] = v / c[i];
}
for(int d = 0; d < c[i]; ++d) {
int l = 1, r = 0; // 初始化队列参数，清空队列。
for(int j = 0; j <= (v-d)/c[i]; ++j) {
// j 对应的体积为 j*c[i]+d。
int x = j, y = f[j*c[i]+d] - j*w[i]; // 退化
// 插入队列
while(l <= r && b[r] <= y) {
r--;
}
a[++r] = x;
b[r] = y;
// 如果队首元素已经失效，删除失效点。
if(a[l] < j - n[i]) {
l++;
}
// 取得队头，进行更新。
f[j*c[i]+d] = b[l] + j*w[i];
}
}
}
参考
Tags: Algorithm