背包问题
整理总结一下背包问题, 看OI Wiki上列了好多, 但是代码又太细了, 然后背包九讲里面也列了很多原理公式, 但是源代码有点粗糙, 总结一下
01背包
万恶之源, 01代表选择(一个)与否, 告诉你容量 W 的背包, 每件物品价值是 v[i], 让你求最大价值.
先套用一般动态规划模板来求解
然而本题重点是记住 dp 的定义, dp[i][j] 代表在[0, i]的物品里选择, 背包容量为 j 的最大价值(其实你正常想应该也想不出其他的定义方法)
那么很容易写出以下转移函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int knapsack(vector<int> &weight, vector<int> &val, int W)
{
vector<vector<int>> dp(weight.size(), vector<int>(W + 1, 0));
for(int i = 0; i < weight.size(); ++i)
for(int j = 0; j <= W; ++j)
// 装不下
if(j - weight[i] < 0)
dp[i][j] = dp[i - 1][j];
else
// 装和不装选个最大的
dp[i][j] = max(
dp[i - 1][j],
dp[i - 1][j - weight[i]] + val[i]
);
return dp[weight.size() - 1][W];
}
考虑到每一行的状态都取决于上一行的状态, 那么就进行状态压缩
易错点: 你要是还按照从上至下从左至右的顺序遍历就错了, 要考虑清楚当前状态相关的前一行状态究竟是前一行还是本行刷新过了
如果是按照错误的方式写出, 那对应的结果是什么?
考虑清楚易错点后, 答案就很显然了
1
2
3
4
5
6
7
8
9
10
11
12
int knapsack(vector<int> &weight, vector<int> &val, int W)
{
vector<int> dp(W + 1, 0);
for(int i = 0; i < weight.size(); ++i)
for(int j = W; j >= weight[i]; --j)
// 明确了遍历范围可以避免索引超出
dp[j] = max(
dp[j],
dp[j - weight[i]] + val[i]
);
return dp[W];
}
每个状态都遍历了一次, 因此时间复杂度 $O(weight.size() * W)$, 空间复杂度能优化至 $O(W)$
完全背包
完全背包即是01背包的基础上加了物品无限的条件(每个物品能无限装进背包)
依然常规 dp 思路考虑, 每个物品选择不再是$[0, 1]$, 而是$[0, \frac{W}{weight[i]}]$, 状态转移方程如下
1
2
3
4
5
dp[i][j] = max(
dp[i - 1][j],
// 从i开始, 即当前的物品也能放入背包, 则由此包括了多次选择本物品的策略
dp[i][j - weight[i]] + val[i]
);
那么我们可以知道前文的思考的答案
1
2
3
4
5
6
7
8
9
10
11
int knapsack(vector<int> &weight, vector<int> &val, int W)
{
vector<int> dp(W + 1, 0);
for(int i = 0; i < weight.size(); ++i)
for(int j = 0; j <= W; ++j)
dp[j] = max(
dp[j],
dp[j - weight[i]] + val[i]
);
return dp[W];
}
多重背包
在完全背包的基础上增加限制, 每个物品的使用次数是有限的, 为 count[i], 那么可以有以下思路将问题转换为01背包: 将该物品分成 count[i] 份一样的物品, 这样问题转换为01背包问题, 状态规模为$O(W\Sigma_{i=1}^ncount[i])$
如果是按照上述策略进行计算, 会产生一些重复性计算过程, 举例: 你会多次判断选择两个物品 i 的情况
在上述思路的基础上引入二进制分组进行优化: 我们将物品 i 拆分并打包成, 1, 2, 4…, $2^{\lfloor \log_2(count[i]+1) \rfloor-1}, count[i] - 2^{\lfloor \log_2(count[i]+1) \rfloor-1}$新物品, 我们可以通过一组二进制数来表示选择 $\forall n \leq count[i]$ 个物品, 举例如下, 最终的状态规模会变成$O(W\Sigma_{i=1}^n\log_2(count[i]))$
- 6 = 1 + 2 + 3
- 8 = 1 + 2 + 4 + 1
- 31 = 1 + 2 + 4 + 8 + 16
此处转换为二进制是由于任意整数都能够由{1,2,4,8,…}一系列2的幂与剩余数求和; 若转换为其他进制则不能起到减小状态规模的作用(你举三进制的例子就和十进制的情况一样的, 幂之间总需要额外的状态填补)
还能通过单调队列实现最终为$O(W*count.size())$的方法, OI wiki上有推导的数学公式, 大体是各种代换, 使得最终的状态转移函数变成一个在连续区间内求最值的一种形式. 这里的blog有另一种方向的解释.
混合背包
就是上述三种问题混在一起, 有的01, 有的完全, 有的多重. 直接分类讨论(根据个数判断)套用上述三种方案即可
二维背包
原有背包问题的基础上, 对背包增加额外的费用属性, 可以根据背包问题类型选择对应的方案即可, 这里只给出01背包示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
int knapsack(vector<int> &weight1, vector<int> &weight2, vector<int> &val, int W1, int W2)
{
vector<vector<int>> dp(W1 + 1, vector<int>(W2 + 1, 0));
for(int i = 0; i < weight1.size(); ++i)
for(int j = W1; j >= weight1[i]; --j)
for(int k = W2; k >= weight2[i]; --k)
dp[j][k] = max(
dp[j][k],
dp[j - weight1[i]][k - weight2[i]] + val[i]
);
// 最终的答案可能得根据问题问法得到
return ans;
}
许多情况下, 额外的费用熟悉并不会十分显性的在问题中出现, 例如: “最多只能取M件物品”, 就增加了个数的费用, 最终的答案就是dp整个表中的最大值; “恰好取M件物品”, 最终的答案就是
*max_element(dp[W1].begin(), dp[W1].end())
分组背包
将物品分为若干组, 每个组只允许取一件物品. 问题就被转换为对每个组进行一次01背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int knapsack(vector<int> &weight, vector<vector<int>> &group, vector<int> &val, int W)
{
vector<int> dp(W + 1, 0);
// 遍历组
for(int i = 0; i < group.size(); ++i)
// 遍历背包容量
for(int j = W; j >= 0; --j)
// 遍历组中的每个物品
for(int k = 0; k <= group[i].size(); ++k)
if(j >= weight[group[i][k]])
dp[j] = max(
dp[j],
dp[j - weight[group[i][k]]] + val[weight[group[i][k]]]
);
return dp[W];
}
遍历顺序必须是组-容量-物品, 否则是错误的!
因为是对每个组内进行01背包求解, 相较于原01背包, 物品-容量; 此处的组可以看成泛化的物品, 物品则是与组依赖的子物品. 这个思路在下文的依赖背包中得到详细阐述.
依赖背包
泛化了分组背包的相关关系, 使得物品之间存在某种依赖关系, 即若物品 i 依赖于物品 j, 则选 i 必须也选择 j. 我们称不依赖于别的物品的物品称为”主件”, 依赖于某主件的物品称为”附件”. 则前文的分组背包中的一个组, 可以看成此处的主件-附件集合.
最大深度不超过2的只有一个根节点的依赖森林
这个就概括了前文的分组背包问题, 总的来说有以下两个性质
- 一个物品只依赖一种物品
不存在一个被依赖的物品, 它依赖其他物品
- 从更一般的角度分析前文解法
泛化背包
将整个背包问题泛化, 使得价值是一个与费用相关的函数. 这种抽象化思想有助于将更多问题都归纳为背包问题进行求解. 不过思维难度好高, 目前的我缺乏足够的积累去理解这个问题, 即使勉强囫囵吞枣, 也不能好好消化
背包问题的扩展问法与变种
输出方案
我们只需要在每次转移函数时, 记录做出的选择即可, 通过 $G_{i, v}$ 表示背包空间为 v 时是否选择了第 i 个物品.
1
2
3
4
5
6
7
8
9
10
11
// 输出
for(int idx = LastItemIdx; idx >= FirstItemIdx; --idx)
{
if(G[i][v])
{
cout << "选择了第" << i << "个物品" << endl;
v -= weight[i];
}
else
cout << "未选择了第" << i << "个物品" << endl;
}
方案总数
对使得背包装到容量 V 的方案总数
考虑到不是求最终最优方案, 那么转移函数中的求最值改成求和即可, 即dp定义为方案数, 而非最大价值
注意, 此时dp初始状态为1, 因为什么都不装也是一种方案
最优方案总数
这里的最优指的是能够获得最大价值的方案
- 未完成