购物单（背包问题）

出题者觉得0/1背包太套路了，因此给我们使了点小绊子，但是问题不大。

设主件个数为n，奖金数量为M，每个主件对应的价格为v，每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有0～2个附件，最多才4种搭配方式(00,01,10,11)，得到如下状态公式：

1. 如果j>=v[i-1]，那么dp[i][j] = max(dp[i][j-v[i-1]]+v[i-1]*w[i-1], dp[i-1][j], ➜➜➜➜)（➜➜➜➜表示有附件的情况，为了简化问题，我们把它放到下面讲）
2. 如果j<v[i-1]，那么dp[i][j] = dp[i-1][j]
3. 基准1: dp[0][..]=0
4. 基准2: dp[..][0]=0

对于状态公式的解释：

1. 如果总奖金数能涵盖当前物品，那么选取包含当前物品和不包含当前物品两种情况下最大的累加和
2. 如果总奖金数不能涵盖当前物品，那么直接取前i-1个物品的最大累加和
3. 基准1: 商品个数为0，再怎么加也是0
4. 基准2: 总奖金数为0，同样再怎么加也是0

其实上面的这些，除了➜➜➜➜之外的其他部分，和0/1背包问题完全一致，接下来我们分析➜➜➜➜:

1. 如果没有附件，则跳过
2. 如果附件数为1，且总奖金容得下附件，那么取最大值
3. 如果附件数为2...

通过合理构建数组，可以大大简化代码，并且提高运行效率。如下面的代码中，我们预先为prices和priceMultiplyPriority两个矩阵开辟了空间。

代码如下：

//
// Created by jt on 2020/9/5.
// 题目来源：华为机试——牛客HJ16——购物单
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    // 由于价格是10的整数倍，处理一下以降低空间/时间复杂度
    N /= 10;
    vector<vector<int> > prices(61, vector<int>(3, 0));        // 价格
    vector<vector<int> > priceMultiplyPriority(61, vector<int>(3, 0));      // 重要程度
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a /= 10; b *= a;
        if (c == 0) {
            prices[i][0] = a; priceMultiplyPriority[i][0] = b;
        } else {
            if (prices[c][1] == 0) {
                prices[c][1] = a; priceMultiplyPriority[c][1] = b;
            } else {
                prices[c][2] = a; priceMultiplyPriority[c][2] = b;
            }
        }
    }
    // 使用分组背包
    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 a = prices[i][0], b = priceMultiplyPriority[i][0];
            int c = prices[i][1], d = priceMultiplyPriority[i][1];
            int e = prices[i][2], f = priceMultiplyPriority[i][2];
            dp[i][j] = j >= a ? max(dp[i-1][j-a] + b, dp[i-1][j]) : dp[i-1][j];
            dp[i][j] = j >= (a+c) ? max(dp[i-1][j-a-c] + b + d, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+e) ? max(dp[i-1][j-a-e] + b + f, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+c+e) ? max(dp[i-1][j-a-c-e] + b + d + f, dp[i][j]) : dp[i][j];
        }
    }
    cout << dp[m][N] * 10 << endl;
}