华为OD机试统一考试 - 虚拟理财游戏
题目描述
在一款虚拟游戏中生活,你必须进行投资以增强在虚拟游戏中的资产以免被淘汰出局。
现有一家Bank,它提供有若干理财产品 m 个,风险及投资回报不同,你有 N(元)进行投资,能接收的总风险值为X。
你要在可接受范围内选择最优的投资方式获得最大回报。
备注:
- 在虚拟游戏中,每项投资风险值相加为总风险值;
- 在虚拟游戏中,最多只能投资2个理财产品;
- 在虚拟游戏中,最小单位为整数,不能拆分为小数;
- 投资额*回报率=投资回报
输入描述
第一行:
- 产品数(取值范围[1,20])
- 总投资额(整数,取值范围[1, 10000])
- 可接受的总风险(整数,取值范围[1,200])
第二行:产品投资回报率序列,输入为整数,取值范围[1,60]
第三行:产品风险值序列,输入为整数,取值范围[1, 100]
第四行:最大投资额度序列,输入为整数,取值范围[1, 10000]
输出描述
每个产品的投资额序列
用例
输入 | 5 100 10 10 20 30 40 50 3 4 5 6 10 20 30 20 40 30 |
输出 | 0 30 0 40 0 |
说明 | 投资第二项30个单位,第四项40个单位,总的投资风险为两项相加为4+6=10 |
题目解析
第一眼看这题有点像二维费用背包,但是本题备注中有一个关键限制:
在虚拟游戏中,最多只能投资2个理财产品;
那么本题其实就变成了:m个理财产品中选1个或2个,所选产品风险值之和 ≤ x,投资额之和 ≤ n,并且最终所选产品的投资回报之和最大。
由于 m 的数量级不大,取值范围[1,20],因此可以考虑暴力破解。
import Foundation func ODTest_7() { print("第一行:") print("产品数(取值范围[1,20])") print("总投资额(整数,取值范围[1, 10000])") print("可接受的总风险(整数,取值范围[1,200])") let tmp = readLine()?.split(separator: " ").map { Int($0) ?? 0 } ?? [] let m = tmp[0] // 产品数 let n = tmp[1] // 总投资 let x = tmp[2] // 总风险 print("第二行:产品投资回报率序列,输入为整数,取值范围[1,60]") // 产品回报率序列 let back = readLine()?.split(separator: " ").map { Int($0) ?? 0 } ?? [] print("第三行:产品风险值序列,输入为整数,取值范围[1, 100]") // 产品风险值序列 let risk = readLine()?.split(separator: " ").map { Int($0) ?? 0 } ?? [] print("第四行:最大投资额度序列,输入为整数,取值范围[1, 10000]") // 产品投资额序列 let invest = readLine()?.split(separator: " ").map { Int($0) ?? 0 } ?? [] var max_invest_back = 0 var select: [Int: Int] = [:] for i in 0 ..< m { // 如果单个产品的投资风险未超过总风险,则投资单个产品 if risk[i] <= x { // 产品I的投资额不能超过该产品的最大投资额,以及总投资 let investI = min(invest[i], n) // 产品投资回报 let invest_back = investI * back[i] // 如果投资回报高于其他产品组合,那么选择该产品 if invest_back > max_invest_back { max_invest_back = invest_back select.removeAll() select[i] = invest_back } } else { continue } for j in (i + 1) ..< m { // 如果两个产品的风险和不超过了总风险,那么两个产品都选 if risk[i] + risk[j] <= x { // 产品I的投资额 var investI = 0 // 产品J的投资额 var investJ = 0 // 其中优先投资回报率大的 if back[i] > back[j] { // 产品I回报率高,则能投多少投多少,最多不能超过min(总投资, 产品I的最多投资额) investI = min(n, invest[i]) // 留给产品J的剩余钱未 n - investI, 而产品J最多投资invest[j],因此取二者较小值 investJ = min(n - investI, invest[j]) } else { investJ = min(n, invest[j]) investI = min(n - investJ, invest[i]) } // 总投资回报 let invest_back = investI * back[i] + investJ * back[j] // 如果当前产品组合的总回报更大,则选当前组合产品 if invest_back > max_invest_back { max_invest_back = invest_back select.removeAll() // select的key记录产品的ID,val记录产品的投资额 if investI > 0 { select[i] = investI } if investJ > 0 { select[j] = investJ } } } } } var result = "" for i in 0 ..< m { if select.keys.contains(i) { result += "\(select[i] ?? 0)" } else { result += "0" } result += " " } print("输出描述") print(result) }
2024华为OD机试卷题 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。