题解 | #购物单#

以主键为物品，附件作为主件的不同开销和价值选项，按照01背包的算法解决该问题。

#include <iostream>
#include <map>

using namespace std;

struct Good {
    int price;
    int importance;
    struct Good* next;
    Good() {
        next = nullptr;
    }
};

int main() {
    int total_money;
    int total_goods;
    map<int, Good*> things;
    int dp[61][3200] = {0};

    scanf("%d %d", &total_money, &total_goods);
    total_money /= 10;

    // 读取物品，按照主件进行存放,主件为表头元素，后续元素为附件
    for(int i=1; i<=total_goods; i++) {
        Good* item = new Good;
        int num;
        scanf("%d %d %d", &(item->price), &(item->importance), &num);
        item->price /= 10;
        if (num == 0) {
            item->next = things[i];
            things[i] = item;
        } else {
            if (things.count(num) == 0) {
                things[i] = item;
            } else {
                Good* tmp = things[num]->next;
                things[num]->next = item;
                item->next = tmp;
            }
        }
    }

    int thing_index = 1;
    for(auto i=things.begin(); i != things.end(); i++) {
        for(int m = 1; m <= total_money; m++) {
            Good* item = i->second;
            // 将主附件的开销和价值保存到数组中
            int money[3];
            int value[3];
            for(int j=0; j<3; j++) {
                if (item != nullptr) {
                    money[j] = item->price;
                    value[j] = item->price * item->importance;
                    item = item->next;
                } else {
                    money[j] = 0;
                    value[j] = 0;
                }
            }
            int value_total;
            int cur_money;
            int cur_value;
            value_total = dp[thing_index - 1][m];
            cur_money = money[0];
            cur_value = value[0];
            if (m >= cur_money) {
                value_total = max(dp[thing_index - 1][m - cur_money] + cur_value, value_total);
            }
            cur_money = money[0] + money[1];
            cur_value = value[0] + value[1];
            if (m >= cur_money) {
                value_total = max(dp[thing_index - 1][m - cur_money] + cur_value, value_total);
            }

            cur_money = money[0] + money[2];
            cur_value = value[0] + value[2];
            if (m >= cur_money) {
                value_total = max(dp[thing_index - 1][m - cur_money] + cur_value, value_total);
            }

            cur_money = money[0] + money[1] + money[2];
            cur_value = value[0] + value[1] + value[2];
            if (m >= cur_money) {
                value_total = max(dp[thing_index - 1][m - cur_money] + cur_value, value_total);
            }
            dp[thing_index][m] = value_total;
        }
        thing_index++;
    }
    cout << dp[things.size()][total_money] * 10;
    return 0;
}