Разложение числа

[doro]

Количество людей может варьироваться от единиц до сотен.
Период - от дня до месяца или даже года (вобщем то тоже величина неизвестная).

[v_mirgorodsky]

Оки, теперь резюмируем все, что стало известно о задаче.
1. Есть некий перечень работ с фиксированными весовыми коеффициентами.
2. Вероятно есть количество людей, требуемых для выполнения каждой из работ.
3. Вероятно есть среднее целевое количество баллов, которое необходимо набрать каждому из работников.
4. Есть некий список людей, которых необходимо расставить по местам.
5. Есть длительность планируемого периода.
6. Возможно есть личные преференции отдельных людей, могущих выполнять только работы определенного вида.

Необходимо расставить людей по работам таким образом, дабы разница набраных ними баллов за выполнение конкретных работ была минимальна за планируемый период.

Если описание задачи верно, то необходимости в алгоритме разложения числа на сумму из коэффициентов сложности работ я не вижу. Очевидно, что такое разложение будет не единственным, количество вариантов таких разложений будет расти очень быстро по мере увеличения значения самого числа, а главное, построенный массив таких разложений никак не помогает в решении поставленной задачи. Окончательному алгоритму все равно придется заниматься перебором вариантов, а именно брать каждый элемент такого массива и проверять его на применимость в контексте уже принятых решений - запланированных людей на определенные работы.

IMHO, если бы передо мной стояла подобная задача я бы решал ее прямым перебором "в лоб". При реальных числах работников и длительности планируемых периодов число вариантов окажется совсем небольшим.

[doro]

v_mirgorodsky

Третий пункт не нужен.

"…прямым перебором "в лоб" - это ими?

[v_mirgorodsky]

Сообщение от doro

"…прямым перебором "в лоб" - это ими?

Нет, это все же не работниками Как я понял, они договориться между собой сами не могут

Просто создается массив работ, потом массив работников. Далее прога пытается учесть преференции работника по поводу работ и другие объективные факторы, заполняя план работ для каждого из работников по календарным дням. Далее, останутся частично "недозаполненные" работники - вот эти остатки и будем заполнять перебором. По мере уменьшения количества доступных работ количество вариантов будет быстро уменьшаться. Для ограничения количества вариантов стоит ограничить планируемый период определенной длительностью, к примеру, неделей. Тогда планирование месяца будет состоять из планирования четырех недель и еще 3-х дней. Даже самый старый PIII будет перебирать в секунду пару десятков тысяч вариантов. Однако будет необходимо аккуратно подойти к критерию определения хорошего варианта, иначе работа программы может затянуться

[doro]

all
Чего-то не понял к чему пришли в итоге.
Я то, например, находил в последовательности медианное или среднее арифметическое значение. Потом к наименьшему значению прибавлял, а от наибольшего отнимал тот коэффициент, с которым в данный момент работаем (начинаю всегда с наибольшего коэффициента), при условии, что результат сложения/вычитания не больше/меньше значения наибольшего/наименьшего значения последовательности в данный момент.
Но часто программа на этом моменте зацикливалась. Да и тяжело и не красиво как-то. Чувствую есть какое-то более элегантное решение.

[v_mirgorodsky]

Сообщение от doro

Я то, например, находил в последовательности медианное или среднее арифметическое значение. Потом к наименьшему значению прибавлял, а от наибольшего отнимал тот коэффициент, с которым в данный момент работаем (начинаю всегда с наибольшего коэффициента), при условии, что результат сложения/вычитания не больше/меньше значения наибольшего/наименьшего значения последовательности в данный момент.

А вот это и есть решение задачи методом прямого перебора "в лоб". Начальное приближение, взятое как "медианное или среднее арифметическое значение" относится к стратегии ведения перебора вариантов. В зависимости от выбора стратегии можно получить более быструю или медленную сходимость к приемлемому результату.

Сообщение от doro

Но часто программа на этом моменте зацикливалась.

Здесь, вероятнее всего есть алгоритмическая или логическая ошибка. Скорее логическая, поскольку алгоритмическая проявлялась бы более регулярно. Еще, возможно, недостаточно хорошо проработано условие выхода из циклов перебора и/или фиксации приемлемого варианта. BTW, необходимо очень аккуратно следить, чтобы следующая итерация перебора возможно меньше зависела от результатов предыдущей - иначе очень вероятны зацикливания на определенных наборах входных значений.

Сообщение от doro

Да и тяжело и не красиво как-то. Чувствую есть какое-то более элегантное решение.

К сожалению, все переборы не отличаются красотой и имеют ограниченную область применения. Возможно и есть более элегантное решение вашей задачи, однако с моими познаниями в дискретной математике оно не просматривается.