题解 | #购物单# c++ 背包问题

#include <iostream>
#include<vector>
using namespace std;
int money[32000], v[60], p[60], q[60], value[60][4], p1[60][4], q1[60];
int main() {
    int N = 0, m = 0;
    cin >> N >> m;

    for (int i = 1; i <= m; i++) {//先记录主件的价格和满意度
        cin >> v[i] >> p[i] >> q[i];
        if (q[i] == 0) {
            value[i][0] = v[i];
            p1[i][0] = v[i] * p[i];
        } 
    }
        for(int i=1;i<=m;i++){//记录附件与主件组合的价格和满意度
                if(q[i]!=0) {
            q1[q[i]]++;
            if (q1[q[i]] < 2) {//第一个附件与主件组合的价格和满意度
                value[q[i]][q1[q[i]]] = v[i] + value[q[i]][0];
                p1[q[i]][q1[q[i]]] = p[i] * v[i] + p1[q[i]][0];
            } else if(q1[q[i]]==2){
                value[q[i]][q1[q[i]]] = v[i] + value[q[i]][0];  //第二个附件与主件组合的价格和满意度
                p1[q[i]][q1[q[i]]] = p[i] * v[i] + p1[q[i]][0];
                value[q[i]][q1[q[i]] + 1] = v[i] + value[q[i]][1]; //第一个和第二个附件与主件组合的价格和满意度
                p1[q[i]][q1[q[i]] + 1] = p[i] * v[i] + p1[q[i]][1];
            }
        }
    }
    for (int i = 1; i <= m; i++) {//分组背包问题
        for (int j = N; j >= 0; j--) {
            for (int k = 0; k < 4&&value[i][k]!=0; k++) {
             if(value[i][k]<=j){
               money[j]=money[j]>money[j-value[i][k]]+p1[i][k]?money[j]:money[j-value[i][k]]+p1[i][k];
             }
            }
        }
    }
    cout << money[N];
    return 0;
}

// 64 位输出请用 printf("%lld")