задача: есть предприятие. m видов работ, n месяцев. работы неделимы. трудоёмкости у каждой работы соотв-но b[i]. надо более или менее равномерно распределить работы по месяцам так, чтобы максимальная напряженность месяца была минимальной из всех возможных, т.е. max (суммаb[i]) ->min
(сумма b[i] - напряженность какого-то месяца)
n>6; m>20
помогите написать прогу. или хотя бы алгоритм. а то меня застопорило..
писать можно но паскали или с++.
буду очень признательна.
чтото при прочтении задачи мне вспоминается университетский курс комбинаторики, почему не знаю. Наверно это одна из тех задач, которую надо сначала решить на бумаге а потом писать прогу.
ЗЫ: А что значит распределить более или менее? наверно все же найти минимальную напряженность месяца, так? а задача полностью сформулирована?
и срок к которому надо скажи
срок к 16.10.
(не collapse, но знаю. )
точная формулировка: в течение n месяцев предприятию необх-мо выполнить m работ, заданы b[i] - трудоёмкости. каждая работа может выполняться в течение только одного месяца (неважно, которого). требуется составить наиболее равномерный план работы предприятия, разбив перечень работ на группы по месяцам так, чтобы планируемый объем работ в течение наиболее напряженного месяца был минимальным.
размерность: n>=6, m>=20
предмет - комбинаторные алгоритмы=)
сдать надо к четвергу, т.е. 16 окт.
буду признательна за помощь=)
Посылаю еще раз, вчера были глюки, не прислалось
пасип=)
;D
Эта прога не работает. Решение должно быть кардинально другим.
Тест: 2 дня, работы: 5 5 3 3 3
Программа выдаст 8 и 11, правильный ответ - 10 и 9.
Возможные пути решения:
- Полный перебор
- Можно оценить продолжительность работ для каждого дня сверху как сумму продолжительностей всех работ, снизу - как сумму продолжительностей всех работ, деленную на количество дней. Это позволит снизить перебор (наверно)
ЗЫ препод этого не заметил... я был о нем лучшего мнения