Python基于最优报价的买卖物品最大利润算法问题修复问询

问题背景 #

现有一个名为book的字典，包含"buy"和"sell"两个子字典。每个子字典的键为价格，值为数量：

• book['buy'][11.40] = 7000：代表可以11.40的价格买入7000件物品
• book['sell'][20.30] = 5500：代表可以20.30的价格卖出5500件物品

需求是计算通过最优报价交易获得的最大利润：以最低价格买入、最高价格卖出，仅当买入价低于卖出价时进行交易，直至其中一方报价耗尽。

以下是运行异常的原实现代码：

bought_price = 0 
sold_price = 0
ordered_buy = dict(sorted(book['buy'].items())) # 按价格升序排序买入单
ordered_sell = dict(sorted(book["sell"].items(), reverse=True)) # 按价格降序排序卖出单

for buy_price, buy_size in ordered_buy.items(): # 遍历最优买入价开始的订单
    for sell_price, sell_size in ordered_sell.items(): # 遍历所有卖出报价
        if buy_price < sell_price:
            if buy_size == 0 or sell_size == 0:
                continue
            if buy_size < sell_size:
                ordered_buy[buy_price] = 0
                offer_rest = sell_price - buy_price
                ordered_sell[sell_price] = offer_rest
                bought_price += buy_price * buy_size  
                sold_price += sell_price * sell_size - sell_price * offer_rest
            elif buy_size > sell_size:
                ordered_sell[sell_price] = 0
                offer_rest = buy_price - sell_price
                ordered_buy[buy_price] = offer_rest
                bought_price += buy_price * buy_size - buy_price * offer_rest
                sold_price += sell_price * sell_size

原代码问题分析 #

1. 遍历逻辑错误：嵌套循环会重复处理已耗尽的订单，导致冗余计算和逻辑混乱
2. 剩余数量计算错误：offer_rest错误计算为价格差，实际应为交易后剩余的物品数量
3. 字典遍历风险：遍历字典时修改其值，可能触发Python遍历行为异常
4. 分支缺失：未处理买入/卖出数量相等的场景

修复后的代码 #

采用双指针迭代方式，同时遍历排序后的买入、卖出订单，确保逻辑清晰且高效：

def calculate_max_profit(book):
    # 对订单排序：买入单按价格升序（低价优先），卖出单按价格降序（高价优先）
    sorted_buy = sorted(book['buy'].items(), key=lambda x: x[0])
    sorted_sell = sorted(book['sell'].items(), key=lambda x: -x[0])
    
    buy_idx = 0
    sell_idx = 0
    total_cost = 0  # 总买入成本
    total_revenue = 0  # 总卖出收入
    
    while buy_idx < len(sorted_buy) and sell_idx < len(sorted_sell):
        buy_price, buy_qty = sorted_buy[buy_idx]
        sell_price, sell_qty = sorted_sell[sell_idx]
        
        if buy_price >= sell_price:
            # 买入价不低于卖出价，无利润空间，终止交易
            break
        
        # 确定本次可交易的最大数量
        trade_qty = min(buy_qty, sell_qty)
        
        # 更新成本与收入
        total_cost += buy_price * trade_qty
        total_revenue += sell_price * trade_qty
        
        # 更新剩余订单数量
        if buy_qty == trade_qty:
            buy_idx += 1  # 当前买入单耗尽，切换下一个
        else:
            sorted_buy[buy_idx] = (buy_price, buy_qty - trade_qty)
        
        if sell_qty == trade_qty:
            sell_idx += 1  # 当前卖出单耗尽，切换下一个
        else:
            sorted_sell[sell_idx] = (sell_price, sell_qty - trade_qty)
    
    # 总利润 = 总收入 - 总成本
    return total_revenue - total_cost

# 测试示例
book = {
    'buy': {11.40: 7000, 12.00: 5000},
    'sell': {20.30: 5500, 19.50: 3000}
}

print(calculate_max_profit(book))

代码说明 #

• 排序逻辑：严格遵循最优策略，优先使用最低买入价和最高卖出价
• 双指针遍历：避免嵌套循环的冗余，仅处理有效订单
• 交易逻辑：每次取两者最小可交易数量，确保订单消耗计算准确
• 终止条件：当无利润空间或任意一方订单耗尽时停止交易

内容的提问来源于stack exchange，提问作者mioza