题解 | 购物单 ：转换成分组背包求解

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;

int main() {
    int money;
    int num;
    cin >> money >> num;
    vector<vector<int>> products;
    unordered_map<int, vector<int>> apeds;
    int index = 0;
    int a, b, c;
    //输入到数组
    while (cin >> a >> b >> c) {
        products.push_back({a, a * b, c});
        if (c != 0) {
            apeds[c - 1].emplace_back(index);
        }
        index++;
    }
    //转换分组背包
    vector<vector<vector<int>>> groups;
    index = 0;
    //处理没有附件的主件
    for (auto& pro : products) {
        if (pro[2] == 0 && apeds.count(index) == 0) {
            groups.push_back({{pro[0], pro[1]}});
        }
        index++;
    }
    //处理有附件的主件及其附件
    for (auto& [index, asso] : apeds) {
        int m_cost = products[index][0];
        int m_happy = products[index][1];
        int n = asso.size();
        vector<vector<int>>group;
        for (int mask = 0; mask < (1 << n); mask++) {
            int cost = m_cost;
            int happy = m_happy;
            for (int i = 0 ; i  <  n ; i++) {
                if (mask & (1 << i)) {
                    vector<int>& aped = products[asso[i]];
                    cost += aped[0];
                    happy += aped[1];
                }
            }
            group.push_back({cost, happy});
        }
        groups.push_back(group);
    }
    //计算分组背包
    vector dp (money + 1, 0);
    for (const auto& group : groups) { //枚举分组
        for (int m = money; m >= 0; m--) { //枚举背包容量(逆序,防止数据覆盖)
            for (const auto& val : group) { //更新每个背包的最大满意度
                if (m >= val[0])
                dp[m] = max(dp[m], dp[m - val[0]] + val[1]);
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}