AcWing 487 金明的预算方案

题目传送门
算法
(\(DP\),分组背包问题)
可以将每个主件及其附件看作一个物品组，记主件为 \(p\)，两个附件为 \(a\),\(b\),则最多一共有\(4\)种组合：

\(p\)
\(p\),\(a\)
\(p\),\(b\)
\(p\),\(a\),\(b\)
这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作一个物品，那么问题就变成了分组背包问题。可以参考\(AcWing\) \(9\). 分组背包问题。

在枚举四种组合时可以使用二进制的思想，可以简化代码。

#include <bits/stdc++.h>

using namespace std;
const int N = 70;       //希望购买物品的个数上限
const int M = 32010;    //总钱数上限

//描述每个物品的结构体
struct Node {
    int v;//体积
    int w;//价值
};
int n;                      //希望购买物品的个数
int m;                      //总钱数
Node a[N];                  //主物品数组
vector<Node> g[N];          //二维的数组，第一维是主件的号码，第二维是它的附件有哪些
//要理解清楚a和g的内容，a是主物品结构体数组，g是以主物品号为索引，内容是一个变长的物品结构体数组
int f[M];                   //一维的分组背包DP数组

int main() {
    cin >> m >> n;
    //读入每一个物品
    for (int i = 1; i <= n; i++) {
        /*
        v表示i物品的价格，p表示i物品的重要度（1~5）。
        q表示i物品是主件还是附件。如果q=0，表示该物品为主件，
        如果q>0，表示该物品为附件，q是所属主件的编号:parent_id概念
        */
        int v, p, q;
        cin >> v >> p >> q;
        p *= v;//使每件物品的价格与重要度的乘积的总和最大
        //i是主件
        if (!q) a[i] = {v, p};
            //i是附件,需记录到主件与附件的关系数组中去
        else g[q].push_back({v, p});
    }
    //分组背包+二进制组合表示
    for (int i = 1; i <= n; i++)//遍历每一个物品
        //一维分组背包的倒序，遍历每一个可能的体积
        for (int j = m; j >= 0; j--)
            //遍历每一个可能的组合方式
            //(1)p:00  (2) pa:10 (3)pb:01 (4) pab:11
            //枚举附件的所有二进制状态模拟形式：
            for (int k = 0; k < 1 << g[i].size(); k++) {
                //初始值是主件的体积和价值
                int v = a[i].v, w = a[i].w;
                //遍历二进制的每一位
                for (int x = 0; x < g[i].size(); x++)
                    if (k >> x & 1) {//当前二进制数此位置为1
                        v += g[i][x].v;
                        w += g[i][x].w;
                    }
                //如果可能装的下，参与打擂台
                if (j >= v) f[j] = max(f[j], f[j - v] + w);
            }
    //输出结果
    printf("%d\n", f[m]);
    return 0;
}