题解 | #购物单#

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

int main() {
    int money, num;
    while (cin >> money >> num) { // 注意 while 处理多个 case
        vector<int> price(61, 0);
        vector<int> importance(61, 0);
        vector<int> parent(61, 0);
        vector<int> db(3201, 0);
        unordered_map<int, vector<int>> father;
        for (int i = 1; i < num + 1; i++) {
            int price_orign;
            cin >> price_orign >> importance[i] >> parent[i];
            price[i] = price_orign /
                       10; //价格和物品单价整除10，减少遍历次数
            if (parent[i] == 0) {
                father.insert(pair<int, vector<int>>(i, vector<int>(1,
                                                     0))); //主键map初始化
            }
        }
        //单独遍历一次防止附件再主键值前插入导致【i】【0】为非预期值
        for (int i = 1; i < num; i++) {
            if (parent[i] != 0) {
                father[parent[i]].push_back(i);
                father[parent[i]][0]++;//将主键附件关系记录
            }
        }
        for (int i = 1; i < num + 1 ; i++) {
            for (int j = money / 10; j > 0; j--) {
                if (parent[i] == 0) {
                    //买本体
                    //买本体加附件一
                    //买本体加附件二
                    //买本体加附件一二
                    if (j >= price[i]) {

                        db[j] = max(db[j], db[j - price[i]] + price[i] * importance[i]);
                    }
                    //考虑附件
                    if (father[i][0] == 1) {
                        int cur_annex = father[i][1];
                        if (j >= price[i] + price[cur_annex]) {
                            db[j] = max(db[j], db[j - price[i] - price[cur_annex]] + price[i] *
                                        importance[i] + price[cur_annex] *
                                        importance[cur_annex]); //主键已在上一步进行了比对，所以此时的db【j】已经取了较大值
                        }

                    }
                    if (father[i][0] == 2) {
                        int first_annex = father[i][1];
                        int second_annex = father[i][2];
                        if (j >= price[i] + price[first_annex]) {
                            db[j] = max(db[j], db[j - price[i] - price[first_annex]] + price[i] *
                                        importance[i] + price[first_annex] *
                                        importance[first_annex]); //考虑附件1
                        }
                        if (j >= price[i] + price[second_annex]) {
                            db[j] = max(db[j], db[j - price[i] - price[second_annex]] + price[i] *
                                        importance[i] + price[second_annex] *
                                        importance[second_annex]); //考虑附件2
                        }
                        if (j >= price[i] + price[first_annex] + price[second_annex]) {
                            db[j] = max(db[j], db[j - price[i] - price[first_annex] - price[second_annex]] +
                                        price[i] * importance[i] + price[first_annex] * importance[first_annex] +
                                        price[second_annex] * importance[second_annex]);//考虑附件12
                        }
                    }

                }
            }
        }
        cout << db[money / 10] * 10;

    }
}
// 64 位输出请用 printf("%lld")

背包问题卡了很久，最后选择用自己比较好理解的逻辑来做，主要根据题目进行问题拆解，根据题目中提供的物品上限以及附件主键依赖关系实现