返回目录题目描述在一款虚拟游戏中生活，你必须进行投资以增强在虚拟游戏中的资产以免被淘汰出局。
现有一家Bank，它提供有若干理财产品 m 个，风险及投资回报不同，你有 N（元）进行投资，能接收的总风险值为X。
你要在可接受范围内选择最优的投资方式获得最大回报。
备注：
在虚拟游戏中，每项投资风险值相加为总风险值；在虚拟游戏中，最多只能投资2个理财产品；在虚拟游戏中，最小单位为整数，不能拆分为小数；投资额*回报率=投资回报输入描述第一行：
产品数（取值范围[1,20]）总投资额（整数，取值范围[1, 10000]）可接受的总风险（整数，取值范围[1,200]）第二行：产品投资回报率序列，输入为整数，取值范围[1,60]
第三行：产品风险值序列，输入为整数，取值范围[1, 100]
第四行：最大投资额度序列，输入为整数，取值范围[1, 10000]
输出描述每个产品的投资额序列
示例：
输入5 100 1010 20 30 40 503 4 5 6 1020 30 20 40 30输出0 30 0 40 0说明投资第二项30个单位，第四项40个单位，总的投资风险为两项相加为4+6=10题目解析第一眼看这题有点像二维费用背包，但是本题备注中有一个关键限制：
在虚拟游戏中，最多只能投资2个理财产品；那么本题其实就变成了：m个理财产品中选1个或2个，所选产品风险值之和 ≤ x，投资额之和 ≤ n，并且最终所选产品的投资回报之和最大。
由于 m 的数量级不大，取值范围[1,20]，因此可以考虑暴力破解。
前面解法思路只有93%通过率，根据题目意思：
你要在可接受范围内选择最优的投资方式获得最大回报。如果有多种投资方式能拿到最大回报，那么此时应该优中选优（虽然题目没有明说），我们应该选其中风险值更小的。
另外，需要注意的是，当我们选择的两个产品的投资回报相同时，此时应该优先投资风险更小的产品。
我理解应该最后7%的用例应该就是这两个场景。
Python算法源码import sys
# 输入获取
m, n, x = map(int, input().split()) # 产品数, 总投资, 总风险
# 产品回报率序列
returns = list(map(int, input().split()))
# 产品风险值序列
risks = list(map(int, input().split()))
# 产品投资额序列
investments = list(map(int, input().split()))
# 记录所选产品的最大投资回报
max_investment_return = 0
# 记录所选产品的最大投资回报对应的风险值
max_investment_return_risk = sys.maxsize
# 记录所选产品的序号
selection = {}
# 选两个产品时
i = 0
while i < m:
# 如果单个产品的投资风险未超过总风险，则投资单个产品
if risks[i] <= x:
# 产品I的投资额不能超过该产品的最大投资额，以及总投资
investment_i = min(investments[i], n)
# 产品投资回报
investment_return = investment_i * returns[i]
# 如果投资回报高于其他产品组合，那么选择该产品
# **特别注意** 如果投资回报等于最优策略，那么继续比较风险值，如果风险值更小，则选择该产品
if investment_return > max_investment_return or (investment_return == max_investment_return and risks[i] < max_investment_return_risk):
max_investment_return = investment_return
max_investment_return_risk = risks[i]
selection.clear()
selection[i] = investment_i
else:
i += 1
continue
j = i + 1
while j < m:
# 如果两个产品的风险和不超过了总风险，那么两个产品都选
if risks[i] + risks[j] <= x:
investment_i = 0 # 产品I的投资额
investment_j = 0 # 产品J的投资额
# 其中优先投资回报率大的
if returns[i] > returns[j]:
# 产品I回报率高，则能投多少投多少，最多不能超过min(总投资, 产品I的最多投资额)
investment_i = min(n, investments[i])
# 留给产品J的剩余钱未 n - investment_i, 而产品J最多投资invest[j]，因此取二者较小值
investment_j = min(n - investment_i, investments[j])
elif returns[i] < returns[j]:
# 产品J回报率高，则能投多少投多少，最多不能超过min(总投资, 产品J的最多投资额)
investment_j = min(n, investments[j])
investment_i = min(n - investment_j, investments[i])
elif risks[i] > risks[j]:
# 产品I和产品J回报率相同，则看谁的风险值更小，如果产品J的风险值更小，则能投多少投多少
investment_j = min(n, investments[j])
investment_i = min(n - investment_j, investments[i])
else:
# 产品I和产品J回报率相同，则看谁的风险值更小，如果产品I的风险值更小，则能投多少投多少
investment_i = min(n, investments[i])
investment_j = min(n - investment_i, investments[j])
# 总投资回报
investment_return = investment_i * returns[i] + investment_j * returns[j]
# 总风险值
investment_return_risk = risks[i] + risks[j]
# 如果当前产品组合的总回报更大，则选当前组合产品
if investment_return > max_investment_return or (investment_return == max_investment_return and investment_return_risk < max_investment_return_risk):
max_investment_return = investment_return
max_investment_return_risk = investment_return_risk
selection.clear()
# select的key记录产品的ID，val记录产品的投资额
if investment_i > 0:
selection[i] = investment_i
if investment_j > 0:
selection[j] = investment_j
j += 1
i += 1
res = []
for i in range(m):
if i in selection:
res.append(selection[i])
else:
res.append(0)
print(" ".join(map(str, res)))C算法源码#include
#include
#define MINIMUM(a, b) ((a) < (b) ? (a) : (b))
int main() {
// 产品数量，总投资，总风险
int num_products, total_investment, total_risk;
scanf("%d %d %d", &num_products, &total_investment, &total_risk);
// 产品回报率数组
int returns[num_products];
for (int i = 0; i < num_products; i++) scanf("%d", &returns[i]);
// 产品风险值数组
int risks[num_products];
for (int i = 0; i < num_products; i++) scanf("%d", &risks[i]);
// 产品投资额数组
int investments[num_products];
for (int i = 0; i < num_products; i++) scanf("%d", &investments[i]);
// 记录所选产品的最大投资回报
int max_investment_return = 0;
// 记录所选产品的最大投资回报对应的风险值
int max_investment_return_risk = INT_MAX;
// 记录所选产品的序号和投资额
int selected_ids[] = {-1, -1};
int selected_investments[] = {0, 0};
int i = 0;
while (i < num_products) {
// 如果单个产品的投资风险未超过总风险，则投资单个产品
if (risks[i] <= total_risk) {
// 产品i的投资额不能超过该产品的最大投资额，以及总投资
int investment_i = MINIMUM(investments[i], total_investment);
// 产品投资回报
int investment_return = investment_i * returns[i];
// 如果投资回报高于最优策略，那么选择该产品
// **特别注意** 如果投资回报等于最优策略，那么继续比较风险值，如果风险值更小，则选择该产品
if (investment_return > max_investment_return || (investment_return == max_investment_return && risks[i] < max_investment_return_risk)) {
max_investment_return = investment_return;
max_investment_return_risk = risks[i];
selected_ids[0] = i;
selected_investments[0] = investment_i;
selected_ids[1] = -1;
}
} else {
i++;
continue;
}
int j = i + 1;
while (j < num_products) {
// 如果两个产品的风险和不超过了总风险，那么两个产品都选
if (risks[i] + risks[j] <= total_risk) {
int investment_i; // 产品i的投资额
int investment_j; // 产品j的投资额
// 其中优先投资回报率大的
if (returns[i] > returns[j]) {
// 产品i回报率高，则能投多少投多少，最多不能超过min(总投资, 产品i的最多投资额)
investment_i = MINIMUM(total_investment, investments[i]);
// 留给产品j的剩余钱为 total_investment - investment_i，而产品j最多投资investments[j]，因此取二者较小值
investment_j = MINIMUM(total_investment - investment_i, investments[j]);
} else if (returns[i] < returns[j]) {
// 产品j回报率高，则能投多少投多少，最多不能超过min(总投资, 产品j的最多投资额)
investment_j = MINIMUM(total_investment, investments[j]);
investment_i = MINIMUM(total_investment - investment_j, investments[i]);
} else if (risks[i] > risks[j]) {
// **特别注意** 产品i和产品j回报率相同，则看谁的风险值更小，如果产品j的风险值更小，则能投多少投多少
investment_j = MINIMUM(total_investment, investments[j]);
investment_i = MINIMUM(total_investment - investment_j, investments[i]);
} else {
// **特别注意** 产品i和产品j回报率相同，则看谁的风险值更小，如果产品i的风险值更小，则能投多少投多少
investment_i = MINIMUM(total_investment, investments[i]);
investment_j = MINIMUM(total_investment - investment_i, investments[j]);
}
// 总投资回报
int total_investment_return = investment_i * returns[i] + investment_j * returns[j];
// 总风险值
int total_investment_return_risk = risks[i] + risks[j];
// 如果当前产品组合的总回报更大，则选当前组合产品
// **特别注意** 如果投资回报等于最优策略，那么继续比较风险值，如果风险值更小，则选择该产品
if (total_investment_return > max_investment_return || (total_investment_return == max_investment_return && total_investment_return_risk < max_investment_return_risk)) {
max_investment_return = total_investment_return;
max_investment_return_risk = total_investment_return_risk;
selected_ids[0] = -1;
selected_ids[1] = -1;
// select的key记录产品的ID，val记录产品的投资额
if (investment_i > 0) {
selected_ids[0] = i;
selected_investments[0] = investment_i;
}
if (investment_j > 0) {
selected_ids[1] = j;
selected_investments[1] = investment_j;
}
}
}
j++;
}
i++;
}
for (int i = 0; i < num_products; i++) {
if (i == selected_ids[0]) {
printf("%d", selected_investments[0]);
} else if (i == selected_ids[1]) {
printf("%d", selected_investments[1]);
} else {
printf("%d", 0);
}
if (i < num_products - 1) {
printf(" ");
}
}
return 0;
}Java算法源码import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringJoiner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] t = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int m = t[0]; // 产品数
int n = t[1]; // 总投资
int x = t[2]; // 总风险
// 产品回报率序列
int[] b = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 产品风险值序列
int[] r = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 产品投资额序列
int[] i = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int mb = 0;
int mbr = Integer.MAX_VALUE;
HashMap
int iIndex = 0;
while (iIndex < m) {
if (r[iIndex] <= x) {
int investI = Math.min(i[iIndex], n);
int ib = investI * b[iIndex];
if (ib > mb || (ib == mb && r[iIndex] < mbr)) {
mb = ib;
mbr = r[iIndex];
s.clear();
s.put(iIndex, investI);
}
} else {
iIndex++;
continue;
}
int jIndex = iIndex + 1;
while (jIndex < m) {
if (r[iIndex] + r[jIndex] <= x) {
int investI;
int investJ;
if (b[iIndex] > b[jIndex]) {
investI = Math.min(n, i[iIndex]);
investJ = Math.min(n - investI, i[jIndex]);
} else if (b[iIndex] < b[jIndex]) {
investJ = Math.min(n, i[jIndex]);
investI = Math.min(n - investJ, i[iIndex]);
} else if (r[iIndex] > r[jIndex]) {
investJ = Math.min(n, i[jIndex]);
investI = Math.min(n - investJ, i[iIndex]);
} else {
investI = Math.min(n, i[iIndex]);
investJ = Math.min(n - investI, i[jIndex]);
}
int ib = investI * b[iIndex] + investJ * b[jIndex];
int ibr = r[iIndex] + r[jIndex];
if (ib > mb || (ib == mb && ibr < mbr)) {
mb = ib;
mbr = ibr;
s.clear();
if (investI > 0) s.put(iIndex, investI);
if (investJ > 0) s.put(jIndex, investJ);
}
}
jIndex++;
}
iIndex++;
}
StringJoiner sj = new StringJoiner(" ");
for (int k = 0; k < m; k++) {
if (s.containsKey(k)) {
sj.add(s.get(k) + "");
} else {
sj.add("0");
}
}
System.out.println(sj);
}
}