出题者觉得0/1背包太套路了,因此给我们使了点小绊子,但是问题不大。
设主件个数为n,奖金数量为M,每个主件对应的价格为v,每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取,奖金数量为j的情况下,所获得的最大价格*重要程度
累加和。另外注意到一个小细节:每个主件只能有0~2个附件,最多才4种搭配方式(00,01,10,11),得到如下状态公式:
- 如果
j>=v[i-1]
,那么dp[i][j] = max(dp[i][j-v[i-1]]+v[i-1]*w[i-1], dp[i-1][j], ➜➜➜➜)
(➜➜➜➜
表示有附件的情况,为了简化问题,我们把它放到下面讲) - 如果
j<v[i-1]
,那么dp[i][j] = dp[i-1][j]
- 基准1:
dp[0][..]=0
- 基准2:
dp[..][0]=0
对于状态公式的解释:
- 如果总奖金数能涵盖当前物品,那么选取包含当前物品和不包含当前物品两种情况下最大的累加和
- 如果总奖金数不能涵盖当前物品,那么直接取前
i-1
个物品的最大累加和 - 基准1: 商品个数为0,再怎么加也是0
- 基准2: 总奖金数为0,同样再怎么加也是0
其实上面的这些,除了➜➜➜➜
之外的其他部分,和0/1背包问题完全一致,接下来我们分析➜➜➜➜
:
- 如果没有附件,则跳过
- 如果附件数为1,且总奖金容得下附件,那么取最大值
- 如果附件数为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; }