题解 | 购物单

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct MainItem {
    int v, w;
    vector<pair<int, int>> attachments; // 存储附件的价格和重要度乘积
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> items; // 存储所有物品的信息：v, w, q
    for (int i = 0; i < m; ++i) {
        int v, w, q;
        cin >> v >> w >> q;
        items.emplace_back(v, w, q);
    }

    map<int, MainItem> mainItems;

    // 处理主件
    for (int i = 0; i < m; ++i) {
        int v = get<0>(items[i]);
        int w = get<1>(items[i]);
        int q = get<2>(items[i]);
        if (q == 0) { // 主件
            int id = i + 1; // 物品编号从1开始
            mainItems[id] = {v, w, {}};
        }
    }

    // 处理附件
    for (int i = 0; i < m; ++i) {
        int v = get<0>(items[i]);
        int w = get<1>(items[i]);
        int q = get<2>(items[i]);
        if (q != 0) { // 附件
            int main_id = q;
            if (mainItems.find(main_id) != mainItems.end()) {
                mainItems[main_id].attachments.emplace_back(v, w);
            }
        }
    }

    // 生成所有主件的组合
    vector<vector<pair<int, int>>> groups;
    for (auto &entry : mainItems) {
        MainItem &main = entry.second;
        int k = main.attachments.size();
        vector<pair<int, int>> combs;
        for (int mask = 0; mask < (1 << k); ++mask) {
            int price = main.v;
            int satis = main.v * main.w;
            for (int i = 0; i < k; ++i) {
                if (mask & (1 << i)) {
                    price += main.attachments[i].first;
                    satis += main.attachments[i].first * main.attachments[i].second;
                }
            }
            combs.emplace_back(price, satis);
        }
        groups.push_back(combs);
    }

    // 动态规划处理分组背包
    vector<int> dp(n + 1, 0);
    for (auto &group : groups) {
        for (int j = n; j >= 0; --j) {
            int current_max = dp[j];
            for (auto &comb : group) {
                int price = comb.first;
                int satis = comb.second;
                if (j >= price) {
                    current_max = max(current_max, dp[j - price] + satis);
                }
            }
            dp[j] = current_max;
        }
    }

    cout << dp[n] << endl;
    return 0;
}