算法动态规划

单调队列优化多重背包

字数统计: 1k字   |   阅读时长: 4分
, ,

摘要: 单调队列优化DP 应用在多重背包问题上

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在 多重背包及其二进制划分优化 中我们了解了多重背包问题，以及使用二进制划分的思想来减少状态个数的做法，并给出了代码模板。本文我们进一步看一下，用单调队列优化 DP 的方式来优化状态转移的过程。

$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]
        )

参考：

代码 (C++)

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]。

参考：同余类状态。

代码 (C++)

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

单调队列优化 DP 擅长解决的状态转移方程的形式如下：

其中 $f(i, j) = g1(i) + g2(j)$。

于是在求 $dp[i]$ 时，要问：$i$ 左侧的区间范围 $L(i)<=j<=R[i]$ 的窗口中，$dp[j] + g2(j)$ 的最大值是多少。这一问是滑动窗口最值问题，可以用单调队列解决。

参考文章：

将倒序枚举体积 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
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 (C++)

注 $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 (模板 C++)

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 题目

这是一个多重背包的应用题，很难，这里暂时不解决。大致看一下问题和分析思路。

问题

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

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

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

分析

  • 这是个多重背包问题，每种硬币都有有限个。
  • 这是个要求取到特定体积的问题，价值不重要，可以都视为 1。
  • 这是个组合问题，并且关注的是存在性。
Share