题解 | 购物单

#include<bits/stdc++.h>
using namespace std;
int main() {
    int a, b;  // a：预算，b:物品数
    cin >> a >> b;
    vector<vector<int>> arr(3, vector<int>(b, 0));  // 存储输入
    vector<vector<int>> brr(6, vector<int>(b, 0));  // 存储主件及其附件信息
    // brr[0][]主件价格 brr[1][]主件重要度
    // brr[2][]附件价格 brr[3][]附件重要度
    // brr[4][]附件价格 brr[5][]附件重要度
    // 输入模块
    for (int i = 0; i < b; i++) {
        cin >> arr[0][i] >> arr[1][i] >> arr[2][i];
    }
    // 整合为brr
    for (int i = 0; i < b; i++) {
        if (arr[2][i] == 0) {
            brr[0][i] = arr[0][i];
            brr[1][i] = arr[1][i];
        } else {
            int c = arr[2][i] - 1;
            if (brr[2][c] == 0) {
                brr[2][c] = arr[0][i];
                brr[3][c] = arr[1][i];
            } else {  // 第二个附件
                brr[4][c] = arr[0][i];
                brr[5][c] = arr[1][i];
            }
        }
    }
    // 动态规划部分
    vector<int> dp(a + 1,0);  // dp动态数组初始化，a+1表示总共有a+1项，0表示从0开始
    for (int i = 0; i < b; i++) {
        if (brr[0][i] == 0) continue;  // 跳过不存在有效数据的行
        // 生成所有可能的组合
        vector<pair<int, int>> c;//c={{价格, 满意度},{价格, 满意度}...}
        // 组合1：仅主件
        c.push_back({brr[0][i], brr[0][i] * brr[1][i]});
        // 组合2：主件+附件1
        if (brr[2][i] != 0) {
            c.push_back({brr[0][i] + brr[2][i],
                         brr[0][i] * brr[1][i] + brr[2][i] * brr[3][i]});
        }
        // 组合3：主件+附件2
        if (brr[4][i] != 0) {
            c.push_back({brr[0][i] + brr[4][i],
                         brr[0][i] * brr[1][i] + brr[4][i] * brr[5][i]});
        }
        // 组合4：主件+附件1+附件2
        if (brr[2][i] != 0 && brr[4][i] != 0) {
            c.push_back({brr[0][i] + brr[2][i] + brr[4][i],
                         brr[0][i] * brr[1][i] + brr[2][i] * brr[3][i] + brr[4][i] * brr[5][i]});
        }
        // 更新dp数组！！
        for (int j = a; j >= 0; j--) {
            for (auto& d : c) {  //d引用读取结构体c的记录
                if (j >= d.first) {
                    dp[j] = max(dp[j], dp[j - d.first] + d.second);//更新核心
                }
            }
        }
    }
    cout << dp[a] << endl;
    return 0;
}