Добрый день. Своё задание пишу в Javа. Алгоритм, придуманный мной для этого задания, не во всех случаях верно работает. Помогите определить условие, при котором он заработает. Либо, подскажите, как ещё можно было бы составить алгоритм для решения поставленной задачи.
Задача.
В ряду стоят автомобили. Они не могут друг друга обгонять. Они должны переехать мост в одну сторону. У моста ограничена грузоподъёмность, которую нельзя превышать. Переправу через мост контролируют диспетчеры.
Ряд автомобилей полностью должен переехать через мост. Если мост слишком нагружен, должен быть написан алгоритм, который разделит автомобили на группы таким образом, чтобы целый ряд автомобилей переехал мост, за как можно более короткое время. Диспетчеры обеспечивают гарантию того, что на мост не въедет группа автомобилей, которая превышает грузоподъемность моста. Первый диспетчер впускает группу на мост. Следующую группу машин впустит лишь тогда, когда диспетчер на другом конце моста даст знать, что первая группа мост переехала.
Вес каждого автомобиля известен. Вес группы автомобилей не должен превышать грузоподъемность моста. К сожалению, каждый автомобиль имеет разную максимальную скорость, которая так же известна. Группа принимает скорость самого медленного автомобиля в этой группе.
Цель:
Составить метод, который разделит ряд автомобилей на группы таким образом, чтобы группа автомобилей не превышала грузоподъёмность моста и, чтобы целый ряд автомобилей проезжал мост за минимально возможное время.
Например:
Грузоподъёмность моста 100 тонн
Длина моста 5км
Вес / Скорость / Время переправы (в какую группу определит алгоритм)
40 25 12мин (1 группа)
50 20 15мин (2 группа)
50 20 15мин (2 группа)
70 10 30мин (3 группа)
12 50 6мин(3 группа)
9 70 4.3мин (3 группа)
49 30 10мин (4 группа)
38 25 12мин (4 группа)
27 50 6мин (5группа)
19 17 4.3мин (6 группа)
Оптимальное время 75 мин (12+15+30+12+6)
Мой вопрос: Помогите, пожалуйста, составить алгоритм. Я его составила, исходя из поиска самого медленного автомобиля в ряду. В очереди ищу самый медленный автомобиль, смотрю на автомобиль за ним и после него. Если, прибавив к самому медленному автомобилю предыдущий или последующий автомобиль грузоподъёмность не превысится, то выбираю тот из двух, который медленнее. Такой алгоритм в любом случае разбивает на группы, но условие, что время переправы должно быть минимальным из всех возможных, не всегда выполняется.
Например, взять грузоподъёмность = 100 тонн
Автомобили
1. 40 тонн 12 мин
2. 50 тонн 15 мин
3. 50 тонн 15 мин
4. 40 тонн 12 мин
Мой алгоритм найдёт первым автомобиль 2., к нему возможно прибавить либо автомобиль 1. либо автомобиль 3. , мой алгоритм выберет автомобиль 3(медленнее, чем 1). И объединит эти машины «как бы» в одну, которая весит 50+50 = 100 тонн и проедет мост за 15 минут. Это группа. Эти элементы уже не рассматриваю.
После алгоритм снова ищет самое медленное авто (рекурсия), перед первым автомобилем никого нет, а 2ой автомобиль уже в группе. Значит 1. автомобиль образует сам свою группу. То же и с автомобилем 4. Таким образом, весь ряд проедет мост за 12+15+12 = 39 минут.
А это неверно, потому как правильнее будет распределить 1авто+2 авто и 3 авто + 4 авто, то есть две группы: 15+15 = 30 минут.
Я предполагаю, что алгоритм должен быть совершенно иным. Либо есть какие-то условия, при которых мой алгоритм заработает для всех вариантов, но это условие я придумать не могу. Можно было бы посмотреть не только на предыдущий и последующий автомобили, но и на пред-предыдущий, пред-пред-предыдущий, но это ерунда, код будет ужасным, и если представить, что в моём ряду более 4ёх автомобилей…(вообще молчу). Может существует какой-нибудь алгоритм, описывающий разделение множества на подмножества при условиях, подходящих моему заданию, который бы помог это решить?
Спасибо.