华为OD机试真题汇总目录
【华为OD机试】真题汇总A+B+C+D券（Python实现）
一、题目
题目描述：
双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而且想尽可能的花完资金。
现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。
二、输入输出
输入描述:
输入第一行为一维整型数组M，数组长度小于100，数组元素记录单个商品的价格，单个商品价格小于1000。输入第二行为购买资金的额度R，R小于100000。
输出描述:
输出为满足上述条件的最大花费额度。
注意：
如果不存在满足上述条件的商品，请返回-1。
三、示例
示例1:
输入输出示例仅供调试，后台判题数据一般不包含示例
输入:
23,26,36,27
78
输出:
76
说明:
金额23、26和27相加得到76，而且最接近且小于输入金额78。
示例2:
输入输出示例仅供调试，后台判题数据一般不包含示例
输入:
23,30,40
26
输出:
-1
说明:
因为输入的商品，无法组合出来满足三件之和小于26.故返回-1。
备注:
输入格式是正确的，无需考虑格式错误的情况。
四、解题思路
- 读取输入的商品名称和目标金额。
- 将商品名称分割存储到
items向量中。- 生成所有可能的三个商品组合。
- 遍历所有组合，计算总费用，找到不超过目标金额的最大总费用。
- 如果找到总费用等于目标金额的组合，直接返回目标金额。
- 如果没有找到等于目标金额的组合，返回不超过目标金额的最大总费用，如果没有找到符合条件的组合，则返回 -1。
五、参考代码
/*
* @#coding: utf-8
* @Author: mgc
* @Date: 2024-02-02 17:47:00
* @LastEditors: Do not edit
* @LastEditTime: 2024-02-02 17:48:55
*/
// #include<set>
// #include<map>
// #include<list>
// #include<regex>
// #include<cmath>
// #include<queue>
// #include<stack>
// #include<bitset>
// #include<utility>
// #include<stdlib.h>
// #include<string.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
// 寻找最大总费用
int findMaxTotalCost() {
string inputLine;
getline(cin, inputLine);
int targetMoney;
cin >> targetMoney;
int maxCost = 0;
vector<string> items;
string item;
stringstream ss(inputLine);
// 将输入的商品名称存储到 items 向量中
while (getline(ss, item, ',')) {
items.push_back(item);
}
vector<vector<string>> cases;
sort(items.begin(), items.end());
// 生成所有可能的组合
do {
cases.push_back({items[0], items[1], items[2]});
} while (next_permutation(items.begin(), items.end()));
// 遍历所有组合，计算总费用，找到不超过目标金额的最大总费用
for (auto case_ : cases) {
int totalCost = stoi(case_[0]) + stoi(case_[1]) + stoi(case_[2]);
if (totalCost == targetMoney) {
return targetMoney;
}
if (targetMoney > totalCost && totalCost > maxCost) {
maxCost = totalCost;
}
}
// 返回结果
if (maxCost == 0) {
return -1;
} else {
return maxCost;
}
}
int main() {
int totalCost = findMaxTotalCost();
cout << totalCost << endl;
return 0;
}