Неужели нет более общих математичных путей решения? Полный перебор – это всегда удручает.
Эта задача и многие подобные решаются перебором с отсечениями (в других разделах он может иметь собственное имя, как "ветви и границы" в дискретной оптимизации, или "альфа-бета процедура" в играх). В нём, сохраняя использование перебора, стараются минимизировать количество перебираемых ветвей до приемлемого.
Один из приёмов - убрать тривиальные решения, например, получаемые перестановками. В данном случае это достигается упорядочением рабочих по производительности, так что из различных решений, совпадающих с точностью до перестановки, остаётся одно.
Более мощный приём - отсекать некоторые направления перебора возможно ранее, не рассматривая все возможные варианты. Здесь есть место для эвристики, подсказывающей, по какой переменной начинать перебор и в каком порядке. Она, как и вообще эвристика, не гарантирует, что получится лучше, чем в другом порядке, но, как правило, удачная эвристика даёт огромную экономию (хотя почти всегда существует контрпример, показывающий, что именно эта эвристика может резко ухудшать дело). В данном случае начинаем перебор с самого могучего. Ясно, что он не выполнит работу за час, иначе она была бы уже сделана, а если ему надо 5 часов и более, то он даже с третью работы не справится, что противоречит предположению, что его производительность максимальна. То есть надо рассматривать не все 24 варианта возможной его производительность, а лишь 2, 3 и 4 часа, в восемь раз меньше.
Выбрав любой из вариантов, получаем ту же задачу, но для двоих рабочих и остаточного объёма. Аналогично для каждого варианта отсекаем невозможные производительности второго рабочего (бОльшие первого или не обеспечивающие выполнения хотя бы половины остатка), и рассматриваем возможные. Поскольку условие у нас - равенство, то для третьего рабочего перебора нет, его производительность получается вычитанием из общего объёма производительностей первых двух, нужна только проверка, получается ли для него удовлетворяющая условию производительность (выполнение работы за целое число часов, не менее, чем у 1 и 2, и не более 24 часов на всю работу), в случае ограничения-неравенства может понадобиться перебор и здесь.
Думается, что эта задача - введение в решение оптимизационных задач направленным перебором с отсечениями. Хотя, конечно, может быть просто упражнением на смекалку или вовсе "умственной забавой".
26.04.2014, 21:06 
