刷题笔记合集🔗

最大利润-贪心的商人

问题描述

商人经营一家店铺，有 种商品，由于仓库限制每件商品的最大持有数量是 ，每种商品的价格是 。

通过对商品的买进和卖出获取利润，请给出商人在 天内能获取的最大的利润。 注：同一件商品可以反复买进和卖出。

输入格式

第一行输入一个整数 ，表示商品的数量。

第二行输入一个整数 ，表示售货天数。

第三行输入 个整数，表示仓库限制每件商品的最大持有数量 。

接下来 行，每行包含 个整数，表示每种商品在每天的价格 。

输出格式

输出一个整数，表示商人在这段时间内的最大利润。

样例输入

3
3
4 5 6
1 2 3
4 3 2
1 5 2

样例输出

32

样例解释

对于第一种商品，可以在第一天以 1 的价格买入 4 个，在第三天以 3 的价格卖出，获利 (3-1)*4 = 8。 对于第二种商品，可以在第二天以 3 的价格买入 5 个，在第一天以 4 的价格卖出，获利 (4-3)*5 = 5。 对于第三种商品，可以在第一天以 1 的价格买入 6 个，在第二天以 5 的价格卖出，获利 (5-1)*6 = 24。 总利润为 8 + 5 + 24 = 37。

样例输入

1
1
1
1

样例输出

0

样例解释

只有一种商品，只有一天，无法获得利润。

数据范围

题解

这道题的核心思路是利用贪心算法来解决。

虽然看起来像是一个复杂的动态规划问题，但实际上有一个更简单的解法。

关键在于理解：只要价格在上涨，我们就应该持有商品；只要价格在下跌，我们就应该卖出商品。

这样，我们可以捕捉到每一个价格上涨的机会，从而最大化利润。

遍历每种商品的价格序列。对于每种商品，我们比较相邻两天的价格：

1. 如果明天的价格高于今天，我们就在今天买入（如果没有持有），明天卖出。
2. 如果明天的价格低于或等于今天，我们就不进行任何操作。

参考代码

• Python

# 读取输入
number = int(input())  # 商品数量
days = int(input())    # 售货天数
item = list(map(int, input().split()))  # 每种商品的最大持有数量
prices = [list(map(int, input().split())) for _ in range(number)]  # 每种商品每天的价格

# 初始化总利润
total_profit = 0

# 遍历每种商品
for i in range(number):
    # 遍历该商品的每一天（除了最后一天）
    for j in range(days - 1):
        # 如果明天的价格高于今天，就在今天买入，明天卖出
        if prices[i][j] < prices[i][j + 1]:
            # 计算利润：（明天价格 - 今天价格）* 最大持有数量
            profit = (prices[i][j + 1] - prices[i][j]) * item[i]
            # 累加到总利润
            total_profit += profit

# 输出最大利润
print(total_profit)

• C

#include <stdio.h>
#include <stdlib.h>

int main() {
    int number, days;
    scanf("%d", &number);  // 读取商品数量
    scanf("%d", &days);    // 读取售货天数

    int* item = (int*)malloc(number * sizeof(int));  // 动态分配内存存储最大持有数量
    for (int i = 0; i < number; i++) {
        scanf("%d", &item[i]);  // 读取每种商品的最大持有数量
    }

    int** prices = (int**)malloc(number * sizeof(int*));  // 动态分配二维数组存储价格
    for (int i = 0; i < number; i++) {
        prices[i] = (int*)malloc(days * sizeof(int));
        for (int j = 0; j < days; j++) {
            scanf("%d", &prices[i][j]);  // 读取每种商品每天的价格
        }
    }

    long long total_profit = 0;  // 使用长整型避免溢出

    // 遍历每种商品
    for (int i = 0; i < number; i++) {
        // 遍历该商品的每一天（除了最后一天）
        for (int j = 0; j < days - 1; j++) {
            // 如果明天的价格高于今天，就在今天买入，明天卖出
            if (prices[i][j] < prices[i][j + 1]) {
                // 计算利润并累加到总利润
                total_profit += (long long)(prices[i][j + 1] - prices[i][j]) * item[i];
            }
        }