这是一道难度标记为: 普及+/提高 的题目，主要考察了 背包问题。

仔细看看，这道题和开心的金明很相似（开心的金明为01背包问题）

但这道题增加了主物件这一设定，如果不买主物件，附属品都无法购买！

说白了就是一道依赖背包问题！

一样物品最多能出现2个附属品，这样就好办了，五种可能性：

1. 啥都不买。
2. 只买主件。
3. 买主件和附属品1
4. 买主件和附属品2
5. 全都买。

只需要将 01背包代码 改一下就能做这道题了。

解题步骤

全局变量定义

typedef pair<int, int> pai; // 附属物品的两个值

struct node
{
    int value;         // 价值数
    int prior;         // 优先级
    vector<pai> auxil; // 附属物
} a[MAXN];

int f[MAXN]; // dp 数组

使用 自定义结构体 + Pair 储存数据非常简洁（不喜欢太多数组）
另外最好把 Vector 改成普通数组，毕竟只有两个附属品。

数据输入

int n, m;

cin >> n >> m;

for (int i = 1; i <= m; i++)
{
    int v, p, q;
    cin >> v >> p >> q;

    if (!q)
    {
        a[i].value = v;
        a[i].prior = v * p;
    }
    else
    {
        a[q].auxil.push_back(make_pair(v, v * p));
    }
}

前面的都很简单，后面的判断主要用于检查是否为附属品，如果是附属品则放到主件的 auxil 下，这样最终遍历时只需要遍历主件。使用 Pair 存放附属品值，非常的方便！

状态转移方程式

// 只购买主件
f[j] = max(f[j], f[j - a[i].value] + a[i].prior);

// 主件 + 附属品1
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first)] + a[i].prior + a[i].auxil[0].second);

// 主件 + 附属品2
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[1].second);

// 主件 + 附属品1 + 附属品2
f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[0].second + a[i].auxil[1].second);

在写转移方程式前注意判断剩余金额和附属品是否存在的问题。

完整代码

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

#define MAXN 100001

typedef pair<int, int> pai;

struct node
{
    int value;         // 价值数
    int prior;         // 优先级
    vector<pai> auxil; // 附属值
} a[MAXN];

int f[MAXN];

int main(int argc, char const *argv[])
{
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int v, p, q;
        cin >> v >> p >> q;

        if (!q)
        {
            a[i].value = v;
            a[i].prior = v * p;
        }
        else
        {
            a[q].auxil.push_back(make_pair(v, v * p));
        }
    }

    for (int i = 1; i <= m; i++)
    {
        for (int j = n; j >= 0; j--)
        {
            if (j >= a[i].value)
            {
                f[j] = max(f[j], f[j - a[i].value] + a[i].prior);
            }

            if (a[i].auxil.size() >= 1)
            {
                if (j >= (a[i].value + a[i].auxil[0].first))
                {
                    f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first)] + a[i].prior + a[i].auxil[0].second);
                }
            }

            if (a[i].auxil.size() >= 2)
            {
                if (j >= (a[i].value + a[i].auxil[1].first))
                {
                    f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[1].second);
                }
            }

            if (a[i].auxil.size() >= 2)
            {
                if (j >= (a[i].value + a[i].auxil[0].first + a[i].auxil[1].first))
                {
                    f[j] = max(f[j], f[j - (a[i].value + a[i].auxil[0].first + a[i].auxil[1].first)] + a[i].prior + a[i].auxil[0].second + a[i].auxil[1].second);
                }
            }
        }
    }

    cout << f[n] << endl;

    return 0;
}