单调队列优化多重背包

  |  

$0 6. 多重背包问题 III

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。

1
2
0<N<=1000
0<V<=20000

$1 多重背包朴素做法

考虑 01 背包的转移中 max 中的两项的对应关系

  • dp[j] : 对应不选 v[i]
  • dp[j - v[i]] + w[i] : 对应选 v[i]

01 背包每个物品的两种情况:选和不选

而多重背包的物品还有以下这些二外的情况:选 2 个,选 3 个,… 选 s[i] 个,因此朴素的多重背包的转移方程就是在 01 背包的转移方程中的 max 中把额外的情况加上,如下

1
2
3
4
5
6
7
8
dp[j] = max(
dp[j],
dp[j - v[i - 1]] + w[i],
dp[j - 2 * v[i - 1]] + 2 * w[i],
dp[j - 3 * v[i - 1]] + 3 * w[i],
...
dp[j - s[i] * v[i - 1]] + s[i] * w[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 <vector>
#include <iostream>

using namespace std;

int main()
{
int N;
int V;
cin >> N >> V;
vector<int> v(N, 0);
vector<int> w(N, 0);
vector<int> s(N, 0);
for(int i = 0; i < N; ++i)
cin >> v[i] >> w[i] >> s[i];

vector<int> dp(V + 1, 0);
for(int i = 1; i <= N; ++i)
for(int j = V; j >= v[i - 1]; --j)
for(int k = 0; k <= s[i - 1] && k * v[i - 1] <= j; ++k)
dp[j] = max(dp[j], dp[j - k * v[i - 1]] + k * w[i - 1]);

cout << dp[V] << endl;
return 0;
}

$2 将物品按体积模V的同余类分解

将状态按模 v[i] 的同余类分解:模 v[i] 余 0 的归一类,模 v[i] 余 1 的归一类,…,模 v[i]v[i]-1 的归一类。这样就将0 <= j <= V 分为了 v[i] 类。

计算 i 阶段的状态 dp[j] 时,dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]),即状态只会在同一个同余类中转移。

