Выбор активности с использованием Python - PullRequest
Новая
       6

Выбор активности с использованием Python

0 голосов
/ 07 января 2019

Я пытаюсь решить проблему выбора активности, используя жадный алгоритм. Мой код не работает для некоторых входов. Я сортирую список активности на основе списка finish_time_list.

Код не работает для следующего ввода:

Activity_list = [1, 2, 3, 4, 5, 6]

start_time_list = [5, 4, 8, 2, 3, 1]

finish_time_list = [13, 6, 16, 7, 5, 4]

Мой отсортированный список активности: [6, 5, 2, 4, 1, 3] 

def find_maximum_activities(activity_list,start_time_list, finish_time_list):

    selected =[]


    activity_tmp_list = [x for _,x in sorted(zip(finish_time_list,activity_list))]

    #the first activity is always selected
    i=0
    #print(i)
    selected.append(activity_tmp_list[i])

    #consider rest of Activities
    for j in range(1,len(activity_list)):

        if start_time_list[j]>=finish_time_list[i]:
            print(j)
            selected.append(activity_tmp_list[j])
            i=j
    return selected

activity_list=[1, 2, 3, 4, 5, 6]
start_time_list=[5, 4, 8, 2, 3, 1]
finish_time_list=[13, 6, 16, 7, 5, 4]

print("Activities:",activity_list)
print("Start time of the activities:",start_time_list)
print("Finishing time of the activities:", finish_time_list)

result=find_maximum_activities(activity_list,start_time_list, finish_time_list)
print("The maximum set of activities that can be completed:",result)

Ожидаемый результат: [6,1]

Фактический результат: [6]

1 Ответ

0 голосов
/ 07 января 2019

Проблема в том, что в вашем цикле for вы сравниваете каждое время запуска с finish_time_list[i]. i=0 каждый раз, когда выполняется цикл, и в этом случае finish_time_list[0] равен 13, что является последним, чтобы завершить, так что if никогда не станет истинным.

Другая проблема заключается в том, что вы проверяете, как j проходит start_time_list, но вы добавляете тот же самый j из activity_tmp_list, который был отсортирован. Поскольку он отсортирован, индексы активности не будут выстраиваться так, как вы хотите.

Более высокоуровневая проблема заключается в том, что вы сохраняете номер активности только в массиве selected, и ничего о том, когда он начинается или заканчивается. Не зная этой информации о том, что уже было выбрано, вы не можете решить, добавлять ли другое действие или нет. Я бы рекомендовал либо сделать класс Activity, содержащий его метку, время начала и время окончания, либо сделать selected 2D-матрицу, чтобы после выбора первого действия он выглядел примерно как [[6, 1, 4]], содержащий метку где это начинается и где это заканчивается. Или, минимально, только метка и время окончания, при условии, что вы хотите сохранить жадный алгоритм.

Если у вас есть другие вопросы, дайте мне знать.

...