分组背包

$O(nm)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

const int N = 65, M = 32010;

//将主件和附件搭配，一组最多有四种情况
//假设主件为p, 附件为 a, b
//则有四种选择，p, (p, a), (p, b), (p, a, b)

typedef pair<int, int> PII;
int f[N][M];    //f[i, j]表示从前i组中选，每组只能选一个，总钱数剩余j可获得的最大价值

vector<PII> goods[N];

int n, m, v, p, q;

int main(){
    scanf("%d %d", &m, &n);
    for(int i = 1; i <= n; i++){
        scanf("%d %d %d", &v, &p, &q);
        if(!q) goods[i].push_back({v, v * p});
        else{
            if(goods[q].size() == 1){
                auto t = goods[q][0];
                goods[q].push_back({v + t.first, v * p + t.second});    //(p, a)
                }
            else{
                auto t = goods[q][0], k = goods[q][1];
                goods[q].push_back({v + t.first, v * p + t.second});    //(p, b)
                goods[q].push_back({v + k.first, v * p + k.second});   //(p, a, b)
                }
            }
        }

    //接下来按分组背包做
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            f[i][j] = f[i - 1][j];
            for(int k = 0; k < goods[i].size(); k++){
                if(j - goods[i][k].first >= 0)
                    f[i][j] = max(f[i][j], f[i - 1][j - goods[i][k].first] + goods[i][k].second);
                }
            }
        }
    printf("%d\n", f[n][m]);
    return 0;
}