文章目录
目录
题目内容
解题思路
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;
}
