题解 | #购物单#

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

int main() {
    int sum, num;
    cin >> sum;
    cin >> num;
    vector<vector<int>> arr(num, vector<int>(3, 0));
    for (int i = 0; i < num; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> arr[i][j];
        }
        arr[i][0] /= 10; //因为所有价格都是10的倍数
        arr[i][1] *= arr[i][0]; //直接计算出满意度
    }
    vector<vector<int>> main; //主件数组
    unordered_map<int, vector<int>> map; // 主件哈希表
    for (int i = 0; i < num; ++i) {
        if (arr[i][2] != 0) { //如果是附件
            map[arr[i][2]-1].push_back(i); // -1是为了与数组下标一致
        }
        else {
            main.push_back({arr[i][0], arr[i][1],i}); //main[i-1][0]]是价格，main[i-1][1]是满意度
        }
    }
    int m = sum / 10, n = main.size(); //计算背包问题，创建dp数组，dp[i]表示考虑前i个物品
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int price = main[i - 1][0], value = main[i - 1][1], indice = main[i - 1][2];
            vector<vector<int>> comb{ {price, value} };
            int index1, index2;
            if (map[indice].size() == 1) {
                index1 = map[indice][0];
                comb.push_back({ price + arr[index1][0], value +  arr[index1][1] });
            }
            if (map[indice].size() == 2) {
                index1 = map[indice][0];
                index2 = map[indice][1];
                comb.push_back({ price + arr[index1][0],  value + arr[index1][1] });
                comb.push_back({ price + arr[index2][0],  value + arr[index2][1] });
                comb.push_back({ price + arr[index1][0] + arr[index2][0],  value +  arr[index1][1] +  arr[index2][1] });
            }
            int max_i = dp[i-1][j];
            for (auto& c : comb) { //获取附件索引
                int price2 = c[0], value2 = c[1];
                if (j >= price2) { //如果背包容量大于当前放入附件价格
                    max_i = max(max_i, dp[i - 1][j - price2] + value2);
                }
            }
            dp[i][j] = max_i;
        }
    }
    cout << dp[n][m] * 10;
    return 0;
}