Проблема идет так (переводится):
На дне горы есть n (n <= 25000) человек, и все хотят подняться, а затем спуститься с горы. Есть два гида: один помогает человеку подняться на гору, другой помогает человеку спуститься. Человек, которого я занимаю (я), чтобы подняться на эту гору, и вниз (я), чтобы спуститься на нее Тем не менее, каждый гид может помочь только 1 человеку за раз (это означает, что не более 1 человека может подниматься, и не более 1 человека может спускаться с горы в любой момент времени). Предположим, когда направляющая «вверх» достигает вершины, он мгновенно телепортируется обратно вниз, как и в случае «направляющей вниз». Найдите наименьшее время, необходимое для того, чтобы все поднялись и спустились с горы. (Люди могут собираться на вершине горы, если это необходимо) </p>
Вот пример ввода для задачи с аннотациями мной:
3 persons
person 1: up=6 minutes, down=4 minutes
person 2: up=8 minutes, down=1 minutes
person 3: up=2 minutes, down=3 minutes
Вывод на вход:
Минимальное количество времени составляет 17. Это потому, что если человек 3 идет первым, то человек 1, а затем человек 2 (и этот же порядок
используется как для подъема, так и для спуска), это дает общее время 17.
Я пытался придумать несколько алгоритмов, но вот что у меня есть:
Алгоритм O (n! * N): просто перестановите коров через все возможные перестановки, используя next_permutation
Жадный алгоритм: я отсортировал людей по убыванию времени убывания и попытался собрать их вместе, но это не привело к правильному решению.
Другие мысли
Сейчас я перехожу к динамическому программированию, поскольку, согласно CLR, проблемы оптимизации обычно являются жадным или динамическим программированием (эта проблема, я думаю, удовлетворяет оптимальной подструктуре).
Я заметил, что в минимальном решении руководство "вверх" не будет отдыхать, пока все не поднимутся в гору. (Таким образом, нет промежутков между подъемом человека 1, подъемом человека 2 и т. Д.) Может быть, проблема может быть сведена к минимизации разрывов между временами снижения?
У меня проблемы с изображением состояния для этой проблемы динамического программирования (я не думаю, что она одномерная, потому что я не думаю, что вы можете найти оптимальное решение для человека, просто зная оптимальное решение для 1 человек).
Может ли кто-нибудь помочь?