Жадный алгоритм Python. Получить все последовательности - PullRequest
Новая
       86

Жадный алгоритм Python. Получить все последовательности

0 голосов
/ 28 мая 2020

Попытка пройти алгоритмы DP и Greedy . Пожалуйста, помогите!

У ввода есть время, диапазон и цена. Например, - (начало, конец, цена) [(0,1,9), (0,3,8),(2,6,5),....(6,11,10)]. Если days_for_trading=2, программа должна дать наивысшую прибыль , то есть (0,1,9),(6,11,10). Но он останавливается на первом удовлетворяющем условии с диапазоном дней (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

1 Ответ

0 голосов
/ 28 мая 2020

Я предполагаю, что это именно эта строка, поскольку вы исключаете из нее последнюю торговую последовательность (и в вашей переменной есть опечатка) 

if days_for_trading==len(traiding_sequence):
    break

попробуйте с помощью 

if days_for_trading > len(traiding_sequence):
    break
...