题解 | 宝物筛选

题干解析

题设给予宝石总数(n)，背包空间大小（C）与每种宝石的价值(w)，每个宝石所占空间大小(c)与数量(m)，要求我们选择一种存储方式，使在不超过背包空间的前提下获得最大价值。

算法思路

多重背包问题。首先我们我们可以延续0/1背包的思路，将所有单个宝石看作一种宝石转化为0/1背包，这样做只需在原有的两层循环嵌入一层k从的循环即可。

但注意以上方案时间复杂度预计为最坏情况下n=100, 所有，总计进行数量级以上的计算，会超时，需要优化

一种简单的优化方向是进行二进制拆分后再转化为0/1背包。

假设某个宝石，我们不妨将25拆成集合，自行尝试一下，这五个数的任意组合的和能够覆盖0~25所有的情况。这便是二进制拆分，通过此技巧能够使时间复杂度降至，计算数量级下降至左右，不会超时。

实现代码

#include <bits/stdc++.h>
using namespace std;

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

    int n, C;
    cin >> n >> C;
    vector<int> w(n + 1), c(n + 1), m(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> c[i] >> m[i];
    }
	// 二进制拆分优化
    int new_n = 0;
    vector<int> new_w(100010), new_c(100010), new_m(100010); // 开大一点，防越界
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m[i]; j <<= 1) {
            m[i] -= j;
            ++new_n;
            new_c[new_n] = j * c[i];
            new_w[new_n] = j * w[i];
        }
        if (m[i]) {
            ++new_n;
            new_c[new_n] = m[i] * c[i];
            new_w[new_n] = m[i] * w[i];
        }
    }
	// 0/1背包
    vector<int> dp(C + 1, 0);
    for (int i = 1; i <= new_n; ++i) {
        for (int j = C; j >= new_c[i]; --j) {
            dp[j] = max(dp[j], dp[j - new_c[i]] + new_w[i]);
        }
    }
    cout << dp[C] << '\n';
    return 0;
}//*/

复杂度分析

• 时间复杂度：依据此前分析，为
• 空间复杂度：数组空间开销理论上