多重背包如何解决不同物品数量限制的长尾词问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计2542个文字，预计阅读时间需要11分钟。
多重背包问题前准备：
在阅读本文之前，需要掌握以下内容：
1. 基础dp背包算法
2.单调队列
3.多重背包问题是什么
4.多重背包问题定义：
给定 + 种物品，每种物品有若干件，每件物品有价值和重量，求按重量限制装物品的最大价值。具体内容如下：
多重背包问题定义：给定 + 种物品，每种物品有若干件，每件物品有价值和重量，求按重量限制装物品的最大价值。
多重背包笔记 前置芝士在看本文之前，需要掌握：
多重背包问题是什么基础dp背包算法;
单调队列
多重背包是指这样一类问题：给定\(n\)种物体，每种物体具有三个属性\(v\)，\(w\)，\(c\)，分别代表其体积，价值和数量。要求在其中选出一些，满足第\(i\)种物品最多选择\(c_i\)个，体积总和\(sum_v \leq m\)，使得价值总和\(sum_w\)最大。
输入数据一般形如：
题目链接第1行输入两个数\(n\)和\(m\)
第\(2\)~\((n+1)\)行每行3个数\(v\)，\(w\)，\(c\)表示一个物体。
朴素解法
常规解法：二进制拆分
最优解：单调队列优化
动态规划的状态\(f_{i,j}\)表示前\(i\)种物体刚好放满容量为\(j\)的背包中获得的最大价值。显然可以枚举i，j，对于\(i\)的每次转移都考虑选取该类物品中的多少个。其时间复杂度为\(O(m*sum_c)\)，基本不可接受。
代码考虑到\(i\)的每次转移都只会用到上一次的状态，可以使用了滚动数组的方式进行优化。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int c[110];
LL v[110], w[110];
LL f[2][110];
int main(void) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%d", &v[i], &w[i], &c[i]);
}
// 前面都是输入不多说，
// 下面开始初始化状态
memset(f, 0, sizeof(f));
// 注意是刚好j体积
for (int i = 0; i <= c[1] && i * v[1] <= m; ++i) {
f[1][i * v[1]] = i * w[1];
}
for (int i = 2; i <= n; ++i) {
for (int j = v[i]; j <= m; ++j) {
for (int k = 0; k <= c[i] && k * v[i] <= j; ++k) {
// 这里对二取模也就是滚动数组优化
f[i % 2][j] = max(f[i % 2][j],
f[(i - 1) % 2][j - k * v[i]] + k * w[i]);
}
}
}
// 由于我们f数组是计算刚好j体积而不是小于等于，
// 所以需要再进行一遍统计
LL res = 0;
for (int i = 0; i <= m; ++i) {
res = max(res, f[n % 2][i]);
}
printf("%lld\n", res);
return 0;
}
常规解法：二进制拆分
朴素解法的瓶颈在于，对于每一种物品，都要逐一枚举选取的数量，相当于把一种物品拆分成了c个一个一个取的01背包，这让时间爆炸增长。我们能不能优化这种拆分方式呢？答案是肯定的。
考虑二进制拆分的原理，任何一个整数都可以表示为许多2的幂次之和，并且每一个不同的二的幂次只会出现一次！这不就是01背包的限制条件吗？于是，我们得到了优化的拆分方案。
对于一种物品，我们先尽量拆成1，2，4，8大小的组，最后无法分出剩下的再单独分为一组，这样保证0~\(c\)之间所有的取法都能产生。此时的物体总数是\(O(\sum^{n}_{i = 1}{\log{c}})\)，总的时间复杂度就是它再乘上m。这个时间复杂度一般可以接受。
代码第一部分是输入并用二进制分解物品：
int n, m;
scanf("%d%d", &n, &m);
vector<pair<LL, LL> > vec;
for (int i = 1; i <= n; ++i) {
LL v, w;
int c;
scanf("%lld%lld%d", &v, &w, &c);
int sum = 0;
// 注意细节：预先判断，如果加入后会超过限制就不能加入
for (int k = 1; sum + k <= c; k *= 2) {
vec.push_back(make_pair(k * v, k * w));
sum += k;
}
// 如果有剩余再将剩余单独打包成一个组
if (c - sum > 0) {
vec.push_back(make_pair((c - sum) * v, (c - sum) * w));
}
}
接下来是常规的01背包解法：
// 注意细节：这里有可能会爆掉空间或者越界访问
if (!vec.empty() && vec[0].first <= m) {
f[0][vec[0].first] = vec[0].second;
}
for (int i = 1; i < vec.size(); ++i) {
for (int j = vec[i].first; j <= m; ++j) {
// 同样的滚动数组优化
f[i % 2][j] = max(f[(i - 1) % 2][j],
f[(i - 1) % 2][j - vec[i].first] + vec[i].second);
}
}
最后统计结果，和刚才一样，完整代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[2][2010];
int main(void) {
int n, m;
scanf("%d%d", &n, &m);
vector<pair<LL, LL> > vec;
for (int i = 1; i <= n; ++i) {
LL v, w;
int c;
scanf("%lld%lld%d", &v, &w, &c);
int sum = 0;
for (int k = 1; sum + k <= c; k *= 2) {
vec.push_back(make_pair(k * v, k * w));
sum += k;
}
if (c - sum > 0) {
vec.push_back(make_pair((c - sum) * v, (c - sum) * w));
}
}
if (vec[0].first <= m) {
f[0][vec[0].first] = vec[0].second;
}
for (int i = 1; i < vec.size(); ++i) {
for (int j = vec[i].first; j <= m; ++j) {
f[i % 2][j] = max(f[(i - 1) % 2][j],
f[(i - 1) % 2][j - vec[i].first] + vec[i].second);
}
}
LL res = 0;
for (int i = 0; i <= m; ++i) {
res = max(res, f[(vec.size() - 1) % 2][i]);
}
printf("%lld\n", res);
return 0;
}
最优解：单调队列优化动态规划
正片开始！
首先考虑朴素解中的状态转移方程：
\[f_{i, j} = \max_{k = 0}^{\min\{c_i, \lfloor \frac{j}{v_i} \rfloor\}}\{f_{i - 1, j - kv_i} + kw_i\} \]对这个式子进行一下分析，可以发现以下性质：
-
在一次\(i\)转移内部，许多东西是不变的。具体地，\(c_i\), \(w_i\), \(v_i\)始终不变；\(j\)的范围不变：\(v_i\)到\(m\)。这些性质使得我们的处理方便了许多，
然而实际上没有在算法中起到决定性作用。 -
对于每一个\(j\)，它只可能是从上个\(i\)转移的\(j\)，\(j - 2v_i\)，…，\(j-kv_i\)转移而来，也就是说，所有会互相影响的\(j\)转移都模\(v_i\)同余。这就给我们一个启发：根据模\(v_i\)的余数进行分组，分成\(v_i\)组。
由性质一，我们在以后的讨论中省略\(i\)下标（对于\(\max\)符号中的\(f\)，一定是\(i-1\)，对于其它是\(i\)）。另外设\(k\)的范围\(t = \min\{c_i, \lfloor \frac{j}{v_i} \rfloor\}\)。
由性质二，我们将每一个\(j\)拆分成\(pv + q\)，其中的q就是分组的依据，在每一组内，它是一个定值。于是状态转移方程变为了：
\[f_{pv+q} = \max_{k = 0}^{t}\{f_{(p-k)v} + kw\} \]看上去好像进行不下去了呢。我们来举一个例子便于推导。假设对于所有的\(j\)，\(t\)都是2，并取\(q = 1\)。那么显然有一下式子（\(p\)太小的就不列出来了）：
\[f_{3v+1} = \max\{f_{3v+1}, f_{2v+1}+w, f_{v+1}+2w\} \]\[f_{4v+1} = \max\{f_{4v+1}, f_{3v+1}+w, f_{2v+1}+2w\} \]\[f_{5v+1} = \max\{f_{5v+1}, f_{4v+1}+w, f_{3v+1}+2w\} \]\[f_{6v+1} = \max\{f_{6v+1}, f_{5v+1}+w, f_{4v+1}+2w\} \]\[...... \]看上去好像还是不能优化呢。但我们如果忽略掉\(\max\)符号内的这些\(w\)尾巴呢？再列一次：
\[\{f_{3v+1}, f_{2v+1}, f_{v+1}\} \]\[\{f_{4v+1}, f_{3v+1}, f_{2v+1}\} \]\[\{f_{5v+1}, f_{4v+1}, f_{3v+1}\} \]\[\{f_{6v+1}, f_{5v+1}, f_{4v+1}\} \]\[...... \]这也就是单调队列所需的形式。于是我们考虑将原式中的\(w\)“尾巴”想办法处理掉，让它们也可以用单调队列来优化。考虑将\(f_{pv+1}\)这一行中的这些项都减掉\(pw\)，再在末尾加上去，就变成了：
\[f_{3v+1} = \max\{f_{3v+1}-3w, f_{2v+1}-2w, f_{v+1}-w\}+3w \]\[f_{4v+1} = \max\{f_{4v+1}-4w, f_{3v+1}-3w, f_{2v+1}-2w\}+4w \]\[f_{5v+1} = \max\{f_{5v+1}-5w, f_{4v+1}-4w, f_{3v+1}-3w\}+5w \]\[f_{6v+1} = \max\{f_{6v+1}-6w, f_{5v+1}-5w, f_{4v+1}-4w\}+6w \]\[...... \]这样的形式就可以使用单调队列来维护，这个问题得到了完美解决。
代码#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int c[1010];
LL v[1010], w[1010];
LL f[2][20010];
int main(void) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%d", &v[i], &w[i], &c[i]);
}
for (int i = 1; i <= c[1] && i * v[1] <= m; ++i) {
f[1][i * v[1]] = i * w[1];
}
for (int i = 2; i <= n; ++i) {
for (int q = 0; q < v[i]; ++q) {
deque<pair<int, LL> > que;
for (int p = 0; p * v[i] + q <= m; ++p) {
int j = p * v[i] + q, t = min(c[i], p);
while (!que.empty() &&
p - que.front().first > t) {
que.pop_front();
}
while (!que.empty() &&
que.back().second <= f[(i - 1) % 2][j] - p * w[i]) {
que.pop_back();
}
que.push_back(make_pair(p, f[(i - 1) % 2][j] - p * w[i]));
f[i % 2][j] = que.front().second + p * w[i];
}
}
}
LL res = 0;
for (int i = 0; i <= m; ++i) {
res = max(res, f[n % 2][i]);
}
printf("%lld\n", res);
return 0;
}
本文共计2542个文字，预计阅读时间需要11分钟。
多重背包问题前准备：
在阅读本文之前，需要掌握以下内容：
1. 基础dp背包算法
2.单调队列
3.多重背包问题是什么
4.多重背包问题定义：
给定 + 种物品，每种物品有若干件，每件物品有价值和重量，求按重量限制装物品的最大价值。具体内容如下：
多重背包问题定义：给定 + 种物品，每种物品有若干件，每件物品有价值和重量，求按重量限制装物品的最大价值。
多重背包笔记 前置芝士在看本文之前，需要掌握：
多重背包问题是什么基础dp背包算法;
单调队列
多重背包是指这样一类问题：给定\(n\)种物体，每种物体具有三个属性\(v\)，\(w\)，\(c\)，分别代表其体积，价值和数量。要求在其中选出一些，满足第\(i\)种物品最多选择\(c_i\)个，体积总和\(sum_v \leq m\)，使得价值总和\(sum_w\)最大。
输入数据一般形如：
题目链接第1行输入两个数\(n\)和\(m\)
第\(2\)~\((n+1)\)行每行3个数\(v\)，\(w\)，\(c\)表示一个物体。
朴素解法
常规解法：二进制拆分
最优解：单调队列优化
动态规划的状态\(f_{i,j}\)表示前\(i\)种物体刚好放满容量为\(j\)的背包中获得的最大价值。显然可以枚举i，j，对于\(i\)的每次转移都考虑选取该类物品中的多少个。其时间复杂度为\(O(m*sum_c)\)，基本不可接受。
代码考虑到\(i\)的每次转移都只会用到上一次的状态，可以使用了滚动数组的方式进行优化。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int c[110];
LL v[110], w[110];
LL f[2][110];
int main(void) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%d", &v[i], &w[i], &c[i]);
}
// 前面都是输入不多说，
// 下面开始初始化状态
memset(f, 0, sizeof(f));
// 注意是刚好j体积
for (int i = 0; i <= c[1] && i * v[1] <= m; ++i) {
f[1][i * v[1]] = i * w[1];
}
for (int i = 2; i <= n; ++i) {
for (int j = v[i]; j <= m; ++j) {
for (int k = 0; k <= c[i] && k * v[i] <= j; ++k) {
// 这里对二取模也就是滚动数组优化
f[i % 2][j] = max(f[i % 2][j],
f[(i - 1) % 2][j - k * v[i]] + k * w[i]);
}
}
}
// 由于我们f数组是计算刚好j体积而不是小于等于，
// 所以需要再进行一遍统计
LL res = 0;
for (int i = 0; i <= m; ++i) {
res = max(res, f[n % 2][i]);
}
printf("%lld\n", res);
return 0;
}
常规解法：二进制拆分
朴素解法的瓶颈在于，对于每一种物品，都要逐一枚举选取的数量，相当于把一种物品拆分成了c个一个一个取的01背包，这让时间爆炸增长。我们能不能优化这种拆分方式呢？答案是肯定的。
考虑二进制拆分的原理，任何一个整数都可以表示为许多2的幂次之和，并且每一个不同的二的幂次只会出现一次！这不就是01背包的限制条件吗？于是，我们得到了优化的拆分方案。
对于一种物品，我们先尽量拆成1，2，4，8大小的组，最后无法分出剩下的再单独分为一组，这样保证0~\(c\)之间所有的取法都能产生。此时的物体总数是\(O(\sum^{n}_{i = 1}{\log{c}})\)，总的时间复杂度就是它再乘上m。这个时间复杂度一般可以接受。
代码第一部分是输入并用二进制分解物品：
int n, m;
scanf("%d%d", &n, &m);
vector<pair<LL, LL> > vec;
for (int i = 1; i <= n; ++i) {
LL v, w;
int c;
scanf("%lld%lld%d", &v, &w, &c);
int sum = 0;
// 注意细节：预先判断，如果加入后会超过限制就不能加入
for (int k = 1; sum + k <= c; k *= 2) {
vec.push_back(make_pair(k * v, k * w));
sum += k;
}
// 如果有剩余再将剩余单独打包成一个组
if (c - sum > 0) {
vec.push_back(make_pair((c - sum) * v, (c - sum) * w));
}
}
接下来是常规的01背包解法：
// 注意细节：这里有可能会爆掉空间或者越界访问
if (!vec.empty() && vec[0].first <= m) {
f[0][vec[0].first] = vec[0].second;
}
for (int i = 1; i < vec.size(); ++i) {
for (int j = vec[i].first; j <= m; ++j) {
// 同样的滚动数组优化
f[i % 2][j] = max(f[(i - 1) % 2][j],
f[(i - 1) % 2][j - vec[i].first] + vec[i].second);
}
}
最后统计结果，和刚才一样，完整代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[2][2010];
int main(void) {
int n, m;
scanf("%d%d", &n, &m);
vector<pair<LL, LL> > vec;
for (int i = 1; i <= n; ++i) {
LL v, w;
int c;
scanf("%lld%lld%d", &v, &w, &c);
int sum = 0;
for (int k = 1; sum + k <= c; k *= 2) {
vec.push_back(make_pair(k * v, k * w));
sum += k;
}
if (c - sum > 0) {
vec.push_back(make_pair((c - sum) * v, (c - sum) * w));
}
}
if (vec[0].first <= m) {
f[0][vec[0].first] = vec[0].second;
}
for (int i = 1; i < vec.size(); ++i) {
for (int j = vec[i].first; j <= m; ++j) {
f[i % 2][j] = max(f[(i - 1) % 2][j],
f[(i - 1) % 2][j - vec[i].first] + vec[i].second);
}
}
LL res = 0;
for (int i = 0; i <= m; ++i) {
res = max(res, f[(vec.size() - 1) % 2][i]);
}
printf("%lld\n", res);
return 0;
}
最优解：单调队列优化动态规划
正片开始！
首先考虑朴素解中的状态转移方程：
\[f_{i, j} = \max_{k = 0}^{\min\{c_i, \lfloor \frac{j}{v_i} \rfloor\}}\{f_{i - 1, j - kv_i} + kw_i\} \]对这个式子进行一下分析，可以发现以下性质：
-
在一次\(i\)转移内部，许多东西是不变的。具体地，\(c_i\), \(w_i\), \(v_i\)始终不变；\(j\)的范围不变：\(v_i\)到\(m\)。这些性质使得我们的处理方便了许多，
然而实际上没有在算法中起到决定性作用。 -
对于每一个\(j\)，它只可能是从上个\(i\)转移的\(j\)，\(j - 2v_i\)，…，\(j-kv_i\)转移而来，也就是说，所有会互相影响的\(j\)转移都模\(v_i\)同余。这就给我们一个启发：根据模\(v_i\)的余数进行分组，分成\(v_i\)组。
由性质一，我们在以后的讨论中省略\(i\)下标（对于\(\max\)符号中的\(f\)，一定是\(i-1\)，对于其它是\(i\)）。另外设\(k\)的范围\(t = \min\{c_i, \lfloor \frac{j}{v_i} \rfloor\}\)。
由性质二，我们将每一个\(j\)拆分成\(pv + q\)，其中的q就是分组的依据，在每一组内，它是一个定值。于是状态转移方程变为了：
\[f_{pv+q} = \max_{k = 0}^{t}\{f_{(p-k)v} + kw\} \]看上去好像进行不下去了呢。我们来举一个例子便于推导。假设对于所有的\(j\)，\(t\)都是2，并取\(q = 1\)。那么显然有一下式子（\(p\)太小的就不列出来了）：
\[f_{3v+1} = \max\{f_{3v+1}, f_{2v+1}+w, f_{v+1}+2w\} \]\[f_{4v+1} = \max\{f_{4v+1}, f_{3v+1}+w, f_{2v+1}+2w\} \]\[f_{5v+1} = \max\{f_{5v+1}, f_{4v+1}+w, f_{3v+1}+2w\} \]\[f_{6v+1} = \max\{f_{6v+1}, f_{5v+1}+w, f_{4v+1}+2w\} \]\[...... \]看上去好像还是不能优化呢。但我们如果忽略掉\(\max\)符号内的这些\(w\)尾巴呢？再列一次：
\[\{f_{3v+1}, f_{2v+1}, f_{v+1}\} \]\[\{f_{4v+1}, f_{3v+1}, f_{2v+1}\} \]\[\{f_{5v+1}, f_{4v+1}, f_{3v+1}\} \]\[\{f_{6v+1}, f_{5v+1}, f_{4v+1}\} \]\[...... \]这也就是单调队列所需的形式。于是我们考虑将原式中的\(w\)“尾巴”想办法处理掉，让它们也可以用单调队列来优化。考虑将\(f_{pv+1}\)这一行中的这些项都减掉\(pw\)，再在末尾加上去，就变成了：
\[f_{3v+1} = \max\{f_{3v+1}-3w, f_{2v+1}-2w, f_{v+1}-w\}+3w \]\[f_{4v+1} = \max\{f_{4v+1}-4w, f_{3v+1}-3w, f_{2v+1}-2w\}+4w \]\[f_{5v+1} = \max\{f_{5v+1}-5w, f_{4v+1}-4w, f_{3v+1}-3w\}+5w \]\[f_{6v+1} = \max\{f_{6v+1}-6w, f_{5v+1}-5w, f_{4v+1}-4w\}+6w \]\[...... \]这样的形式就可以使用单调队列来维护，这个问题得到了完美解决。
代码#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int c[1010];
LL v[1010], w[1010];
LL f[2][20010];
int main(void) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%d", &v[i], &w[i], &c[i]);
}
for (int i = 1; i <= c[1] && i * v[1] <= m; ++i) {
f[1][i * v[1]] = i * w[1];
}
for (int i = 2; i <= n; ++i) {
for (int q = 0; q < v[i]; ++q) {
deque<pair<int, LL> > que;
for (int p = 0; p * v[i] + q <= m; ++p) {
int j = p * v[i] + q, t = min(c[i], p);
while (!que.empty() &&
p - que.front().first > t) {
que.pop_front();
}
while (!que.empty() &&
que.back().second <= f[(i - 1) % 2][j] - p * w[i]) {
que.pop_back();
}
que.push_back(make_pair(p, f[(i - 1) % 2][j] - p * w[i]));
f[i % 2][j] = que.front().second + p * w[i];
}
}
}
LL res = 0;
for (int i = 0; i <= m; ++i) {
res = max(res, f[n % 2][i]);
}
printf("%lld\n", res);
return 0;
}