华为OD机试 - 虚拟理财游戏 - 贪心算法（Python/JS/C/C++ 2024 D卷 200分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
在一款虚拟游戏中生活，你必须进行投资以增强在虚拟游戏中的资产以免被淘汰出局。现有一家 Bank，它提供有若干理财产品 m，风险及投资回报不同，你有 N（元）进行投资，能接受的总风险值为 X。
你要在可接受范围内选择最优的投资方式获得最大回报。
说明：
1、在虚拟游戏中，每项投资风险值相加为总风险值；
2、在虚拟游戏中，最多只能投资 2 个理财产品；
3、在虚拟游戏中，最小单位为整数，不能拆分为小数；
投资额*回报率=投资回报
二、输入描述
第一行：产品数(取值范围[1, 20])，总投资额(整数，取值范围[1, 10000])，可接受的总风险(整数，取值范围[1, 200])
第二行：产品投资回报率序列，输入为整数，取值范围[1,60]
第三行：产品风险值序列，输入为整数，取值范围[1,100]
第四行：最大投资额度序列，输入为整数，取值范围[1,10000]
三、输出描述
每个产品的投资额序列。
补充说明
1、在虚拟游戏中，每项投资风险值相加为总风险值；
2、在虚拟游戏中，最多只能投资 2 个理财产品；
3、在虚拟游戏中，最小单位为整数，不能拆分为小数；
投资额*回报率=投资回报
四、测试用例
测试用例1
1、输入
5 100 10
10 20 30 40 50
3 4 5 6 10
20 30 20 40 30
2、输出
0 30 0 40 0
3、说明
投资第二项 30 个单位，第四项 40 个单位，总的投资风险为两项相加为 4+6=10
测试用例2
1、输入
1 1000 100
50
100
1000
2、输出
1000
五、解题思路
这个问题可以看作是一个优化问题，目标是在给定的投资总额和风险限制内，选择最多两个理财产品以获得最大的回报。以下是解决该问题的详细步骤：
- 读取输入：
- 获取产品数量、总投资额、可接受的总风险。
- 获取每个产品的投资回报率、风险值和最大投资额度。
- 初始化变量：
- 初始化记录最大回报的变量 maxReturn。
- 初始化记录最小风险的变量 minRisk。
- 使用一个哈希表 bestInvestment 来记录最佳投资策略。
- 单个产品投资的处理：
- 遍历每个产品，检查单个产品的风险是否在可接受范围内。
- 计算该产品的实际投资额和投资回报。
- 如果该产品的投资回报高于当前记录的最大回报，或者在相同回报下风险更低，则更新最佳投资策略。
- 两个产品组合投资的处理：
- 遍历所有可能的产品组合（两个产品的组合）。
- 检查两个产品的总风险是否在可接受范围内。
- 根据回报率和风险值的不同情况，计算每个产品的实际投资额和组合投资回报。
- 如果该组合的投资回报高于当前记录的最大回报，或者在相同回报下风险更低，则更新最佳投资策略。
- 输出结果：
- 遍历所有产品，根据最佳投资策略生成最终的投资额度序列并输出。
六、Python算法源码
# 导入必要的库
import sys
from itertools import combinationsdef main():# 读取第一行输入：产品数，总投资额，可接受的总风险input_line = sys.stdin.readline().strip()while input_line == '':input_line = sys.stdin.readline().strip()product_count, total_investment, total_risk = map(int, input_line.split())# 读取第二行输入：产品投资回报率序列rates = list(map(int, sys.stdin.readline().strip().split()))# 读取第三行输入：产品风险值序列risks = list(map(int, sys.stdin.readline().strip().split()))# 读取第四行输入：产品最大投资额度序列max_investments = list(map(int, sys.stdin.readline().strip().split()))# 初始化最大回报和最小风险max_return = 0min_risk = float('inf')# 存储最佳投资策略best_investment = {}# 枚举所有可能的投资组合for i in range(product_count):# 单个产品投资if risks[i] <= total_risk:invest_i = min(max_investments[i], total_investment)return_i = invest_i * rates[i]if return_i > max_return or (return_i == max_return and risks[i] < min_risk):max_return = return_imin_risk = risks[i]best_investment = {i: invest_i}# 枚举与其他产品组合投资for j in range(i + 1, product_count):combined_risk = risks[i] + risks[j]if combined_risk <= total_risk:# 优先投资回报率高的产品if rates[i] > rates[j]:invest_first = min(max_investments[i], total_investment)invest_second = min(max_investments[j], total_investment - invest_first)elif rates[i] < rates[j]:invest_first = min(max_investments[j], total_investment)invest_second = min(max_investments[i], total_investment - invest_first)else:# 回报率相同，优先风险低的if risks[i] < risks[j]:invest_first = min(max_investments[i], total_investment)invest_second = min(max_investments[j], total_investment - invest_first)else:invest_first = min(max_investments[j], total_investment)invest_second = min(max_investments[i], total_investment - invest_first)total_return = invest_first * rates[i] + invest_second * rates[j]# 更新最佳投资策略if total_return > max_return or (total_return == max_return and combined_risk < min_risk):max_return = total_returnmin_risk = combined_riskbest_investment = {}if invest_first > 0:if rates[i] > rates[j]:best_investment[i] = invest_firstbest_investment[j] = invest_secondelse:best_investment[j] = invest_firstbest_investment[i] = invest_second# 构造输出结果result = []for i in range(product_count):result.append(str(best_investment.get(i, 0)))print(' '.join(result))if __name__ == "__main__":main()七、JavaScript算法源码
// 引入必要的模块
const readline = require('readline');// 创建接口用于读取输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let inputLines = [];
rl.on('line', (line) => {if (line.trim() === '') return;inputLines.push(line.trim());if (inputLines.length === 4) {rl.close();}
});rl.on('close', () => {// 解析第一行输入：产品数，总投资额，可接受的总风险const [productCount, totalInvestment, totalRisk] = inputLines[0].split(' ').map(Number);// 解析第二行输入：产品投资回报率序列const rates = inputLines[1].split(' ').map(Number);// 解析第三行输入：产品风险值序列const risks = inputLines[2].split(' ').map(Number);// 解析第四行输入：产品最大投资额度序列const maxInvestments = inputLines[3].split(' ').map(Number);// 初始化最大回报和最小风险let maxReturn = 0;let minRisk = Infinity;// 存储最佳投资策略let bestInvestment = {};// 枚举所有可能的投资组合for (let i = 0; i < productCount; i++) {// 单个产品投资if (risks[i] <= totalRisk) {let investI = Math.min(maxInvestments[i], totalInvestment);let returnI = investI * rates[i];if (returnI > maxReturn || (returnI === maxReturn && risks[i] < minRisk)) {maxReturn = returnI;minRisk = risks[i];bestInvestment = {};bestInvestment[i] = investI;}}// 枚举与其他产品组合投资for (let j = i + 1; j < productCount; j++) {let combinedRisk = risks[i] + risks[j];if (combinedRisk <= totalRisk) {let investFirst, investSecond;if (rates[i] > rates[j]) {investFirst = Math.min(maxInvestments[i], totalInvestment);investSecond = Math.min(maxInvestments[j], totalInvestment - investFirst);} else if (rates[i] < rates[j]) {investFirst = Math.min(maxInvestments[j], totalInvestment);investSecond = Math.min(maxInvestments[i], totalInvestment - investFirst);} else {// 回报率相同，优先风险低的if (risks[i] < risks[j]) {investFirst = Math.min(maxInvestments[i], totalInvestment);investSecond = Math.min(maxInvestments[j], totalInvestment - investFirst);} else {investFirst = Math.min(maxInvestments[j], totalInvestment);investSecond = Math.min(maxInvestments[i], totalInvestment - investFirst);}}let totalReturn = investFirst * rates[i] + investSecond * rates[j];// 更新最佳投资策略if (totalReturn > maxReturn || (totalReturn === maxReturn && combinedRisk < minRisk)) {maxReturn = totalReturn;minRisk = combinedRisk;bestInvestment = {};if (investFirst > 0) {if (rates[i] > rates[j]) {bestInvestment[i] = investFirst;bestInvestment[j] = investSecond;} else {bestInvestment[j] = investFirst;bestInvestment[i] = investSecond;}}}}}}// 构造输出结果let result = [];for (let i = 0; i < productCount; i++) {result.push(bestInvestment[i] || 0);}console.log(result.join(' '));
});八、C算法源码
#include <stdio.h>
#include <stdlib.h>// 定义最大产品数
#define MAX_PRODUCTS 20int main(){int productCount, totalInvestment, totalRisk;// 读取第一行输入：产品数，总投资额，可接受的总风险scanf("%d %d %d", &productCount, &totalInvestment, &totalRisk);int rates[MAX_PRODUCTS];// 读取第二行输入：产品投资回报率序列for(int i=0;i<productCount;i++) {scanf("%d", &rates[i]);}int risks[MAX_PRODUCTS];// 读取第三行输入：产品风险值序列for(int i=0;i<productCount;i++) {scanf("%d", &risks[i]);}int maxInvestments[MAX_PRODUCTS];// 读取第四行输入：产品最大投资额度序列for(int i=0;i<productCount;i++) {scanf("%d", &maxInvestments[i]);}// 初始化最大回报和最小风险long long maxReturn = 0;int minRisk = 1000000;// 存储最佳投资策略int bestInvestment[MAX_PRODUCTS];for(int i=0;i<productCount;i++) bestInvestment[i] = 0;// 枚举所有可能的投资组合for(int i=0;i<productCount;i++){// 单个产品投资if(risks[i] <= totalRisk){int investI = (maxInvestments[i] < totalInvestment) ? maxInvestments[i] : totalInvestment;long long returnI = (long long)investI * rates[i];if(returnI > maxReturn || (returnI == maxReturn && risks[i] < minRisk)){maxReturn = returnI;minRisk = risks[i];// 重置最佳投资for(int k=0;k<productCount;k++) bestInvestment[k] = 0;bestInvestment[i] = investI;}}// 枚举与其他产品组合投资for(int j=i+1;j<productCount;j++){int combinedRisk = risks[i] + risks[j];if(combinedRisk <= totalRisk){int investFirst, investSecond;if(rates[i] > rates[j]){investFirst = (maxInvestments[i] < totalInvestment) ? maxInvestments[i] : totalInvestment;investSecond = (maxInvestments[j] < (totalInvestment - investFirst)) ? maxInvestments[j] : (totalInvestment - investFirst);}else if(rates[i] < rates[j]){investFirst = (maxInvestments[j] < totalInvestment) ? maxInvestments[j] : totalInvestment;investSecond = (maxInvestments[i] < (totalInvestment - investFirst)) ? maxInvestments[i] : (totalInvestment - investFirst);}else{// 回报率相同，优先风险低的if(risks[i] < risks[j]){investFirst = (maxInvestments[i] < totalInvestment) ? maxInvestments[i] : totalInvestment;investSecond = (maxInvestments[j] < (totalInvestment - investFirst)) ? maxInvestments[j] : (totalInvestment - investFirst);}else{investFirst = (maxInvestments[j] < totalInvestment) ? maxInvestments[j] : totalInvestment;investSecond = (maxInvestments[i] < (totalInvestment - investFirst)) ? maxInvestments[i] : (totalInvestment - investFirst);}}long long totalReturn = (long long)investFirst * rates[i] + (long long)investSecond * rates[j];// 更新最佳投资策略if(totalReturn > maxReturn || (totalReturn == maxReturn && combinedRisk < minRisk)){maxReturn = totalReturn;minRisk = combinedRisk;// 重置最佳投资for(int k=0;k<productCount;k++) bestInvestment[k] = 0;if(investFirst > 0){if(rates[i] > rates[j]){bestInvestment[i] = investFirst;bestInvestment[j] = investSecond;}else{bestInvestment[j] = investFirst;bestInvestment[i] = investSecond;}}}}}}// 输出最佳投资组合for(int i=0;i<productCount;i++){if(i != 0) printf(" ");printf("%d", bestInvestment[i]);}printf("\n");return 0;
}九、C++算法源码
#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int productCount, totalInvestment, totalRisk;// 读取第一行输入：产品数，总投资额，可接受的总风险cin >> productCount >> totalInvestment >> totalRisk;vector<int> rates(productCount);// 读取第二行输入：产品投资回报率序列for(auto &x : rates) cin >> x;vector<int> risks(productCount);// 读取第三行输入：产品风险值序列for(auto &x : risks) cin >> x;vector<int> maxInvestments(productCount);// 读取第四行输入：产品最大投资额度序列for(auto &x : maxInvestments) cin >> x;// 初始化最大回报和最小风险long long maxReturn = 0;int minRisk = INT32_MAX;// 存储最佳投资策略vector<int> bestInvestment(productCount, 0);// 枚举所有可能的投资组合for(int i=0;i<productCount;i++){// 单个产品投资if(risks[i] <= totalRisk){int investI = min(maxInvestments[i], totalInvestment);long long returnI = (long long)investI * rates[i];if(returnI > maxReturn || (returnI == maxReturn && risks[i] < minRisk)){maxReturn = returnI;minRisk = risks[i];fill(bestInvestment.begin(), bestInvestment.end(), 0);bestInvestment[i] = investI;}}// 枚举与其他产品组合投资for(int j=i+1;j<productCount;j++){int combinedRisk = risks[i] + risks[j];if(combinedRisk <= totalRisk){int investFirst, investSecond;if(rates[i] > rates[j]){investFirst = min(maxInvestments[i], totalInvestment);investSecond = min(maxInvestments[j], totalInvestment - investFirst);}else if(rates[i] < rates[j]){investFirst = min(maxInvestments[j], totalInvestment);investSecond = min(maxInvestments[i], totalInvestment - investFirst);}else{// 回报率相同，优先风险低的if(risks[i] < risks[j]){investFirst = min(maxInvestments[i], totalInvestment);investSecond = min(maxInvestments[j], totalInvestment - investFirst);}else{investFirst = min(maxInvestments[j], totalInvestment);investSecond = min(maxInvestments[i], totalInvestment - investFirst);}}long long totalReturn = (long long)investFirst * rates[i] + (long long)investSecond * rates[j];// 更新最佳投资策略if(totalReturn > maxReturn || (totalReturn == maxReturn && combinedRisk < minRisk)){maxReturn = totalReturn;minRisk = combinedRisk;fill(bestInvestment.begin(), bestInvestment.end(), 0);if(investFirst > 0){if(rates[i] > rates[j]){bestInvestment[i] = investFirst;bestInvestment[j] = investSecond;}else{bestInvestment[j] = investFirst;bestInvestment[i] = investSecond;}}}}}}// 输出最佳投资组合for(int i=0;i<productCount;i++){if(i !=0 ) cout << ' ';cout << bestInvestment[i];}cout << '\n';return 0;
}🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
