商城双11大促销 - 华为机试真题题解

本文主要是介绍商城双11大促销 - 华为机试真题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考试平台：时习知

分值： 300分（第三题）

考试时间：两小时（共3题）

alt

题目描述

商城双11大促销，每种商品限购两件。一共有M种商品。每种商品的原始价格为X元。

买一件折扣价是Y元，买两件折扣价是Z元。其中X>=Y>=Z。

小明银行卡里有余额N元。在N元的范围内怎么购买商品才可以获得最多的优惠金额?

输入

第1行: 商品种类M，M的范围是[1-20]。

第2到M+1行: 每个商品的原始价格X元，购买一件的折扣价Y元，购买两件的折扣价Z元。X、Y、Z的范围是[1-1000]。

第M+2行: 小明银行卡余额N元。N的范围是[1-20000]，N元至少可以购买一件商品。

输出

输出可以获得的最多优惠金额

示例1

输入：
2
10 8 6
8 6 6
20输出：
10解释： 
第一个商品买2件，第二个商品买1件。总共花费2*6+6=18元在20元范围内。第一件商品优惠8元(2件)，第二件商品优惠2元(1件)。总共优惠10元。

示例2

输入：
3
10 8 4
20 17 13
30 20 10
50输出：
55解释： 
第一个商品买2件，第二个商品买1件第三个商品买2件。总共花费 24+17+210=41元在50元范围内。
第一件商品优惠12元(2件)，第二件商品优惠3元(1件)，第三件商品优惠40元(2件)，总共优惠55元。

题解

这段 C++ 代码使用了动态规划的方法解决了问题。以下是对代码的一些解释：

X[i] 表示第 i 种商品的原价，Y[i] 表示购买一件的折扣价，Z[i] 表示购买两件的折扣价。
dp[i][j] 表示前 i 种商品花费不超过 j 元所能获得的最大优惠金额。
通过双重循环遍历商品和银行卡余额，使用状态转移方程更新 dp[i][j] 的值。
最后输出 dp[M][N] 即为问题的答案。

这个问题是一个典型的动态规划问题，利用动态规划的思想，通过填表的方式计算出最优解。

在这个过程中，需要考虑当前商品购买一件和购买两件的情况，以及与之前的状态之间的关系。

算法的时间复杂度为 O(M * N)，其中 M 为商品种类，N 为小明的银行卡余额。

C++

#include <algorithm>
#include <iostream>
#include <vector>using namespace std;int main()
{int M;   // 商品种类cin >> M;// 原价，购买一件的折扣价，购买两件的折扣价vector<int> X(M), Y(M), Z(M);for (int i = 0; i < M; ++i) {cin >> X[i] >> Y[i] >> Z[i];}int N;   // 银行卡余额cin >> N;// dp[i][j]表示前i个商品，花费不超过j元所能获得的最大优惠金额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) {// 不购买当前商品dp[i][j] = dp[i - 1][j];// 购买一件当前商品if (j >= Y[i - 1]) {int discount = X[i - 1] - Y[i - 1];   // 原价 - 优惠价 = 优惠金额dp[i][j]     = max(dp[i][j], dp[i - 1][j - Y[i - 1]] + discount);}// 购买两件当前商品if (j >= 2 * Z[i - 1]) {int discount = (X[i - 1] - Z[i - 1]) * 2;dp[i][j]     = max(dp[i][j], dp[i - 1][j - 2 * Z[i - 1]] + discount);}}}cout << dp[M][N] << endl;return 0;
}