Архив форумов ЦИТФорума

[100lyarov]

Просьба, если у кого есть алгоритм, а может и рабочая программа планирующая рабочее время, выложите плз.
В краце задача такова:
Составляем планировщик задач на день.
Есть рабочий день - 8,5 часов (0,5 часа перерыв на обед).
Пользователь вводит сабж и указывает сколько времени на это потребуется, потом следующий, и т.д.
Программа размещает все сабжи так, чтобы работа не пришлась на время обеда и на привысило 8 часов рабочего дня.

Спасибо.

[Yello]

На сегодняшний день такая задача решается только переборным алгоритмом (после ввода всех "дел", пока сумма превысит 8,5, а затем второй шаг - полный перебор вариантов, и останов как только получили требуемый вариант, ну или так, как тебе надо). А о сокращении полного перебора здесь, имхо, говорить просто смешно...

[100lyarov]

Я думал просто, что есть какой ни будь стандартный алгоритм. Ну попсовый, который применяется в задачах такого типа.
И на том спасибо.

[Yello]

А может кто-нибудь ещё чего поумнее скажет ? (А у меня получается, что такая задача - как раз из NP, как ни крути...)

[Kefir]

Да можно, какой-нибудь эвристический алгоритм придумать, который будет давать приемлемый результат. Или применить генетические алгоритмы.

Я так понимаю это вполне стандартная задача о распределении нагрузки, кажется у нас в Универе в этом году кто-то из бакалавров решал ее как раз генетическими алгоритмами.
_________________
Самоловских Виталий aka Kefir

[100lyarov]

не, ну я точно не баколавр и про такие генетические алгоритмы не в курсе. попытаюсь с помощью вложеных циклов сделать.

[Kefir]

Очень советую прочитать для начала хотя бы про задачу о рюкзаке, чтобы получить понятие, как такие задачи вообще решаются.
_________________
Самоловских Виталий aka Kefir

[100lyarov]

не подскажешь, что это за задачи и где про нее можно почитать?

[Kefir]

Это классика... Образно говоря, у тебя есть рюкзак, в который влезает n единиц. У тебя есть много вещей, каждая занимает m1,m2,m3 и т.д. единиц. Задача состоит в том чтобы заполнить рюкзак как можно полнее. Алгоритм точного решения имеет, кажется, экспоненциальную сложность.

А где почитать. гугл и яндекс всегда помогут.
_________________
Самоловских Виталий aka Kefir

[100lyarov]

спасибо. интересная штука.
и правда очень похоже на мою задачу.