题解 | 购物单

思路：把次件转换为主件。

举个例子，输入如下

100 5
80 2 0
40 5 1 ==>对应选择该次件和其主件的情况，可以转换为 40+80 2+5 0
20 5 1 ==>对应选择该次件和其主件的情况，可以转换为 20+80 2+5 0
(140 9 0)  ==>新添加的主件，对应两个次件都选的情况，可以转换为 20+40+80 2+2+5 0 
40 3 0
50 2 0

可以看出，次件的组合加上对应主件就相当于一个新的主件。

所以我们需要对输入进行处理，把次件转换成主件。

而对于主件，就可以用01背包的方法去做了。

这个方法应该可以处理任意n个次件的情况。

这里给出可以通过但没有优化的代码。

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

// dp[i][j] :=前i件物品，预算不大于j时，最大满意度

struct node{
    int price;
    int importance;
    int parent_node;
    vector<int> child_nodes;
    list<pair<int,int>> partial_sum_price_and_manyidu;
};


int main() {
    int max_price,N;
    cin >> max_price>> N;
    max_price/=10;//减小内存使用
    vector<node> stuffs(N+1);
    list<int> parent_stuff;

    for(int i=1;i<N+1;i++) {
        cin >> stuffs[i].price
        >> stuffs[i].importance
        >> stuffs[i].parent_node;
        stuffs[i].price/=10；
        if(stuffs[i].parent_node==0) {
             parent_stuff.push_back(i);
        }
        else{
            stuffs[stuffs[i].parent_node].child_nodes.push_back(i);
        }
    }

    // 计算选择主件后，所有可能的次件的价格和满意度的组合
    // 相当于把这些次件转换为主件
    // 题目说最多两个次件，就暴力写组合了
        for(auto& node:parent_stuff){
                list<pair<int,int>>& psum= stuffs[node].partial_sum_price_and_manyidu;
                int psum1=stuffs[node].price, psum2= stuffs[node].price*stuffs[node].importance;
                psum.emplace_back(psum1, psum2);
                for(auto& it : stuffs[node].child_nodes){

                        // 大小为一的组合 即主件分别加上每个单独的次件
                        psum1+=stuffs[it].price;
                        psum2+=stuffs[it].price * stuffs[it].importance;
                        psum.emplace_back(psum1,psum2);
                        psum1-=stuffs[it].price;
                        psum2-=stuffs[it].price * stuffs[it].importance;
                }
                if(stuffs[node].child_nodes.size()>1){
                        int& it = stuffs[node].child_nodes[0];
                        int& it1 = stuffs[node].child_nodes[1];
                        psum1+=stuffs[it].price+stuffs[it1].price;
                        psum2+=stuffs[it].price * stuffs[it].importance+stuffs[it1].price * stuffs[it1].importance;
                        psum.emplace_back(psum1,psum2);
                }
        }
    vector<vector<int>> dp(parent_stuff.size()+1,vector<int>(1+max_price));
    int i=1;
    for(auto it : parent_stuff) {
        for(int j=0;j<=max_price;j++) {
                dp[i][j] = dp[i-1][j];//如果j<value，取dp[i-1][j];
            for(const auto& [value,manyidu] : stuffs[it].partial_sum_price_and_manyidu) {
                if(j>=value){ 
                // 这里没有保证部分和的满意度单调，会导致dp[i][j]取最后一个满足该条件的最大值，需要取max
                    dp[i][j] = max(dp[i][j],dp[i-1][j-value]+ manyidu);
                }
            }
        }
        i++;
    }
    cout << 10*dp.back().back();//前面除以10，记得还原。
}
// 64 位输出请用 printf("%lld")