时间戳

首页 > 解决方案 > 贪心算法 Python。获取所有序列

python - 贪心算法 Python。获取所有序列

问题描述

试图通过DP 和 Greedy 算法。请帮忙！

输入有时间、范围和价格。例如。-（开始，结束，价格）[(0,1,9), (0,3,8),(2,6,5),....(6,11,10)]。如果days_for_trading=2，程序应该给予最高的利润，它们是(0,1,9),(6,11,10)。但它在 days range 的第一个满足条件上停止(0,1,9), (2,6,5)。

真的不知道如何使这个迭代进一步。谢谢！

更新：感谢所有参与者。解决了。但是当前的算法不符合内存使用的限制。如果有人需要，我会在下面的评论中保留该任务的链接

def get_max(tmp, days_for_trading):
    global best_profit
    for day_start, day_end, price in tmp:
        traiding_sequence=[]
        cur_profit=0
        count=0
        deal=(day_start, day_end, price)
        traiding_sequence.append(deal)
        cur_profit+=price
        for next_day_start, next_day_end, next_price in tmp:    
            if days_for_trading==len(traiding_sequence):
                break
            else:
                if next_day_start>traiding_sequence[count][1]:
                    next_deal=(next_day_start, next_day_end, next_price)
                    traiding_sequence.append(next_deal)
                    cur_profit+=next_price
                    count+=1        
        best_profit=cur_profit if cur_profit>best_profit else best_profit

标签： pythonalgorithmdynamic-programminggreedy

解决方案

我认为是这一行，因为您排除了最后一个交易序列（并且您的变量中有错字）

if days_for_trading==len(traiding_sequence):
    break

试试看

if days_for_trading > len(traiding_sequence):
    break

推荐阅读