У меня возникли трудности с недооцененной алгоритмической проблемой:
В порту стоит трехполосный паром и перед ним очередь из N автомобилей. Каждый из них имеет указанную длину в см. Мы также знаем длину (L) парома. Нам необходимо предложить алгоритм, позволяющий загрузить паром максимальным количеством автомобилей из очереди. Каждая машина может выбрать одну из трех полос движения: левую, центральную или правую. Автомобили должны обрабатываться по порядку - для каждого автомобиля (начиная с переднего) мы должны решить, по какой полосе он будет двигаться. Если не хватает свободного места для машины, находящейся в начале очереди на момент финиша. Остальные машины ждут следующего парома.
Жадный метод (первое соответствие) не является самым эффективным в каждом случае (например, если L равно 5 и у нас есть очередь 5 2 2 3 3). Таким образом, я пытался выяснить, каково решение, если мы будем думать об этом как о проблеме динамического программирования. Тем не менее, я пытаюсь найти любой, но все известные мне динамические алгоритмы (особенно из Введение в алгоритмы) не подходят для этой проблемы.
Заранее благодарим вас за любые предложения. :)
