宝物筛选

题意

给出 n 种宝物。第 i 种宝物有：

价值 v_i
重量 w_i
数量 m_i

要求在总重量不超过 W 的前提下，使总价值最大。

思路

最直接的办法是对每种物品暴力枚举取几件。

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, capacity;
    cin >> n >> capacity;

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

    for (int i = 1; i <= n; ++i) {
        int value, weight, count;
        cin >> value >> weight >> count;

        prev_dp = dp;
        for (int j = 0; j <= capacity; ++j) {
            for (int k = 1; k <= count && k * weight <= j; ++k) {
                // 直接枚举当前物品选几件，是最朴素的多重背包写法。
                dp[j] = max(dp[j], prev_dp[j - k * weight] + k * value);
            }
        }
    }

    cout << dp[capacity] << '\n';
    return 0;
}

下面是另一种「选择序列」风格的暴力写法。它把“当前种宝物取几件”看成这一层递归的选择，先生成完整的 choose_take[]，叶子节点再检查容量并统计总价值：

另一种暴力写法：选择序列

cpp

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// brute_01_style.cpp：选择序列风格暴力，每一层决定当前种宝物取几件。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, capacity;
int value[MAXN], weight[MAXN], item_count[MAXN];
int choose_take[MAXN]; // choose_take[i] 表示第 i 种宝物取几件
int answer;

bool check() {
    int total_weight = 0;
    for (int i = 1; i <= n; i++) {
        total_weight += choose_take[i] * weight[i];
    }
    return total_weight <= capacity;
}

int calc_answer() {
    int total_value = 0;
    for (int i = 1; i <= n; i++) {
        total_value += choose_take[i] * value[i];
    }
    return total_value;
}

// dfs_choose(pos)：只负责决定第 pos 种宝物取 0..item_count[pos] 件。
void dfs_choose(int pos) {
    if (pos == n + 1) {
        if (check()) {
            int current_value = calc_answer();
            if (answer < current_value) answer = current_value;
        }
        return;
    }

    for (int take = 0; take <= item_count[pos]; take++) {
        choose_take[pos] = take;
        dfs_choose(pos + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> capacity;
    for (int i = 1; i <= n; i++) {
        cin >> value[i] >> weight[i] >> item_count[i];
    }

    answer = 0;
    dfs_choose(1);

    cout << answer << '\n';
    return 0;
}

brute.cpp 直接枚举当前物品取 0..m_i 件，写法很直白，但复杂度太高。

关键观察是：数量为 m 的物品，可以拆成若干组 1, 2, 4, ... 件的组合。这样每组都只需要考虑“选或不选”，于是多重背包就转成了 0/1 背包。

拆分表

这张表展示如果某种物品有 13 件，可以怎样拆：

组编号	件数
1	1
2	2
3	4
4	6

这些组的件数和是 13，并且可以拼出 0..13 之间任意一个数量。所以对原物品的所有合法选择，都能改写成“若干组的选或不选”。这正是 0/1 背包的形式。

于是做法就很自然：

把每种物品的数量做二进制拆分
每一组形成一个新的 0/1 物品
对所有新物品做一维 0/1 背包

DP 公式

把数量为 $m_i$ 的物品二进制拆分成若干组。若某一组包含 $c$ 件原物品，则形成一个 0/1 物品：

weight=c\cdot w_i,\quad value=c\cdot v_i

对所有拆出的物品做 0/1 背包。设 $dp_j$ 表示容量不超过 $j$ 时的最大价值，则：

dp_j=\max(dp_j,\ dp_{j-weight}+value)

容量倒序枚举，最终答案为：

dp_W

公式解释：二进制拆分保证 0..m_i 的任意件数都能由若干组拼出来。拆完后每组只能选或不选，于是多重背包变成普通 0/1 背包。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

struct Item {
    int value;
    int weight;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, capacity;
    cin >> n >> capacity;

    vector<Item> items;
    items.reserve(2000);

    for (int i = 1; i <= n; ++i) {
        int value, weight, count;
        cin >> value >> weight >> count;

        // 把 count 件物品拆成 1,2,4,... 的若干组，转成 0/1 背包。
        for (int k = 1; k <= count; k <<= 1) {
            items.push_back({value * k, weight * k});
            count -= k;
        }
        if (count > 0) {
            items.push_back({value * count, weight * count});
        }
    }

    vector<int> dp(capacity + 1, 0);
    for (const auto &item : items) {
        for (int j = capacity; j >= item.weight; --j) {
            dp[j] = max(dp[j], dp[j - item.weight] + item.value);
        }
    }

    cout << dp[capacity] << '\n';
    return 0;
}

复杂度

设拆分后的新物品总数为 M，则总时间复杂度是 $O(W * M)$ ，空间复杂度是 $O(W + M)$ 。

总结

这题的关键不是背包状态本身，而是把“每种物品最多选 m_i 件”的限制高效压缩掉。二进制拆分是多重背包里最常用、也最稳的做法。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

拆分表

DP 公式

代码

复杂度

总结

一图流解析