算法

(分组背包) $O(Nm)$

先预处理一下数组，可以考虑以下四种情况：
1. 只买主件
2. 买主件和第一个附件
3. 买主件和第二个附件
4. 买主件和两个附件

然后打一下分组背包的板子就行了。所以麻烦在于前面数组的预处理~~

C++ 代码

#include <iostream>

using namespace std;

struct bag {
    int cnt;
    int w[5], v[5];
} a[70];

int dp[32010];

int main() {
    int N, m;
    cin >> N >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z == 0) {
            a[i].cnt = 1;
            a[i].w[1] = x;
            a[i].v[1] = x * y;
        }
        else {
            if (a[z].cnt == 1) {
                a[z].cnt = 2;
                a[z].w[2] = a[z].w[1] + x;
                a[z].v[2] = a[z].v[1] + x * y;
            }
            else {
                a[z].w[3] = a[z].w[1] + x;
                a[z].v[3] = a[z].v[1] + x * y;
                a[z].w[4] = a[z].w[2] + x;
                a[z].v[4] = a[z].v[2] + x * y;
                a[z].cnt = 4;
            }
        }
    } 

    for  (int i = 1; i <= m; i++) {
        for (int j = N; j >= 0; j--) {
            for (int k = 1; k <= a[i].cnt; k++) {
                if (j >= a[i].w[k]) {
                    dp[j] = max(dp[j], dp[j - a[i].w[k]] + a[i].v[k]);
                }
            }
        }
    }

    cout << dp[N] << '\n';

    return 0;
}