算法动态规划

多重背包及其二进制划分优化

字数统计: 1.3k字   |   阅读时长: 6分
, ,

摘要: 多重背包

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

$0 多重背包问题描述

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

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

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

输出最大价值。

$1 多重背包朴素解法

状态设计

从 01 背包入手

参考：基础背包。

01背包的状态：

1
dp[j] = 总体积为 j 时，最大价值

01 背包的转移方程：

1
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) // j 从大往小推
1
2
3
for(int i = 0; i < N; ++i)
    for(int j = S; j >= v[i]; --j)
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

向多重背包进化

考虑 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]
        )

这种做法等效于把物品拆开，按照 01 背包做。

模板题: 4. 多重背包问题 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 多重背包二进制划分优化

二进制划分

事实1：$2^{0}, 2^{1}, …, 2^{k-1}$，这 k 个 2 的幂次，可以表示出 $0 ~ 2^{k-1}$ 中的任何数。

事实2：任意一个数 n，它一定可以用 1,2,4,8,…$2^{k}$, 以及 $2^{k}$ 到 $2^{k+1}$ 之间的某个数表示。 例如 13 以内的所有数都可以用 1,2,4,6 表示。

总结：

给定数 S，$t = \lceil \log_{2}S\rceil - 1$，用 $0, 1, 2, 4, …, 2^{t}, S-2^{t}$ 可以拼出所有 $0 ~ S$ 的数，同时任何不在这个范围的数都拼不出来。

用同样的思路分析多重背包：

将数量为 s[i] 的物品 i，拆分成若干物品，其体积和价值分别为： ($w_{i}$, $v_{i}$), ($2w_{i}$, $2v_{i}$), …

然后对这些物品做 01 背包。这样 01 背包的物品数就比思路 1 少很多了。这可以理解为类似于倍增法的思想。

$p = \lceil \log_{2}(s[i]) \rceil - 1$，当 s[i] == 2^{p+1} - 1 时，这样划分已经可以了，$2^{0}, 2^{1}, …, 2^{p}$ 这 p + 1 个数，刚好能表示 $0 ~ 2^{p+1}-1$，同时更大的数表示不了。

对于 $2^{p} < s[i] < 2^{p+1}$ 的情况，记差值 $d = s[i] - (2^{p} - 1)$，把这个物品 $d \times v[i], d \times w[i]$ 这个物品也加上。

这样拆分出的物品可以组合出 $0~s[i]$ 的所有情况，同时大于 s[i] 的情况无法组合出来。

  • 拆分物品的的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i = 0; i < N; ++i)
{
    int ss = s[i];
    ss -= 1; // 物品 (v[i], w[i]) 已经在里面
    for(int k = 2; k <= ss; k *= 2)
    {
        ss -= k;
        v.push_back(v[i] * k);
        w.push_back(w[i] * k);
    }
    if(ss > 0)
    {
        v.push_back(v[i] * ss);
        w.push_back(w[i] * ss);
    }
}

模板题: 5. 多重背包问题 II

代码模板 (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
31
32
33
34
35
36
37
38
39
40
41
42
43
#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];

    for(int i = 0; i < N; ++i)
    {
        int ss = s[i];
        ss -= 1; // 物品 (v[i], w[i]) 已经在里面
        for(int k = 2; k <= ss; k *= 2)
        {
            ss -= k;
            v.push_back(v[i] * k);
            w.push_back(w[i] * k);
        }
        if(ss > 0)
        {
            v.push_back(v[i] * ss);
            w.push_back(w[i] * ss);
        }
    }

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

    N = v.size();
    for(int i = 1; i <= N; ++i)
        for(int j = V; j >= v[i - 1]; --j)
            dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);

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