$dp[i][j]$ 表示将前 $i$ 种物品放入容量为 $j$ 的背包中所得到的最大价值
$dp[i][j]$ = $max($不放入物品 $i$,放入1个物品 $i$,放入2个物品 $i$, … , 放入 $k$ 个物品 i$)$
这里 $k$ 要满足:$k <= s, j - kv >= 0$
不放物品 i = $dp[i-1][j]$
放k个物品 i = $dp[i-1][j - kv] + kw$
$dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2v] + 2*w,…, dp[i-1][j-kv] + kw)$
实际上我们并不需要二维的dp数组,适当的调整循环条件,我们可以重复利用dp数组来保存上一轮的信息
我们令 $dp[j]$ 表示容量为 $j$ 的情况下,获得的最大价值
那么,针对每一类物品 $i$ ,我们都更新一下 $dp[m] –> dp[0]$ 的值,最后 $dp[m]$ 就是一个全局最优值
$dp[m] = max(dp[m], dp[m-v] + w, dp[m-2v] + 2*w, dp[m-3v] + 3w, …)$
接下来,我们把 $dp[0] –> dp[m]$ 写成下面这种形式
$dp[0], dp[v], dp[2v], dp[3v], … , dp[kv]$
$dp[1], dp[v+1], dp[2v+1], dp[3v+1], … , dp[kv+1]$
$dp[2], dp[v+2], dp[2v+2], dp[3v+2], … , dp[kv+2]$
…
$dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j]$
$显而易见,m 一定等于 kv + j,其中 0 \le j < v$
所以,我们可以把 dp 数组分成 $v$ 个类,每一类中的值,都是在同类之间转换得到的
也就是说,$dp[kv+j] 只依赖于 { dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j] }$
因为我们需要的是 ${ dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j] }$ 中的最大值,
可以通过维护一个单调队列来得到结果。这样的话,问题就变成了 $j$ 个单调队列的问题
所以,我们可以得到
$dp[j] = dp[j]$
$dp[j+v] = max(dp[j] + w, dp[j+v])$
$dp[j+2v] = max(dp[j] + 2w, dp[j+v] + w, dp[j+2v])$
$dp[j+3v] = max(dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])$
…
但是,这个队列中前面的数,每次都会增加一个 $w$ ,所以我们需要做一些转换
$dp[j] = dp[j]$
$dp[j+v] = max(dp[j], dp[j+v] - w) + w$
$dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w$
$dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w$
…
这样,每次入队的值是 $dp[j+kv] - kw$
原题解是这么写的,但是经过评论提醒,我发现似乎代码中的入队值是 $dp[j+kv]$。
单调队列问题,最重要的两点
1)维护队列元素的个数,如果不能继续入队,弹出队头元素
2)维护队列的单调性,即:尾值 $\ge dp[j + kv] - kw$
本题中,队列中元素的个数应该为 $s+1$ 个,即 $0 - s$ 个物品 $i$
dalao的code:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int dp[N], pre[N], q[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
memcpy(pre, dp, sizeof(dp));
int v, w, s;
cin >> v >> w >> s;
for (int j = 0; j < v; ++j) {//维护v个单调队列,%v=j的体积类
int head = 0, tail = -1;
for (int k = j; k <= m; k += v) {//枚举每个j+kv 注意代码中的k实际上=解释中的j+kv
if (head <= tail && k - s*v > q[head])
++head;//太小了,q[head]不可能转移到k
while (head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w)
--tail;
if (head <= tail) dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);
q[++tail] = k;
}
}
}
cout << dp[m] << endl;
return 0;
}
你好,请问转换的时候减掉的那个kw为什么在代码中不用加回来呢
似乎代码中的入队值实际上就是 dp[j+kv] 本身,我只是重新排版了原题解,所以没有发现这个问题
复杂度 $O(NV$