多重背包O(VN)算法——单调队列优化

多重背包O(VN)算法——单调队列优化

多重背包问题：

有N种物品和容量为V的背包，若第i种物品容量为v[i],价值为w[i],总共有n[i]件，怎样装才能使背包内的物品总价值最大？

设dp[i][j]表示对容量为j的背包，处理完前i种物品后，背包内的物品可达到的最大总价值，并设m[i] = min(n[i]. j / v[i])。

放入背包的第i种物品的数目可以是0、1、2......，可得：

dp[i][j] = max{dp[i-1][j-k*v[i]] + k*w[i]} (0 <= k <= m[i])

如何在O(1)时间内求出dp[i][j]呢？

我们先假设所有物品都只有两件，背包容量足够大，并假设dp[i][j] = dp(j) (固定i，只看j的影响), v = v[i], w = w[i];

则：

j = 6*v时， 我们需要求dp(6*v),dp(5*v)+w,dp(4*v) + 2*w这三项中的最大值；

j = 5*v时， 我们需要求dp(5*v),dp(4*v)+w,dp(3*v) + 2*w这三项中的最大值；

j = 4*v时， 我们需要求dp(4*v),dp(3*v)+w,dp(2*v) + 2*w这三项中的最大值；

稍作变形：

j = 6*v时 每项都减去6*w;

j = 5*v时 每项都减去5*w;

j = 4*v时 每项都减去4*w;

则：

j = 6*v时， 我们需要求dp(6*v) - 6*w,dp(5*v)-5*w,dp(4*v) - 4*w这三项中的最大值；

j = 5*v时， 我们需要求dp(6*v) - 5*w,dp(5*v)-4*w,dp(4*v) - 3*w这三项中的最大值；

j = 4*v时， 我们需要求dp(6*v) - 4*w,dp(5*v)-3*w,dp(4*v) - 2*w这三项中的最大值；

此时我们会发现求解最大项的过程中会有很多重复

因此可以将递推公式做一些调整：

设a = j/v[i], b = j % v[i], 既j = a * v[i] + b,将此式带入原递推方程得：

dp[i][j] = max{dp[i-1][b + (a - k)*v[i]] + k*w[i]} (0 <= k <= m[i])

用t替换(a-k)得：

dp[i][j] = max{dp[i-1][b + t*v[i]] + (a-t)*w[i]} (a - m[i] <= t <= a)

化简一下：dp[i][j] = max{dp[i-1][b + t*v[i]] -t*w[i]}  + a*w[i](a - m[i] <= t <= a)

因此，dp[i][j]就是求j的前面m[i] + 1个数对应的dp[i - 1][b + t * v[i]] - t*w[i]的最大值，加上a*w[i].

如果将dp[i][j]前面所有的dp[i - 1][b + t*v[i]] - t*w[i]放入一个队列，原问题可以转化为：

在O(1)时间内求一个队列的最大值。

这时就可以使用单调队列了，模板如下

const int maxn = 110;const int maxv = 100000 + 10;int N, V, n[maxn], v[maxn], w[maxn];int dp[maxv], q1[maxv], q2[maxv];//q1存储状态，q2是单调队列void bag01(int w, int v) { for (int i = V; i >= v; i--) { dp[i] = max(dp[i], dp[i - v] + w); }}void completebag(int w, int v) { for (int i = v; i <= V; i++) { dp[i] = max(dp[i], dp[i - v] + w); }}void multiplybag(int w, int v, int n) { if (n == 0 || v == 0) return; //数量或价值为0都没有意义，直接忽略 if (n == 1) bag01(w, v); else if (n * v >= V) completebag(w, v); else { for (int i = 0; i < v; i++) { int head1 = 0, tail1 = -1, head2 = 0, tail2 = -1;//注意队列是闭区间 int cnt = 0; for (int j = i; j <= V; j += v) { if (tail1 == head1 + n) {//若队列1大小达到指定值，则第一个元素出队 if (q1[head1] == q2[head2]) ++head2;//若q2的第一个元素等于q1出队的元素，则该元素也出队 ++head1; } int temp = dp[j] - cnt * w; q1[++tail1] = temp; while (tail2 >= head2 && q2[tail2] < temp) --tail2;//删除辅助队列q2所有小于temp的元素，使q2单调递减 q2[++tail2] = temp; dp[j] = q2[head2] + cnt * w;//q2队首元素为q1所有状态的最大值 cnt++; } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。