购买 Steam 上的游戏

题目描述

Steam 上有许多游戏和 DLC(游戏拓展内容)。每个游戏和 DLC 都有其价格和耐玩值，购买 DLC 必须先购买对应的游戏主体, 购买游戏主体则不一定要买其 DLC, 每个游戏可以有多个 DLC。

给定一个游戏 DLC 清单和一个预算，你可以从清单上选择购买游戏和 DLC，每种只能买一份, 请你设计一个算法，求出在不超预算的情况下能获取的最大化耐玩值。

输入描述

一个整数 M (1 ≤ m ≤ 10^4)，表示你可用的预算。

vector<int> prices：一个整数数组，表示游戏或 DLC 的价格, 1 ≤ prices[i] ≤ 10^3。
vector<int> values：一个整数数组，表示游戏或 DCL 的耐玩值, 1 ≤ values[i] ≤ 100。
vector<int> indices：一个整数数组，表示游戏或 DLC 对应的编号，游戏本体的编号为 -1, DLC 的编号为其游戏本体在数组中的序号。

输出描述

输出一个整数，表示在不超过预算 M 元的前提下，能获取的最大耐玩值。

思路

有依赖的背包问题，转成分组背包问题，见方法一
方法一里涉及对 DLC 的组合枚举，若 DLC 数量较多，二进制枚举会爆炸。更优的解法有：
1. 0-1 背包 + 分组背包合并（见方法二）每个主件及其 DLC 作为一组，主件必须买，DLC 可选。组内用 0-1 背包求出“买主件 + 任意 DLC 组合”的所有可达（价格，价值）对，然后用分组背包合并到总 dp。

代码

方法一: 分组背包

时间复杂度分析: $O (M \sum (2^{d}))$ 其中 $d$ 是每个游戏主体的 DLC 数量， $M$ 是预算。

int steamGames_dp(const vector<int>& prices, const vector<int>& values, const vector<int>& indices, int M) {
    int N = prices.size();
    unordered_map<int, vector<int>> dlc_id_map;
    for (int i = 0; i < N; ++i) {
        if (indices[i] != -1) {
            dlc_id_map[indices[i]].emplace_back(i);
        }
    }
    vector<int> dp(M + 1, 0); // 枚举每个金额下能买到的最大耐玩值
    for (int i = 0; i < N; ++i) {
        // 跳过非游戏主体的物品，游戏DLC放在其主体那轮循环一起讨论
        if (indices[i] != -1) {
            continue;
        }
        // 对 DLC 按价格从低到高排序，便于后续提前中断枚举
        auto& dlc_ids = dlc_id_map[i];
        int dlc_cnt = dlc_ids.size();
        sort(dlc_ids.begin(), dlc_ids.end(), [&](int l, int r) { return prices[l] < prices[r]; });
 
        for (int j = M; j >= prices[i]; --j) {
            // 枚举DLC的所有选购组合，可以用二进制枚举，也可以dfs递归枚举
            // 二进制枚举直观简单，但性能可能不如递归
            for (uint32_t mask = 0; mask < (1u << dlc_cnt); ++mask) {
                int sum_price = prices[i], sum_value = values[i]; // 捆绑购买主体
                for (int d = 0; d < dlc_cnt; ++d) {
                    if (mask & (1 << d)) {
                        sum_price += prices[dlc_ids[d]];
                        sum_value += values[dlc_ids[d]];
                    }
                }
                if (sum_price <= j) {
                    dp[j] = max(dp[j], dp[j - sum_price] + sum_value);
                } else {
                    break; // 游戏及DLC总价超过当前预算，中断枚举
                }
            }
        }
    }
    return dp[M];
}

方法二: 0-1 背包 + 分组背包

时间复杂度分析
- 所有物品都经历一次 0-1 背包 → O(NM)
- 每组游戏及其 DLC 的小背包合并到总背包 → $O (n * M^{2})$ , 其中 $n$ 是游戏主体的数量， $M$ 是预算。

// 分组背包+组内0-1背包优化版 SC: O(MN+n*M^2)
int steamGames_grouped_dp(const vector<int>& prices, const vector<int>& values, const vector<int>& indices, int M) {
    int N = prices.size();
    unordered_map<int, vector<int>> dlc_id_map;
    for (int i = 0; i < N; ++i) {
        if (indices[i] != -1) {
            dlc_id_map[indices[i]].emplace_back(i);
        }
    }
    vector<int> dp(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        if (indices[i] != -1) {
            continue; // 只处理主件
        }
        // 组内0-1背包：主件必须买，DLC可选
        vector<pair<int, int>> group_items; // (price, value)
        group_items.emplace_back(prices[i], values[i]);
        for (int k : dlc_id_map[i]) {
            group_items.emplace_back(prices[k], values[k]);
        }
        int group_size = group_items.size();
        // 组内dp，f[x]=主件+部分DLC总价为x时的最大耐玩值
        vector<int> f(M + 1, -1);
        f[group_items[0].first] = group_items[0].second; // 必须买主件
        for (int j = 1; j < group_size; ++j) {
            int p = group_items[j].first, v = group_items[j].second;
            for (int b = M; b >= p; --b) {
                if (f[b - p] != -1) {
                    f[b] = max(f[b], f[b - p] + v);
                }
            }
        }
        // 分组背包合并
        for (int j = M; j >= prices[i]; --j) {
            for (int k = prices[i]; k <= j; ++k) {
                if (f[k] != -1) {
                    dp[j] = max(dp[j], dp[j - k] + f[k]);
                }
            }
        }
    }
    return dp[M];
}

所有方法结果对比

Steam Games Problem
M: 200
Prices: [100, 23, 59, 69, 30, 40]
Values: [4, 3, 5, 2, 6, 7]
Indices: [-1, 0, 0, -1, 3, -1]
------
steamGames_dp: 16 (Time: 0.0055 ms)
steamGames_grouped_dp: 16 (Time: 0.0186 ms)

根据上述的分析, 方法一偏向于处理 DLC 数量较少的情况，方法二则更适合处理 DLC 数量较多的情况。

因为这里 DLC 不多, 且方法二的复杂度和预算的平方成正相关，所以这里方法一更高效。

Sean's Blog

探索