算法知识点: DP，分组背包问题

复杂度：

解题思路：

可以将每个主件及其附件看作一个物品组，记主件为 ，两个附件为,则最多一共有4种组合：

这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作一个物品，那么问题就变成了分组背包问题。

C++ 代码： 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef pair <int, int> PII;
const int N = 70,
    M = 32010;
 
int m, n;
PII a[N];
vector<PII> b[N];
int f[M];
 
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
    {
        int v, w, p;
        scanf("%d%d%d", &v, &w, &p);
        w *= v;
        if (!p) a[i] = {
            v, w
        };
        else b[p].push_back(
        {
            v, w
        });
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (!a[i].first) continue;
 
        for (int j = m; j >= 0; j--)
            for (int k = 0; k < 1 << b[i].size(); k++)
            {
                int v = a[i].first, w = a[i].second;
                for (int u = 0; u < b[i].size(); u++)
                    if (k >> u &1)
                    {
                        v += b[i][u].first;
                        w += b[i][u].second;
                    }
 
                if (j >= v) f[j] = max(f[j], f[j - v] + w);
            }
    }
 
    printf("%d\n", f[m]);
 
    return 0;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