返回目录

题目描述

在一款虚拟游戏中生活，你必须进行投资以增强在虚拟游戏中的资产以免被淘汰出局。

现有一家Bank，它提供有若干理财产品 m 个，风险及投资回报不同，你有 N（元）进行投资，能接收的总风险值为X。

你要在可接受范围内选择最优的投资方式获得最大回报。

备注：

• 在虚拟游戏中，每项投资风险值相加为总风险值；
• 在虚拟游戏中，最多只能投资2个理财产品；
• 在虚拟游戏中，最小单位为整数，不能拆分为小数；
• 投资额*回报率=投资回报

输入描述

第一行：

• 产品数（取值范围[1,20]）
• 总投资额（整数，取值范围[1, 10000]）
• 可接受的总风险（整数，取值范围[1,200]）

第二行：产品投资回报率序列，输入为整数，取值范围[1,60]

第三行：产品风险值序列，输入为整数，取值范围[1, 100]

第四行：最大投资额度序列，输入为整数，取值范围[1, 10000]

输出描述

每个产品的投资额序列

示例：

题目解析

第一眼看这题有点像二维费用背包，但是本题备注中有一个关键限制：

在虚拟游戏中，最多只能投资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 <stdio.h>
#include <limits.h>

#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<Integer, Integer> s = new 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);
    }
}