刷题笔记合集🔗

虚拟理财游戏

题目描述

在一款虚拟游戏中,玩家需要通过投资来增加自己的资产,以免被淘汰出局。游戏中有一家银行提供 个理财产品,每个产品的风险和投资回报不同。玩家拥有 元的初始资金,可以接受的总风险值为 。

为了在游戏中取得胜利,玩家需要在可接受的风险范围内,选择最优的投资方式以获得最大回报。游戏规则如下:

1. 每项投资的风险值相加为总风险值。
2. 玩家最多只能投资 个理财产品。
3. 投资金额必须为整数,不能拆分为小数。
4. 投资回报 = 投资金额 × 回报率。

现在请你帮助玩家设计一个最佳的投资策略。

输入格式

第一行包含三个整数 、 和 ,分别表示理财产品数量、总投资金额和可接受的风险值。

第二行包含 个整数,表示每个理财产品的投资回报率。

第三行包含 个整数,表示每个理财产品的风险值。

第四行包含 个整数,表示每个理财产品的最大投资额度。

输出格式

输出一行,包含 个整数,表示在每个理财产品上的投资金额。如果不投资某个产品,则对应的投资金额为 。

样例输入

5 100 10
10 20 30 40 50 
3 4 5 6 10
20 30 20 40 30

样例输出

0 30 0 40 0

样例解释

在给定的 个理财产品中,选择投资第 个产品 元和第 个产品 元,总投资 元,总风险值为 ,满足要求。投资回报为 元,是所有满足条件的投资方案中回报最高的。

数据范围

• 
• 
• 
• 投资回报率
• 风险值
• 最大投资额度

题解

暴力枚举

题目有一个关键限制:玩家最多只能投资 个理财产品。这就大大简化了问题的复杂度。

可以这样考虑:从 个理财产品中选择 个或 个产品进行投资,使得选择的产品总风险值不超过 ,总投资额不超过 ,并且投资回报最大化。

由于 的数量级很小,最多只有 ,可以直接用暴力枚举的方法来解决这个问题。具体步骤如下:

1. 枚举选择 个产品的所有情况,对于每个产品,如果其风险值和投资额都满足条件,就计算投资回报,更新答案。

2. 枚举选择 个产品的所有情况,对于每对产品,如果它们的风险值之和和投资额之和都满足条件,就计算总投资回报,更新答案。

3. 最后,我们就得到了在风险值和投资额限制下的最大投资回报,以及对应的投资方案。

参考代码

• Python

# 读入数据
m, N, X = map(int, input().split())
rates = list(map(int, input().split()))
risks = list(map(int, input().split()))
limits = list(map(int, input().split()))

# 初始化答案
max_profit = 0
ans = [0] * m

# 枚举选1个产品的情况
for i in range(m):
    if risks[i] <= X and limits[i] <= N:
        profit = rates[i] * limits[i]
        if profit > max_profit:
            max_profit = profit
            ans = [0] * m
            ans[i] = limits[i]

# 枚举选2个产品的情况        
for i in range(m):
    for j in range(i+1, m):
        if risks[i] + risks[j] <= X and limits[i] + limits[j] <= N:
            profit = rates[i] * limits[i] + rates[j] * limits[j]
            if profit > max_profit:
                max_profit = profit
                ans = [0] * m
                ans[i] = limits[i]
                ans[j] = limits[j]

# 输出答案                
print(*ans)

• C

#include <stdio.h>

#define MAX_M 20

int main() {
    int m, N, X;
    int rates[MAX_M], risks[MAX_M], limits[MAX_M];
    
    // 读入数据
    scanf("%d %d %d", &m, &N, &X);
    for (int i = 0; i < m; i++) {
        scanf("%d", &rates[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &risks[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &limits[i]);
    }
    
    // 初始化答案
    int max_profit = 0;
    int ans[MAX_M] = {0};
    
    // 枚举选1个产品的情况
    for (int i = 0; i < m; i++) {
        if (risks[i] <= X && limits[i] <= N) {
            int profit = rates[i] * limits[i];
            if (profit > max_profit) {
                max_profit = profit;
                for (int j = 0; j < m; j++) {
                    ans[j] = 0;
                }
                ans[i] = limits[i];
            }
        }
    }
    
    // 枚举选2个产品的情况
    for (int i = 0; i < m; i++) {
        for (int j = i+1; j < m; j++) {
            if (risks[i] + risks[j] <= X && limits[i] + limits[j] <= N) {
                int profit = rates[i] * limits[i] + rates[j] * limits[j];
                if (profit > max_profit) {
                    max_profit = profit;
                    for (int k = 0; k < m; k++) {
                        ans[k] = 0;
                    }
                    ans[i] = limit