金明的预算方案 https://www.acwing.com/problem/content/489/

每个主件有0/1/2个附件，要买附件，必须先买主件
每件物品有重要度，如何在不超过n元的情况下，使每件物品价格与重要度乘积最大

把每一个主件和附件的组合看成一组，每一组里面的物品为主件和附件的选法

记主件为p，附件为a，b，则每组最多有4种组合
p / p a / p b / p a b

时间复杂度o(Nm)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 70, M = 32010;
int f[M], n, m;
PII master[N];
vector<PII> servent[N];

int main()
{
    cin >> m >> n;
    for ( int i = 1; i <= n; i ++ )
    {
        int v, w, q;
        cin >> v >> w >> q;
        if ( !q ) master[i] = make_pair(v, v * w);  //主件
        else servent[q].push_back(make_pair(v, v * w)); //附件
    }
    for ( int i = 1; i <= n; i ++ )
        if ( master[i].first )
            for ( int j = m; j >= 0; j -- )
                for ( int k = 0; k < (1 << servent[i].size()); k ++ )   //用二进制遍历，1表示选，0表示不选
                {
                    int w = master[i].second, v = master[i].first;  //先加上主件
                    for ( int u = 0; u < servent[i].size(); u ++ )      //取出二进制下每一位的数字
                        if ( k >> u & 1 )
                        {
                            v += servent[i][u].first;              
                            w += servent[i][u].second;
                        }
                    if ( j >= v ) f[j] = max(f[j], f[j - v] + w);
                }
    cout << f[m];
    return 0;
}