算法动态规划

单调队列优化多重背包

字数统计: 804字   |   阅读时长: 3分

$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