把代码整理简化后加了些注释，更接近01背包，更好看一点

#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;
}

为什么一定是已经放入当前主件的情况呢？

Ta有可能在另一个阶段被更新啊，所以不为零无法说明Ta是选择了主件的吧？

大佬您太强了，我的思路与您相似，但是不知道哪里出问题了

#include <bits/stdc++.h>
using namespace std;
const int N = 32110;
int m, n;
int v[N], w[N];
int ans;
vector<int> vec[N];
int vis[N];
int id;
int f[110][N];
int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> v[i] >> w[i];
        cin >> id;
        if(id) vec[id].push_back(i);
        else vis[i] = 1;
    }
    for(int i = 1; i <= n; i ++ )
    {
        if(vis[i])
        {
            for(int j = m; j >= 0; j -- )
            {
                f[i][j] = f[i - 1][j];
                if(j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i] * v[i]);
            }
            for(auto p : vec[i])
            {
                for(int j = m; j >= v[i] + v[p]; j -- )
                {
                    f[i][j] = max(f[i][j], f[i - 1][j - v[p] - v[i]] + w[p] * v[p] + w[i] * v[i]);
                }
            }
        }
        else
        {
            for(int j = m; j >= 0; j -- ) f[i][j] = f[i - 1][j];
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

我知道了，因为这样的话漏了一种情况，谢谢大佬

请问一下 你这个写法 会漏哪种情况

再优化一下：

#include <iostream>
#include <vector>
#define v first
#define w second
using namespace std;
using PII = pair<int, int>;
const int M = 32010, N = 70;

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

int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= n; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (!c) g[i] = {a, a * b};
    else son[c].push_back({a, a * b});
  }

  for (int i = 1; i <= n; i++) {
    for (int j = g[i].v; j <= m; j++)
      f[i][j] = f[i - 1][j - g[i].v] + g[i].w;

    for (int k = 0; k < son[i].size(); k++)
      for (int j = m; j >= g[i].v + son[i][k].v; j--)
        f[i][j] = max(f[i][j], f[i][j - son[i][k].v] + son[i][k].w);

    for (int j = 0; j <= m; j++)
      f[i][j] = max(f[i][j], f[i - 1][j]);
  }

  printf("%d\n", f[n][m]);
}

不知道还能不能优化成滚动数组，我自己尝试好像不可以

显然是可以的

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void take_max(T &a,const T &b) noexcept
{
    if(a<b)
        a=b;
}
template<typename T>
inline void take_min(T &a,const T &b) noexcept
{
    if(a>b)
        a=b;
}
template<typename _ForwardIterator>
void print(_ForwardIterator first,_ForwardIterator last) noexcept
{
    if(first!=last)
    {
        do{
            (cout<<(*first)).put(' ');
        }while(++first!=last);
    }
    cout.put('\n');
}
typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
constexpr uint N=65U,M=32005U;
uint v[N],w[N],fa[N];
uint h[N],e[N],ne[N],idx;
inline void add(const uint u,const uint v) noexcept
{
    ++idx;
    e[idx]=v,ne[idx]=h[u],h[u]=idx;
}
uint dp[2U][M];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // 显然是分组背包，一套主件和附件分一组
    // 一组内构成树形结构，可以树形背包，但会超时
    // 一组有n个附件的组，处理出其背包数组的时间复杂度O(n*V^2)
    // 然后背包合并，n组物品，则时间复杂度为O(n*V^2)

    // 观察数据范围
    // 本题一个主件的附件数不超过2且附件没有附件
    // 因此我们可以对一个主件的附件进行子集枚举

    // 优化
    // 如果题目只给附件没有附件，那么每一组就是一个菊花图
    // 按树形背包的思想，可以发现只要选了主件，那附件可以01背包
    // 于是就不用枚举附件的每个子集了
    // 我们在根上预留出根节点要的空间，子节点直接作为一个物品往上做01背包即可
    // 然后一组有n个附件的组，我们只用O(nV)的时间复杂度就处理出了其背包数组
    // 但处理出背包数组是需要合并的，合并复杂度不可接受
    // 考虑变换一下，把物品往总的背包数组里加
    // 先强制钦定选该组的主件，然后01背包选附件，再与不选该组的情况取max
    // 这样就变相完成了把这组物品加入背包的操作
    // 非常美妙的做法
    uint V,n;
    cin>>V>>n;
    for(uint i(1U);i<=n;++i)
    {
        cin>>v[i]>>w[i];
        w[i]*=v[i];
        cin>>fa[i];
        add(fa[i],i);
    }
    uint *cur(*dp),*last(dp[1U]);
    for(uint i(1U);i<=n;++i)
    {
        if(fa[i])
            continue;
        for(uint j(v[i]);j<=V;++j)
            cur[j]=last[j-v[i]]+w[i];
        for(uint ei(h[i]);ei;ei=ne[ei])
        {
            const uint son(e[ei]);
            for(uint j(V);j>=v[i]+v[son];--j)
                take_max(cur[j],cur[j-v[son]]+w[son]);
        }
        for(uint i(1U);i<=V;++i)
            take_max(cur[i],last[i]);
        swap(cur,last);
        // 注意到dp数组的每一个元素都是单增的，因此不用memset0
    }
    (cout<<last[V]).put('\n');
    return 0;
}

锟斤拷烫烫烫

大佬好强。但是这段好搞不懂： 分步骤来就好了，当我们处理DP第I组的时候，我们先选择了第I组的主件而不选任何附件的数据进行处理，这样我们第I行DP里面凡是不为0的，就意味着选了主件，凡是为0，就意味着没选主件

马蜂…

宏定义太多了

# 妙

宏定义了个寂寞

请问这是DP套DP嘛

这种写法的思路和我的差不多，也就是类似于有依赖性背包的解法。但感觉有几处说的不太对，原句中所指的“这样我们第I行DP里面凡是不为0的，就意味着选了主件，凡是为0，就意味着没选主件，然后我们就发现可以直接枚举所有的附件”这句话个人感觉解释为“先假设放入主件，然后更新附件的值”，其实判断dp中凡是不为0的位置就相当于判断该位置是否是主件更新的范围内。也就可以用类似有依赖性背包的做法。先更新放入附件的值(0~V-v[i])(V指总钱数，v[i]指该主件的花费钱数)，然后更新放入主键的dp，在判断和原dp比较取最大值
还有就是虽然数据写的很好，但题目给的钱数要求十的倍数（可能是后来更新了题面）。建议数据可以改为10的倍数

%%%

讲的挺好的，我一开始也是这么想的，这个解法应该是这道题的升级版，（题目里好像讲了一个主件最多两附件，不知道是不是后来加的）

tql!!!!

tql

orz,

tqlll

加一个Markdown就完美了