(转成01背包) $O(n*v)$

遍历主件，对每个主件，新开一个临时数组，在取这个主件的情况下把上次状态转移过来。然后用这个主件的附件在这个临时数组上跑01背包。最后用这个临时数组去更新原数组就行了（取最大值）。so easy！

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

vector<int> e[66];
int v[66], w[66], p;
int f[32023], g[32023];

int main(void)
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        cin >> v[i] >> w[i] >> p;
        e[p].push_back(i);
    }

    for (const auto& cur : e[0])
    {
        for (int j = v[cur]; j <= n; ++j)
            g[j] = f[j - v[cur]] + v[cur] * w[cur];

        for (const auto& next : e[cur])
            for (int j = n; j >= v[next] + v[cur]; --j)
                g[j] = max(g[j], g[j - v[next]] + v[next] * w[next]);

        for (int j = 0; j <= n; ++j)
            f[j] = max(f[j], g[j]);
    }

    cout << f[n] << endl;

    return 0;
}