华为OD机试真题-最大利润【C++ Java Python】

ゞ浴缸里的玫瑰 2024-03-22 18:53 65阅读 0赞

## 文章目录 ##

--------------------

**目录**

题目内容

解题思路

Java代码

Python代码

C++代码

## 题目内容 ##

--------------------

商人经营一家店铺，有number 种商品，  
由于仓库限制每件商品的最大持有数量是 item\[index\]。  
每种商品的价格是 price\[item\_index\]\[day\]  
通过对商品的买进和卖出获取利润  
请给出商人在 days 天内能获取的最大的利润

注:同一件商品可以反复买进和卖出

**输入描述**

3 第一行输入商品的数量 number  
3 第二行输入商品售货天数 days  
4 5 6 第三行输入仓库限制每件商品的最大持有数量是item\[index\]  
1 2 3 第一件商品每天的价格  
4 3 2 第二件商品每天的价格  
1 5 3 第三件商品每天的价格

**输入：**  
3  
3  
4 5 6  
1 2 3  
4 3 2  
1 5 3

**输出：**  
32

## 解题思路 ##

--------------------

由于题目比较复杂，为了降低难度，**先不看示例case**，假设有一件商品：

第 0 天的价格：1

第 1 天的价格：2

第 2 天的价格：3

第 3 天的价格：4

**贪心算法的策略**：由于不限制交易次数，只要**今天价格比昨天高**，就在昨天买，在今天卖。

比如上述商品，它的价格为 \[1, 2, 3, 4\] ，这 4 天的价格依次上升，按照贪心算法，得到的最大利润是：

res = (prices\[3\] - prices\[2\]) + (prices\[2\] - prices\[1\]) + (prices\[1\] - prices\[0\]) = prices\[3\] - prices\[0\]

如果你读不懂上述例子，我们可以这么理解：第 0 天买， 第 1 天卖；第 1 天再买，第 2 天卖；第 2 天再买， 第 3 天卖；为什么这么操作？正如之前的贪心策略：只要**今天价格比昨天高**，就在昨天买，然后在今天卖。你可能会问：**`为什么不能在第 0 天买入，然后一直存放着不卖，直到第三天再卖出？`** 当然可以按照你的想法交易，但是我们的策略是不是**等同于**第 0 天买入，第 3 天卖出？ 你可以自己计算一下，两种做法是不是最终的收益是一样的。

好了，当你理解了**一件商品**的买卖策略之后，多件商品的买卖策略**完全相同**。对于本题，多件商品，我们可以这么解题：

最开始，将最大利润设置为 `0`。  
然后遍历每件商品，计算利润。

*  遍历每天的价格，计算该商品每天的利润**`当天价格 - 前一天价格的差值`**，如果差值为负数，则取0。
 *  将每天的利润累加，得到该商品总利润。
 *  计算该商品的最大利润，**`商品利润*仓库限制的最大持有数量`**。
 *  将商品最大利润累加到总利润。

## Java代码 ##

--------------------

import java.util.Scanner;
    import java.util.List;
    import java.util.ArrayList;
    import java.util.stream.Collectors;
    
    class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            // 商品数量和售货天数
            int numberOfItems = Integer.parseInt(in.nextLine());
            int days = Integer.parseInt(in.nextLine());
    
            // 仓库限制的每件商品最大持有数量
            List<Integer> maxItemLimits = Arrays.stream(in.nextLine().split(" "))
                    .map(Integer::parseInt)
                    .collect(Collectors.toList());
    
            // 每件商品每天的价格
            List<ArrayList<Integer>> itemPrices = new ArrayList<ArrayList<Integer>>();
            for (int i = 0; i < numberOfItems; i++) {
                List<Integer> dailyPrice = Arrays.stream(in.nextLine().split(" "))
                    .map(Integer::parseInt)
                    .collect(Collectors.toList());
                itemPrices.add(new ArrayList<>(dailyPrice));
            }
    
            // 最大利润
            int maxProfit = 0;
            
            for (int i = 0; i < itemPrices.size(); i++) {
                int profit = 0;
                for (int j = 1; j < itemPrices.get(i).size(); ++j) {
                    profit += Math.max(0, itemPrices.get(i).get(j) - itemPrices.get(i).get(j - 1));
                }
                // 将商品利润累加到总利润
                maxProfit += profit * maxItemLimits.get(i);
            }
    
            System.out.println(maxProfit);
        }
    }

## Python代码 ##

--------------------

# coding:utf-8
    
    import functools
    # 商品数量
    num_goods = int(input())
    
    # 售货天数
    num_days = int(input())
    
    # 每种商品的最大持有数量
    max_stock = [int(x) for x in input().split(" ")]
    
    # 每种商品每天的价格
    prices = []
    for i in range(num_goods):
        prices.append([int(x) for x in input().split(" ")])
    
    # 总利润
    total_profit = 0
    
    for i in range(len(prices)):
        profit = 0 
        for j in range(1, len(prices[i])):
            # 如果今天的价格高于昨天的价格，则买进昨天，今天卖出，获得利润
            # 如果今天的价格低于昨天的价格，那么就不操作，利润为0
            profit += max(0, prices[i][j] - prices[i][j-1])
    
        # 将每种商品的利润加入总利润
        total_profit += profit * max_stock[i]
    
    print(total_profit)

## C++代码 ##

--------------------

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() {
        // 商品数量和经营天数
        int itemNum, days;
        cin >> itemNum >> days;
    
        // 每种商品的最大持有量
        vector<int> maxItem;
        for (int i=0; i<itemNum; i++) {
            int maxHold;
            cin >> maxHold;
            maxItem.push_back(maxHold);
        }
    
        // 每种商品每天的价格
        vector<vector<int>> prices;
        for (int i=0; i<itemNum; i++) {
            vector<int> price;
            for (int j=0; j<days; j++) {
                int p;
                cin >> p;
                price.push_back(p);
            }
            prices.push_back(price);
        }
        
        int maxProfit = 0;
        for (int i=0; i<prices.size(); i++) {
            int profit = 0;
            // 每天比较今天的价格与昨天的价格，如果今天价格高，则卖出商品获利
            for (int j=1; j<prices[i].size(); j++) {
                profit += max(0, prices[i][j] - prices[i][j-1]);
            }
            maxProfit += profit * maxItem[i];
        }
            
        cout << maxProfit << endl;
    
        return 0;
    }