题解 | #购物单#

#include <iostream>
#include <vector>
using namespace std;

/***
买附件，必须买主件
主件有0,1,2个附件。

每件的价格是10n，预算为N；每个物品的重要度[1, 5]
满意度： 价格与重要度的乘积的综合。
*/
int main() {
    int N, m;
    cin >> N >> m;

    vector<int> v(m + 1);
    vector<int> p(m + 1);
    vector<int> q(m + 1);
    vector<bool> flag(m + 1, false);    // 记录那些主件有附件
    for (int i = 1; i <= m; i++) {
        cin >> v[i] >> p[i] >> q[i];
        if (q[i] != 0) {
            flag[q[i]] = true;
        }
    }

    vector<int> f(N + 1, -0x7f7f7f7f);
    f[0] = 0;
    for (int i = 1; i <= m; i++) {
        // 附件不单独处理
        if (q[i] != 0) continue;
        
        // 对主件的子背包进行处理
        if (flag[i]) {
            int i_cnt = 0;
            int i_v = 0;
            vector<int> i_sub;
            for (int k = 1; k <= m; k++) {
                if (q[k] == i) {
                    i_sub.push_back(k);
                    i_cnt++;
                    i_v += v[k];
                }
            }

            i_v = min(N - v[i], i_v);
            vector<int> f_sub(i_v + 1, -0x7f7f7f);    // f_sub的个数是值域
            f_sub[0] = 0;

            for (int j = 0; j < i_cnt; j++) {
                for (int k = i_v; k >= v[i_sub[j]]; k--) {
                    f_sub[k] = max(f_sub[k], f_sub[k - v[i_sub[j]]] + v[i_sub[j]] * p[i_sub[j]]);
                    // if(f_sub[k] > 0){
                    //     printf("i_v:%d, j:%d, k:%d, f_sub[k-v[j]]:%d, add:%d, f[new]:%d\n",
                    //     i_v, i_sub[j], k, f_sub[k - v[i_sub[j]]], v[i_sub[j]] * p[i_sub[j]], f_sub[k]);
                    // }
                }
            }
            
		  	// 主件进行背包，并将主件的副件的子背包嵌入
            for (int j = N; j >= v[i]; j--) {
                // 处理主件
                f[j] = max(f[j], f[j - v[i]] + v[i] * p[i]);
                // if (f[j] > 0) {
                //     printf("i:%d, j:%d, f[j-v[i]]:%d, add:%d, f[j]:%d\n", i, j, f[j - v[i]], v[i] * p[i], f[j]);
                // }
                
                // 将子背包与父件合并，并同步至父背包
                for (int k = 0; k <= i_v; k++) {
                    if (f_sub[k] > 0 && j - v[i] - k >= 0) {
                        f[j] = max(f[j], f[j - v[i] - k] + f_sub[k] + v[i] * p[i]);
                        // if(f[j] > 0){
                        //     printf("merge, j:%d, k:%d, f[j-v[i]-k]:%d, add:%d, f[j]:%d\n", j, k, f[j - v[i] - k],
                        //     f_sub[k] + v[i] * p[i], f[j]);
                        // }
                    }
                }
            }            

        }
	  	// 对没有子件的背包进行处理
        else{
            for (int j = N; j >= v[i]; j--) {
                f[j] = max(f[j], f[j - v[i]] + v[i] * p[i]);
                // if (f[j] > 0) {
                //     printf("nosub_i:%d, j:%d, f[j-v[i]]:%d, add:%d, f[j]:%d\n", i, j, f[j - v[i]], v[i] * p[i], f[j]);
                // }
            }            
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (f[i] > ans) ans = f[i];
    }
    cout << ans << endl;
    return 0;
}

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