$算法分析：$

$如果没有附件的话,这道题就是一道0/1背包的模板题$

$但是题目又说一个主件最多有两个附件，那么对于每$

$个主件，都有5种情况：$

$1.什么都不买$

$2.只买主件$

$3.买一个主件和第一个附件$

$4.买一个主件和第二个附件$

$5.买一个主件和两个附件全买$

$所以我们枚举主件，对这5种情况分别转移即可。$

样例

样例输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出

2200

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
const int M = 5e3 + 1;
int n, m;
int mw[N], mc[N], aw[M][M], ac[M][M];
int f[N];
int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        int v, p, q;
        cin >> v >> p >> q;
        if(!q){
            mw[i] = v;
            mc[i] = v * p;
        }
        else{
            ++ aw[q][0];
            aw[q][aw[q][0]] = v;
            ac[q][aw[q][0]] = v * p;
        }
    }
    for(int i = 1;i <= m;i ++)
        for(int j = n;mw[i] != 0 && j >= mw[i];j --){
            f[j] = max(f[j], f[j - mw[i]] + mc[i]);
            if(j >= mw[i] + aw[i][1])
                f[j] = max(f[j], f[j - mw[i] - aw[i][1]] + mc[i] + ac[i][1]);
            if(j >= mw[i] + aw[i][2])
                f[j] = max(f[j], f[j - mw[i] - aw[i][2]] + mc[i] + ac[i][2]);
            if(j >= mw[i] + aw[i][1] + aw[i][2])
                f[j] = max(f[j], f[j - mw[i] - aw[i][1] - aw[i][2]] + mc[i] + ac[i][1] + ac[i][2]);
        }
    cout << f[n] << endl;
    return 0;
}