题解 | #购物单#

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int N, m; // N为总钱数，m为总物品数
    cin >> N >> m;
    int v[m];    // 记录物品价格
    int w[m];    // 记录物品重要度
    int type[m]; // 记录物品主附属性
    int t;
    // 读取物品信息,i+1为该物品的编号
    for (int i = 0; i < m; i++) {
        cin >> v[i] >> w[i] >> t;
        type[i] = t - 1; // 将编号转化为数组下标
    }

    vector<vector<int>> vmap(61, vector<int>(4,
                             0)); // 记录主键4种情况所需的价格
    vector<vector<int>> wmap(61, vector<int>(4,
                             0)); // 记录主键4种情况所给予的重要度


    for (int i = 0; i < m; i++) {
        // 若为主键
        if (type[i] == -1) {
            // 初始化第一种情况——只有主键
            vmap[i][0] = v[i];
            wmap[i][0] = v[i] * w[i];
            for (int j = 0; j < m; j++) {
                // 检索到附件
                if (type[j] == i) {
                    // 第一次检索到附件
                    if (vmap[i][1] == 0) {
                        vmap[i][1] = vmap[i][0] + v[j];
                        wmap[i][1] = wmap[i][0] + v[j] * w[j];
                    }
                    // 第二次检索到附件
                    else {
                        vmap[i][2] = vmap[i][0] + v[j];
                        wmap[i][2] = wmap[i][0] + v[j] * w[j];

                        vmap[i][3] = vmap[i][1] + v[j];
                        wmap[i][3] = wmap[i][1] + v[j] * w[j];
                    }
                }
            }
        }
    }

    // 创建动态规划数组
    vector<vector<int>> dp(m + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 1; j < N + 1; j++) {

            //初始化第一行
            if (i == 0 ) {
                dp[i][j] = j >= vmap[i][0] ? wmap[i][0] : 0;
                dp[i][j] = j >= vmap[i][1] ? max(wmap[i][1], dp[i][j]) : dp[i][j];
                dp[i][j] = j >= vmap[i][2] ? max(wmap[i][2], dp[i][j]) : dp[i][j];
                dp[i][j] = j >= vmap[i][3] ? max(wmap[i][3], dp[i][j]) : dp[i][j];
            }

            if (i != 0 ) {
                dp[i][j] = j >= vmap[i][0] ? max(dp[i - 1][j],
                                                 dp[i - 1][j - vmap[i][0]] + wmap[i][0]) : dp[i - 1][j];
                dp[i][j] = j >= vmap[i][1] ? max(dp[i][j],
                                                 dp[i - 1][j - vmap[i][1]] + wmap[i][1]) : dp[i][j];
                dp[i][j] = j >= vmap[i][2] ? max(dp[i][j],
                                                 dp[i - 1][j - vmap[i][2]] + wmap[i][2]) : dp[i][j];
                dp[i][j] = j >= vmap[i][3] ? max(dp[i][j],
                                                 dp[i - 1][j - vmap[i][3]] + wmap[i][3]) : dp[i][j];

            }
        }
    }
    cout << dp[m - 1][N] << endl;
}

01背包问题的变种。

贴上01背包问题的笔记：

1 背包算法

概述

1.1 01背包算法

1.1.1 概述：

• 有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
• 若使用暴力解法回溯，对于每种物品有放与不放2种状态，n个物品时间复杂度为2^n

1.1.2 dp数组的含义:

• dp[i][j] 下标为[0,i]的物品任取，放进容量为j的背包里，所能达到的最大价值
• 不放物品i， 背包容量为j，它所能装下物品的最大价值为dp[i-1][j]
• 放一个物品i后，背包价值计算为dp[i-1][j-weight[i]] + value[i]
• dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])从放物品i与不放物品i中选择最大的那个，作为dp[i][j]的值

1.1.3 dp数组表格如何初始化：

• 一个元素，依赖于其正上方与左上方的元素，先初始化第一行与第一列
• 非零下标任意初始化，不影响

1.1.4 遍历顺序：

• 一般情况，两层for，外层遍历物品，第二层遍历背包容量，内部写dp公式 但是对于2维dp的两层for循环其实是可以颠倒的（满足上方和左上方有数据）

对于本问题，主要是分清楚每次放什么，对于附件不考虑单独情况，只考虑主件，对于每个主件最多有2个附件，一共4种情况：不带附件、带附件1、带附件2、带全部附件；对于每种情况选择最佳并且符合钱包的答案即可。提前计算一些数据，比如价格和价值存入数组中，方便dp时使用。

题目看了好久才看懂）