题解 | #购物单# 简单背包简单过

#include <iostream>
#include <vector>
using namespace std;
int n, m;
const int maxm = 100, maxn = 33000;
int ps[maxm], vs[maxm], qs[maxm];
int dp[maxn]; 
vector<int> slav[maxm]; // 每个主件可能的附件
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> vs[i] >> ps[i] >> qs[i];
        if (qs[i]) { // 附件
            slav[qs[i]].push_back(i); // 主:附
            // cout << qs[i] << ":"<<i<<endl;
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = n; j >= vs[i]; --j) {
            if (qs[i]) continue; // 附件不考虑,再对应主件中考虑
            dp[j] = max(dp[j], dp[j - vs[i]] + vs[i] * ps[i]); // 只买主件
            if (slav[i].size() >= 1) { // 1个附件
                int k = slav[i][0];
                if (j >= vs[i] + vs[k])
                    dp[j] = max(dp[j], dp[j - vs[i] - vs[k]]  // 主件+附件1
                        + vs[i] * ps[i] + vs[k] * ps[k]);
            } 
            if (slav[i].size() == 2) { // 2个附件
                int k = slav[i][1];
                if (j >= vs[i] + vs[k])
                    dp[j] = max(dp[j], dp[j - vs[i] - vs[k]]  // 主件+附件2
                        + vs[i] * ps[i] + vs[k] * ps[k]);
                int t = slav[i][0];
                if (j >= vs[i] + vs[k] + vs[t]) // 主件+附件1+附件2
                    dp[j] = max(dp[j], dp[j - vs[i] - vs[k] - vs[t]]  
                        + vs[i] * ps[i] + vs[k] * ps[k] + vs[t] * ps[t]);
            } 
        } 
    }
    cout << dp[n];
    return 0;
}
// 64 位输出请用 printf("%lld")