$\color{red}{DP}$——目录

题目大意：

一共有 $N$ 个物品和 $M$ 元钱

物品之间可能存在 依赖关系，对于第 $i$ 个物品，价格为 $v_i$，价值为 $w_i$，依赖的父物品为 $p_i$
每个物品只能被购买一次

依赖关系：只有购买了父物品后，才能购买子物品 （若 $p_i=0$ 表示该物品为 主件）

求一种 购买方案，使得 总花费 不超过 $M$，且 总价值 最大

解题方法：

我们发现每个子物品没有再附属的子物品，所以我们可以考虑枚举选择子物品的方案
我们可以对于每一个集合，不选的话无需更新，如果购买必须购买主件，所以我们可以先购买主件，然后枚举附件的选择方案就可以了。

$$闫氏DP分析法$$

1. 状态表示——集合：$f[i][j]$ 表示考虑前 $i$ 个物品，且总体积不超过 $j$ 的集合下能获得的最大价值。
2. 状态表示——属性：因为是求最大价值，故为 $max$。
3. 状态计算——集合划分：考虑第 $i$ 个选不选。
   • 不选或选不了（剩余体积不够 $j < v[i]$）：$f[i - 1][j]$。
   • 选：$f[i - 1][j - v[i]] + w[i]$。首先你对第i个物品进行了你的抉择，所以前一维变成了 $i - 1$，接着因为使用了 $v[i]$ 的体积，所以应该是 $j - v[i]$。

其实状态表示是不变的，只是在代码中用了循环的方式枚举物品而已
当然也可以优化一下，就是用DP的方式考虑所有子物品，代码在最后贴上，感兴趣的可以康康

下面这个代码如果写成二维的话就需要再最后传递一下，防止不是主物品。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define v first
#define w second

using namespace std;

typedef pair<int, int> PII;
const int N = 70, M = 32010;

int n, m;
PII master[N];
vector<PII> sv[N];
int f[M];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ ) {
        int v, w, q;
        cin >> v >> w >> q;
        if (!q) master[i] = {v, v * w};
        else sv[q].push_back({v, v * w});
    }

    for (int i = 1; i <= n; i ++ ) 
        if (master[i].v) {
            for (int j = m; j >= 0; j -- ) {
                for (int k = 0; k < 1 << sv[i].size(); k ++ ) {
                    int v = master[i].v, w = master[i].w;
                    for (int u = 0; u < sv[i].size(); u ++ ) 
                        if (k >> u & 1) {
                            v += sv[i][u].v;
                            w += sv[i][u].w;
                        }
                    if (j >= v) f[j] = max(f[j], f[j - v] + w);
                }
            }
        }
        /*
        如果写成二维就这样写：
        for (int i = 1; i <= m; i ++ ) f[i][j] = max(f[i][j], f[i - 1][j]);
        */
    cout << f[m] << endl;
    return 0;
}

接下来是其他大佬写的优化代码

#include <bits/stdc++.h>
#define v first
#define w second

using namespace std;
typedef pair<int, int> PII;
const int N = 32010, M = 70;

int n, m;
PII fa[M];
vector<PII> son[M];
int f[M][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (!c) fa[i] = {a, a * b};
        else son[c].push_back({a, a * b});
    }

    for (int i = 1; i <= m; i ++ )
    {
        if (fa[i].v)
        {
            // 01背包，先从主件开始放
            for (int j = fa[i].v; j <= n; j ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - fa[i].v] + fa[i].w);

            // 因为push_back的下标是从0开始的，遍历的时候要注意
            // 这部分判断的是，放入当前的主件，对于这个主件的附件用01背包的方式去思考求解
            // 并且当前的f[i][j]一定是已经放入当前主件的情况
            for (int k = 0; k < son[i].size(); k ++ )
                for (int j = n; j >= son[i][k].v; j -- )
                    // 放过主件以后，才能放附件，f为0的部分说明这部分放不进当前的主件
                    if (f[i][j - son[i][k].v] > 0)
                        f[i][j] = max(f[i][j], f[i][j - son[i][k].v] + son[i][k].w);
        }
        // 注意i不是主件时，也要把状态传递下去
        for (int j = 0; j <= n; j ++ )
            f[i][j] = max(f[i][j], f[i - 1][j]);
    }

    cout << f[m][n] << endl;
    return 0;