因此可以将倒序枚举体积 j = V,...,v[i] 改为枚举余数 q = 0,1,...,v[i],再倒序枚举 p = (V - q) / v[i], ..., 0,对应的状态为 j = q + p * v[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
26
27
28
29
30
#include <vector>
#include <iostream>

using namespace std;

int main()
{
int N;
int V;
cin >> N >> V;
vector<int> v(N, 0);
vector<int> w(N, 0);
vector<int> s(N, 0);
for(int i = 0; i < N; ++i)
cin >> v[i] >> w[i] >> s[i];

vector<int> dp(V + 1, 0);
for(int i = 1; i <= N; ++i)
for(int q = 0; q < v[i - 1]; ++q)
for(int p = (V - q) / v[i - 1]; p >= 0; --p)
{
int j = q + p * v[i - 1];
for(int k = 0; k <= s[i - 1] && k * v[i - 1] <= j; ++k)
dp[j] = max(dp[j], dp[j - k * v[i - 1]] + k * w[i - 1]);
}


cout << dp[V] << endl;
return 0;
}

$3 单调队列

单调队列优化 DP 的状态转移方程的形式如下:

参考:

将倒序枚举体积 j = V,...,v[i] 改为枚举余数 q = 0,1,...,v[i],再倒序枚举 p = (V - q) / v[i], ..., 0,对应的状态为 j = q + p * v[i] 后,新的状态转移方程为

1
2
dp[q + p * v[i]] = max(dp[q + k * v[i]] + (p - k) * w[i])
其中 p - s[i] <= k <= p - 1

对应的状态计算过程如下:

1
2
3
4
5
6
7
8
for(int i = 1; i <= N; ++i)
for(int q = 0; q < v[i - 1]; ++q)
for(int p = (V - q) / v[i - 1]; p >= 0; --p)
{
int j = q + p * v[i - 1];
for(int k = 0; k <= s[i - 1] && k * v[i - 1] <= j; ++k)
dp[j] = max(dp[j], dp[j - k * v[i - 1]] + k * w[i - 1]);
}

当把 i 和 q 视为定值时,转移方程属于单调队列优化 DP 的形式即

其中 f(k, p) 可以分为仅与 k 相关和仅与 p 相关的两部分。

代码1

注 $O(NV)$ 卡常超时。

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
#include <vector>
#include <iostream>
#include <deque>

using namespace std;

int main()
{
int N;
int V;
cin >> N >> V;
vector<int> v(N, 0);
vector<int> w(N, 0);
vector<int> s(N, 0);
for(int i = 0; i < N; ++i)
cin >> v[i] >> w[i] >> s[i];

vector<int> dp(V + 1, 0);
deque<int> deq;

for(int i = 1; i <= N; ++i)
{
int vv = v[i - 1];
int ss = s[i - 1];
int ww = w[i - 1];
for(int q = 0; q < vv; ++q) // 枚举余数
{
// 建立单调队列
deq.clear();
// 将初始候选集合(p = maxp 时)插入队列
int maxp = (V - q) / vv;
for(int k = maxp - 1; k >= max(maxp - ss, 0); --k)
{
while(!deq.empty() && dp[q + deq.back() * vv] - deq.back() * ww <= dp[q + k * vv] - k * ww)
deq.pop_back();
deq.push_back(k);
}
// 倒序枚举状态
for(int p = maxp; p >= 0; --p)
{
// 排除过时决策
while(!deq.empty() && deq.front() > p - 1)
deq.pop_front();

// 取队头进行状态转移
if(!deq.empty())
dp[q + p * vv] = max(dp[q + p * vv], dp[q + deq.front() * vv] - deq.front() * ww + p * ww);

// 插入新决策,同时维护单调性
if(p - ss - 1 >= 0)
{
while(!deq.empty() && dp[q + deq.back() * vv] - deq.back() * ww <= dp[q + (p - ss - 1) * vv] - (p - ss - 1) * ww)
deq.pop_back();
deq.push_back(p - ss - 1);
}
}
}
}

cout << dp[V] << endl;
return 0;
}

代码2

vector 模拟 deq,一次性开出长度为 V + 1 的队列空间。初始化和队列操作仅用 l, r 两个变量维护即可。

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
#include <vector>
#include <iostream>

using namespace std;

int main()
{
int N;
int V;
cin >> N >> V;
vector<int> v(N, 0);
vector<int> w(N, 0);
vector<int> s(N, 0);
for(int i = 0; i < N; ++i)
cin >> v[i] >> w[i] >> s[i];

vector<int> dp(V + 1, 0);
vector<int> deq(V + 1);

for(int i = 1; i <= N; ++i)
{
int vv = v[i - 1];
int ss = s[i - 1];
int ww = w[i - 1];
for(int q = 0; q < vv; ++q) // 枚举余数
{
// 建立单调队列
int l = 0, r = -1;
// 将初始候选集合(p = maxp 时)插入队列
int maxp = (V - q) / vv;
for(int k = maxp - 1; k >= max(maxp - ss, 0); --k)
{
while(l <= r && dp[q + deq[r] * vv] - deq[r] * ww <= dp[q + k * vv] - k * ww)
--r;
deq[++r] = k;
}
// 倒序枚举状态
for(int p = maxp; p >= 0; --p)
{
// 排除过时决策
while(l <= r && deq[l] > p - 1)
++l;

// 取队头进行状态转移
if(l <= r)
dp[q + p * vv] = max(dp[q + p * vv], dp[q + deq[l] * vv] - deq[l] * ww + p * ww);

// 插入新决策,同时维护单调性
if(p - ss - 1 >= 0)
{
while(l <= r && dp[q + deq[r] * vv] - deq[r] * ww <= dp[q + (p - ss - 1) * vv] - (p - ss - 1) * ww)
--r;
deq[++r] = p - ss - 1;
}
}
}
}

cout << dp[V] << endl;
return 0;
}

$4 题目

281. 硬币

问题

给定N种硬币,其中第 i 种硬币的面值为Ai,共有Ci个。

从中选出若干个硬币,把面值相加,若结果为S,则称“面值S能被拼成”。

求1~M之间能被拼成的面值有多少个。

分析

  • 多重背包
  • 取到特定体积
  • 组合问题:求可行性

Share