Luogu-P1776 宝物筛选

题意

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$，重量为 $w_i$，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

对于 $100%$ 的数据，$n\leq \sum m_i \leq 10^5$，$0\le W\leq 4\times 10^4$，$1\leq n\le 100$。

解法 1：二进制优化

每一个数都可以表示成 $2$ 的幂的和（因为每一个数都可以用二进制表示）。

时间复杂度：$O(nW\sum \log m_i)$

 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

#include <bits/stdc++.h>
using namespace std;
int dp[40005];
int main()
{
	int n, W;
	scanf("%d%d", &n, &W);
	for (int i = 0; i < n; i++) {
		int t, c, p;
		scanf("%d%d%d", &c, &t, &p);
		int tmp = 1;
		while (p >= tmp) {
			p -= tmp;
			for (int j = W; j >= t*tmp; j--)
				dp[j] = max(dp[j], dp[j-t*tmp]+c*tmp);
			tmp *= 2;
		}
		if (p == 0) continue;
		for (int j = W; j >= t*p; j--) {
			dp[j] = max(dp[j], dp[j-t*p]+c*p);
		}
	}
	printf("%d\n", dp[W]);
	return 0;
}

解法 2：单调队列优化

设 $f[i][j]$ 表示前 $i$ 种物品重量不超过 $j$ 的最大价值。显然有一个状态转移方程：

$$ f[i][j] = max_{0<=k<=m[i]}{f[i-1][j-k\times w[i]]+k\times v[i]} $$

我们设 $j=k_1*w[i]+d$：

$$ f[i][j]=max{f[i-1][(k_1-k)\times w[i]+d]-(k_1-k)\times v[i] }+ k_1\times v[i] $$

我们枚举余数 $d$ 和 $k_1$，就可以表示出每一个数，然后维护一个单调队列，这个队列里面的决策通过加上第 $i$ 种物品都可以凑成 $j$，因此增加的数量不能超过 $m[i]$，也就是 $k_1-k <= m[i]$。

时间复杂度：$O(nW)$

RECORD

 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

#include <bits/stdc++.h>
using namespace std;
int n, W;
int v[105], w[105], m[105];
int dp[105][40004];
struct deq {
	int head, tail;
	int arr[40004];
	bool empty() { return head+1 == tail; }
	void pop_front() { head++; }
	void pop_back() { tail--; }
	void push_back(int x) { arr[tail] = x; tail++; }
	void clear() { head = 0; tail = 1; }
	int front() { return arr[head+1]; }
	int back() { return arr[tail-1]; }
} dq;
int main()
{
	cin >> n >> W;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i] >> m[i];
		if (w[i] == 0) {
			ans += v[i]*m[i];
			continue;
		}
		for (int j = 0; j < w[i]; j++) { // 余数 
			dq.clear();
			// k 实际上表示的是文中的 k_1
			for (int k = 0; j+k*w[i] <= W; k++) {
				// dq.front() 实际上表示的是文中的 k_1 - k
				while (!dq.empty() && k-dq.front() > m[i]) dq.pop_front();
				while (!dq.empty() && dp[i-1][j+dq.back()*w[i]]+(k-dq.back())*v[i] <= dp[i-1][j+k*w[i]]) dq.pop_back();
				dq.push_back(k);
				if (!dq.empty()) dp[i][j+k*w[i]] = max(dp[i][j+k*w[i]], dp[i-1][j+dq.front()*w[i]]+(k-dq.front())*v[i]);
			}
		}
	}
	cout << dp[n][W]+ans << endl;
	return 0;
}