poj 1014 Dividing 多重背包之单调队列优化

缘起

【1】讲了 poj 1014 Dividing 的二进制优化解法（并且从论述中我们看得出是极为自然的一种解法，而且巨好写）. 而【2】讲述了单调队列这一数据结构——一种高效处理窗口极值的数据结构. 那么怎么使用单调队列来优化多重背包问题呢?

分析

题目见【1】.

单调队列优化本质上就是将原本的dp变个形,然后转换为窗口最值问题(例如长度<=M的最大子区间).就能用单调队列优化了(体现在O(n)复杂度降为O(1)). 所以其实单调队列并不是专门优化多重背包的.

核心思想如下

1
2
3
4
5
6
7
8
本题的模型是
dp[i][j]=max{dp[i-1][j-k*i],0<=k<=n[i]},dp[i][j](6>=i>=1,0<=j<=sum)表示只考虑物品
1,...,i的取用,价值j可不可能到达
则令j=q*i+r(即做一个带余除法),则dp[i][j]=max{dp[i-1][(q-k)*i+r],0<=k<=n[i]}
则再做一个变形令kk=q-k,则dp[i][j]=max{dp[i-1][kk*i+r],q-n[i]<=kk<=q},q是j(=i*q+r)除以i的
商,r是余数(需要枚举),则转换为窗口最大问题(所以说,单调队列并非只能优化多重背包)
则就能用单调队列O(1)求出max的值,也就是说,对于物品i的处理(确切讲是对于容量j的处理)是分层的(余数相同的
为一层),则算法复杂度是O(nv)的

所以，单调队列优化多重背包其实是要处理很多边界而且远没有二进制优化（【1】）好写. 一般题目不会卡二进制优化（除了变态的楼教主的男人八题——poj 1742）

所以遇到多重背包问题一般用二进制优化水之.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 60005;
int n[7],sum, dp[maxn],q[maxn],front,rear,t[maxn];

void cp(int c)
{
	for (int i = c; i<=sum; i++)
	{
		dp[i] = max(dp[i],dp[i-c]);
	}
}

void mp(int c, int m)
{
	if (c*m>=sum)
	{
		cp(c);
	}
	else // 单调队列优化,而不是二进制优化
	{
		for (int r = 0,y; r<c; r++) // 枚举余数,对于每个余数都使用单调队列优化
		{
			y = 0;
			for (int x=r;x<=sum; x+=c, y++) t[y] = dp[x]; // 将dp[kk*c+r]（kk=0,1,2...）复制到t中来
			front = rear = 0; // 清空队列, 求t的窗口极大值来得到dp的值
			for (int yy = 0; yy<y; yy++)
			{
				while(front!=rear && t[q[rear-1]]<t[yy]) rear--;
				q[rear++] = yy;
				dp[yy*c+r] = t[q[front]]; // 还原到dp上去
				if (yy-q[front]>=m) front++; // 这里,窗口的宽度是m+1
			}
		}
	}
} // O(V) 算法,这里V=sum即背包容量

bool sz()
{
	if (sum&1)
	{
		return false;
	}
	sum>>=1;
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	for (int i = 1; i<=6;i++) // 遍历各个物品进行多重背包
	{
		mp(i, n[i]);
	}
	return dp[sum];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 1;
	while(scanf("%d%d%d%d%d%d", n+1,n+2,n+3,n+4,n+5,n+6), n[1]||n[2]||n[3]||n[4]||n[5]||n[6])
	{
		sum = n[1]+2*n[2]+3*n[3]+4*n[4]+5*n[5]+6*n[6];
		if (kase>1) puts("");
		printf("Collection #%d:\n", kase++);
		sz()? puts("Can be divided."):puts("Can't be divided.");
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 792kB
Length 1386
Lang C++
Submitted 2019-08-28 22:46:03
Shared
RemoteRunId 20813952

参考

【1】https://yfsyfs.github.io/2019/08/28/poj-1014-Dividing-%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E4%B9%8B%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%BC%98%E5%8C%96/

【2】https://yfsyfs.github.io/2019/08/28/poj-2823-Sliding-Window-%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97/