题解 | #购物单#

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


int main() {
    int money, num;
    unordered_map<int, vector<int>> primary;
    cin >> money >> num;
    if (money <= 0 || num <= 0) {
        return 0;
    }
    money /= 10;
    // cin primary
    vector<int> price(num+1, 0), value(num+1, 0);
    for (int i = 1; i <= num; ++i) {
        int v, p, q;
        cin >> p >> v >> q;
        price[i] = p/10;
        value[i] = v*p;
        if (q == 0) {
            if (!primary.count(i)) {
                primary.insert({i, {0, 0}});
            }
        }
        if (q > 0) {
            if (!primary.count(q)) {
                primary.insert({q, {i, 0}});
            } else {
                if (primary[q][0] == 0)
                    primary[q][0] = i;
                else
                    primary[q][1] = i;
            }
        }
    }
    // bag
    vector<int> dp(money+1, 0);
    for (const auto pr: primary) {
        int id = pr.first;
        for (int j = money; j >= price[id]; --j) {
            int ap1 = pr.second[0], ap2 = pr.second[1];
            dp[j] = max(dp[j], dp[j-price[id]]+value[id]);
            if (j >= price[ap1] + price[id]) {
                dp[j] = max(dp[j], dp[j-price[id]-price[ap1]]+value[id]+value[ap1]);
            }
            if (j >= price[ap2] + price[id]) {
                dp[j] = max(dp[j], dp[j-price[id]-price[ap2]]+value[id]+value[ap2]);
            }
            if (j >= price[ap1] + price[ap2] + price[id]) {
                dp[j] = max(dp[j], dp[j-price[id]-price[ap1]-price[ap2]]+value[id]+value[ap1]+value[ap2]);
            }     
        }
    }
    cout << dp[money] << endl;
    return 0;
}

关键点：

为了更方便主键没有附件填0，所以Price和value需要多申请一个，下标从1开始。

逆向是为了优先把price大的物品先放进去试试，如果正向的话，Price小的物品已经占据了该空间，导致price大的无法放入。

dp推导公式逆向时，不是跟前一个比是跟自己比（前一个更新永远比当前慢）：dp[j] = max(dp[j], dp[j-price[i]]+value[i])