$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

分组背包思路：

• $1. 状态表示$
  $集合：只从前\ i\ 组物品中选，第\ i\ 组物品选第\ k\ 个物品，体积不超过\ j\ 的价值$
  $属性：\max$

• $2. 状态转移$
  $选择第\ i\ 组物品的第\ k\ 个物品：f[i][j]=\max\{f[i-1][j-v[i][k]]+w[i][k]\}\ (0\le k\le s[i])$

本题思路：

1. 将第 i 个主件以及其携带的附件看成是第 i 组物品
2. 假设第 i 个主件有 n 个附件，则第 i 组物品有 2 ^ n 种决策
3. 依次枚举每组物品，体积，决策

完整代码

#include<bits/stdc++.h>

#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> servant[N];
int f[M];

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

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

    for(int i=1;i<=n;i++) //枚举个数
        for(int j=m;j;j--) //枚举体积
            for(int k=0;k<1<<servant[i].size();k++) //枚举决策
            {
                int v=master[i].v,w=master[i].w; //主件
                for(int u=0;u<servant[i].size();u++) //附件
                    if(k>>u&1)
                    {
                        v+=servant[i][u].v;
                        w+=servant[i][u].w;
                    }
                if(j>=v) f[j]=max(f[j],f[j-v]+w);
            }

    cout<<f[m]<<endl;

    return 0;
}