Ответы пользователя по тегу Алгоритмы
  • Как максимизировать сумму элементов выбираемых из списка?

    @Aleshonne
    Научные вычисления
    В общем, примерный план решения такой:
    Начинаем смотреть элементы с конца списка. Последние k элементов заносятся в кэш как есть, от них никуда не деться. Далее для каждого элемента с номером i нужно просмотреть, как он сочетается с элементами i + k .. i + 2k. Дальше смотреть смысла нет, так как это только ухудшит ситуацию. И так идём до первого элемента. Потом выбираем лучший из элементов с номерами 1 .. k. Вроде как получается линейный относительно размера списка код (не более k(n + 1) операций).
    Код реализации:
    https://ideone.com/ZU8Mrr
    Ответ написан
  • Как распределить заказы по курьерам?

    @Aleshonne
    Научные вычисления
    Это задача теории расписаний, обработка заданий множеством подвижных процессоров (возможно, с директивными сроками, если время приезда курьера назначено), и она, если я ничего не путаю, является NP-полной. Точное решение — полный перебор всех комбинаций заказов и курьеров, его можно немного оптимизировать, см. темы «Функция Беллмана», «Метод ветвей и границ».
    Если коротко, то нужно рассмотреть рекуррентную функцию B_i, которая является множеством оптимальных по Парето решений задачи для i заказов, и зависит от параметров i-го заказа и решения B_(i-1). Чтобы узнать конкретный вид функции B_i, надо отучиться в универе на математической специальности, а потом, как тут уже писали, пару лет исследовать проблему (возможно, попутно защитив диссертацию). Я знаю человека, который за решение похожей задачи доктора получил.
    Рекомендую использовать живого человека (диспетчера), который вручную разобьёт набор заказов на кластеры с учётом времени в пути между ними, а также будет вносить оперативные корректировки в процессе развоза заказов. По кластеру курьер отлично сориентируется сам.
    Ещё можно использовать жадный алгоритм, по принципу:
    1) добавить в конец списка курьеров одного фиктивного (всего n+1 курьер, m заданий);
    2) i-му курьеру назначить случайное незанятое задание j и (m/(n + 1) - 1) ближайших к нему;
    3) если есть свободные курьеры, увеличить i на 1 и перейти к пункту (2);
    4) задания, доставшиеся фиктивному курьеру раздать тем курьерам, к начальной точке работы которых они ближе.
    Фиктивный курьер нужен, потому что обычно последнему при таком распределении достаются осколки из разных углов. Но результат работы алгоритма требует контроля живым человеком.
    Ответ написан