题解 | 购物单

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

struct Item {
    int v, w, q;
    vector<Item> sub_items;
    vector<int> values;
    vector<int> cost;
    Item(int v, int w, int q): v(v), w(w), q(q) {
        values.push_back(w * v);
        cost.push_back(v);
    }
    void push(Item& subi) {
        sub_items.push_back(subi);
        values.push_back(values[0] + subi.v * subi.w);
        cost.push_back(cost[0] + subi.v);
        if (sub_items.size() == 2) {
            values.push_back(values[2] + values[1] - values[0]);
            cost.push_back(cost[2] + cost[1] - cost[0]);
        }
    }
};


int main() {
    int n, m;
    cin >> n >> m;
    n = n / 10;
    vector<Item> items;
    vector<Item> sub_items;
    for (int i = 0; i < m; i++) {
        int v, w, q;
        cin >> v >> w >> q;
        v = v / 10;
        if (q > 0) {
            sub_items.emplace_back(v, w, q);
        }
        items.emplace_back(v, w, q);
    }
    for (Item& subi : sub_items) {
        items[subi.q - 1].push(subi);
    }
    vector<vector<int>> dp(items.size() + 1, vector<int>(n + 1, 0));
    int score_max = 0;
    int item_num = 0;
    for (int i = 0; i < items.size(); i++) {
        Item item = items[i];
        if (item.q > 0) {
            continue;
        }
        item_num++;
        for (int j = 1; j <= n; j++) {
            dp[item_num][j] = dp[item_num-1][j]; //##### 1
            for (int k = 0; k < item.values.size(); k++) {
                int value = item.values[k];
                int cost = item.cost[k];
                if (j >= cost) {
                    int t =  max(dp[item_num - 1][j], dp[item_num - 1][j - cost] + value*10);
                    dp[item_num][j] = max(dp[item_num][j], t); //##### 2
                }
            }
        }
    }
    cout << dp[item_num][n] ;
}
// 64 位输出请用 printf("%lld")

01背包问题变形

容易出问题的点：

1. 对于主件，更新的值应该是所有可能的组合是最大的值，一开始容易写成只要能购买就更新，这样可能导致后面低价值组合覆盖前面高价值的组合。（更新时选择）
2. 更新dp[n][j]前，应该初始化为dp[n][j]= dp [n-1][j]，否则有可能当前的j小于当前所有组合，导致一直为初值0，影响后面的更新。（更新前的设置）