题解 | 购物单

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item {
    int price; //价格
    int importance; //重要度
    int master; //主键编号
};

int main() {
    int n, m; // n: 总预算, m: 物品总数
    cin >> n >> m;

    vector<Item> items(m + 1); //存储所有物品
    vector<vector<int> > attachments(m + 1); //存储每个主件的附件编号

    for (int i = 1; i <= m; ++i) {
        int price, importance, master;
        cin >> price >> importance >> master;
        items[i] = {price, importance, master};
        if (master > 0) {
            attachments[master].push_back(i);
        }
    }

    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= m; ++i) {
        //跳过附件 直接处理主件 因为从主件上也可以找到附件 所以不用单独考虑附件
        if (items[i].master) continue;

        int price0, price1, price2; //分别表示主件 附件1和附件2的价格 price要单独用变量表示而不是用items[i].price，是因为后面更新dp数组的时候用得到 而importance就不用单独表示出来了
        int satisfaction0, satisfaction1, satisfaction2; //表示满意度

        price0 = items[i].price;
        satisfaction0 = price0 * items[i].importance;

        price1 = 0;
        price2 = 0;
        satisfaction1 = 0;
        satisfaction2 = 0;

        if (attachments[i].size() >= 1) {
            int idx1 = attachments[i][0];
            price1 = items[idx1].price;
            satisfaction1 = price1 * items[idx1].importance;
        }

        if (attachments[i].size() == 2) {
            int idx2 = attachments[i][1];
            price2 = items[idx2].price;
            satisfaction2 = price2* items[idx2].importance;
        }

        for (int j = n; j >= price0; --j) {
            //只买主件
            dp[j] = max(dp[j], dp[j - price0] + satisfaction0);

            //买主件+附件1
            if (j - price0 - price1 >= 0) {
                dp[j] = max(dp[j], dp[j - price0 - price1] + satisfaction0 + satisfaction1);
            }
            //买主件+附件2
            if (j - price0 - price2 >= 0) {
                dp[j] = max(dp[j], dp[j - price0 - price2] + satisfaction0 + satisfaction2);
            }
            //买主件+附件1、2 
            if(j - price0 - price1 - price2 >= 0) {
                dp[j] = max(dp[j], dp[j - price0 - price1 - price2] + satisfaction0 + satisfaction1 + satisfaction2);
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

动态规划 还是难……