金明的预算方案（DP+邻接表）

解题思路:DP (分别考虑只拿主件， 主件+ 1附件， 主件 + 2附件）

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;

// 定义常量 N，用于确定数组的最大长度
const int N = 2e5 + 10;

// 全局变量声明
int n, m, dp[N];  // n 表示背包的最大容量，m 表示物品的数量，dp 数组用于动态规划

// 定义结构体 node，用于存储物品信息
struct node{
    int w, p;  // w 表示物品的重要程度，p 表示物品的价值
};

// 定义一个数组，数组的每个元素是一个存储 node 结构体的向量
// 用于将物品按组存储，a[i] 表示第 i 组的物品
vector<node> a[N];

int main()
{
    // 从标准输入读取背包的最大容量 n 和物品的数量 m
    cin >> n >> m;

    // 循环读取每个物品的信息
    for(int i = 1; i <= m; ++ i){
        int w, p, idx;
        // 读取物品的价值 p、重要程度 w 和所属组的索引 idx
        cin >> p >> w >> idx;
        if (!idx) a[i].push_back({w,p});  // 若 idx 为 0，将该物品放入第 i 组
        else a[idx].push_back({w,p});  // 否则，将该物品放入第 idx 组
    }

    // 动态规划过程，遍历每一组物品
    for(int i = 1; i <= m; ++ i){
        // 若第 i 组有物品
        if(a[i].size() > 0)
            // 从背包最大容量 n 开始，逆向遍历到该组第一个物品的重量
            for(int j = n; j >= a[i][0].p; j --){
                int t = j, ac = 0;  // t 记录当前剩余容量，ac 记录当前累计价值
                // 遍历第 i 组的所有物品
                for(int k = 0; k < a[i].size(); ++ k){
                    // 若当前剩余容量足够放入第 k 个物品
                    if(t >= a[i][k].p){
                        t -= a[i][k].p;  // 减去该物品的价值，更新剩余金钱
                        ac += a[i][k].w * a[i][k].p;  // 累加该物品的价值，更新累计价值
                    }
                    // 更新 dp[j] 为当前值和新方案值中的较大值
                    dp[j] = max(dp[j], dp[t] + ac);
                }
            }
    }
    // 输出背包容量为 n 时能获得的最大价值
    cout << dp[n];
    return 0;
}