题解 | #购物单#

写完这题感觉自己是个“大聪明”。甚至还气的发了个报错反馈。。这波写了注释都可以敲错代码，更新函数写了个i-1然后死活过不了。真是尬死了。

然后，到了我们的题解环节

首先根据题目可以发现这是一个经过改编的01背包问题，做完这道题相信小伙伴们也和纳西妲一样能够对动态规划有了更深入的理解（应用算法模板）。

由于在选物品时有区分主件、附件，因此在物品大小（价格）和物品价值（重要性）上我选择用二维数组存放，将附件绑定到主件所在的行上，这样一来无论是写代码时还是思考问题时都显得比较直观。

输入

为了让我们的算法看起来比较直观，在输入时应当做好处理，建立大小为（m+1,3)的数组，m+1行是为了将下标与物品序号对齐，3列则是一个主件我们根据题目发现最多也就2个附件（1+2）。为了让整体占用空间较小将价格方面的数据统一缩小10倍，这样以来在动态规划算法进行时会比较快。（循环次数缩小10倍！）

动态规划

相较于传统01背包问题，这道题需要多加几个特殊条件：

• 只取主件而不取其附件
• 取主件和该主件对应的附件1
• 取主件和该主件对应的附件2
• 取出一套

下面直接上代码吧（反正写的时候就把思路写在代码里了。。所以感觉直接看代码也没啥问题）

#include <vector>
#include <iostream>

using namespace std;

int main() { //解法的前提是每件物品只能买一次，否则会出现数据遗漏覆盖
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, m;
    cin >> N >> m;
    N /= 10; // 王强查到了每件物品的价格（都是 10 元的整数倍）
    // price[主件][附件]
    vector<vector<int>> price(m + 1, vector<int>(3,
                              0)); // 构建商品（及其附件）价格数组，并初始化为0
    vector<vector<int>> value(m + 1, vector<int>(3,
                              0)); // 构建商品（及其附件）重要度数组，初始化为0
    for (int i = 1; i <= m; i++) {
        int v, p, q;
        cin >> v >> p >> q;
        // 当该物品为主件时
        if (q == 0) {
            price[i][0] = v / 10;// 价格同步缩小十倍
            value[i][0] = p;
        }
        // 当物品为附件时
        else {
            // 主件q是否已经有一个附件
            // 如果有,则该输入为主件q的第二个附件的值
            if (price[q][1] != 0) {
                price[q][2] = v / 10;
                value[q][2] = p;
            } else { //没有则为主件q的第一个附件
                price[q][1] = v / 10;
                value[q][1] = p;
            }
        }
    }
    /*
    -------------------------动态规划--------------------------------------------------
    */
    vector<vector<int>> dp(m + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= m; i++) {//取件数
        for (int j = 1; j <= N; j++) {//背包大小（金额预算）
            int p = price[i][0], v = value[i][0];
            int p1 = price[i][1], v1 = value[i][1];
            int p2 = price[i][2], v2 = value[i][2];
            // 分四种情况讨论：（在第一轮比较中就与历史值进行比较，因此后续更新状态只需和当前状态dp[i][j]比较即可）
            // 1、只买主件,只有买了主件才有后续买附件(更新参数：dp[i-1][j-p]+p*v)
            if (j >= p) {//预算足够时
                dp[i][j] = max(dp[i - 1][j - p] + p * v, dp[i - 1][j]);
            } else dp[i][j] = dp[i - 1][j];
            // 2、买主件和其附件1（更新参数：dp[i-1][j-p-p1]+p*v+p1*v1）
            if (j >= p + p1) {
                dp[i][j] = max(dp[i - 1][j - p - p1] + p * v + p1 * v1, dp[i][j]);
            } else dp[i][j] = dp[i][j];
            // 3、买主件和其附件2（更新参数：dp[i-1][j-p-p2]+p*v+p2*v2）
            if (j >= p + p2) {
                dp[i][j] = max(dp[i - 1][j - p - p2] + p * v + p2 * v2, dp[i][j]);
            } else dp[i][j] = dp[i][j];
            // 4、买全套（更新参数：dp[i-1][j-p-p1-p2]+p*v+p1*v1+p2*v2）
            if (j >= p + p1 + p2) {
                dp[i][j] = max(dp[i - 1][j - p - p1 - p2] + p * v + p1 * v1 + p2 * v2,
                               dp[i][j]);
            } else dp[i][j] = dp[i][j];
        }
    }

    cout << dp[m][N] * 10 << endl;
    return 0;
}