Задали написать программу или веб-приложение, решающее следующую задачу (скрин): 

Реально ли уложиться в условие - время выполнение 10 сек? 
Язык - желательно php, поэтому здесь и пишу... Однако, возможно и на С/С++
Натолкните на идею, если такую задачу можно решить     

Если переведешь на русский, то наверняка появятся куча советов, как решить задачу

Задача М. Эффективный процесс.

В однм из химических производств процесс производства вещества состоит из повторяемых циклов-процессов. Процесс состоит из 8 подпроцессов, которые имеют номера 1-8. Процессы должны быть запущены по одному, не ранее чем через один интервал времени Т. Подпроцессы имеют различную длительность, возможности совмещения во времени. условия запуска, согласно таблицы (на скрине)
Эффективность процесса оцениваем показателем эффективности, который рассчитываем как разность между показателем качества вещества, который без нарушения условий равен 8, а каждое нарушение условий отнимает 1.5 и показателем длительности процесса, который равен длительности подпроцесса в количестве интервалов Т, деленной на 5. Программа должна напечатать 2 лучших последовательности номеров подпроцессов и их показатели .

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

что обозначают условия запуска подпроцесса: если, например, стоит условие "-5", то это значит что подпроцесс должен быть запущен перед подпроцессом №5, а положительное число - подпроцесс должен быть запущен после подпроцесса с указанным номером.

Воник вопрос, запускаем мы 6й процесс который совместим с 3м.

На втором шаге мы запускаем 3й процесс, который совместим с 6.

На третем шаге что? Другие процессы не совместимы? Ждем ?

Если ждем, тогда о каких нарушениях идет речь в условиях? Если не ждем, то нарушаем процесс ? или как?

awdev, 
условия: (-8) - процесс должен быть запущен после 8-го, (5) - перед 5-м. 

На совместимость можно забить, проверял вручную, что с ней, что без нее, результаты те же. то есть, суть в том, чтобы выбрать все числа из диапазона 12345678-88888888, в которых нет нарушения условий совместимости, и потом  с ними уже посчитать показатель эффективности...
но перебор банальным for($i=12345678; $i<88888889;$i++){}
это зло, в 10 сек не уложится ни за что...

NFL, 
у тебя 8! перестановок с учетом ограничений еще меньше.
Цикл тебе нужен по перестановкам. И 40к комбинаций уложить в 10с более чем реально

Simpliest, пример можно?  что то туплю...

12345678
21345678
23145678
...
87654321

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

Не совсем ясны условия задачи.
1. То что подпроцессы могут быть совмещены по времени - это означает, что совместимые подпроцессы могут быть запущены одновременно (т.е. суммарное время их выполнения всегда равно max(T1, T2))? Или же все-таки учитывается  условие, что подпроцесс может быть запущен не ранее чем через 1 ед. времени (т.е. суммарное время max(T1,T2+1) или max(T2,T1+1) в зависимости от порядка)?
2. Условие запуска означает, что подпроцесс должен быть выполнен непосредственно перед/после указанного подпроцесса? Или же между ними могут быть выполнены другие подпроцессы без нарушения условия процесса?
3. Могут ли быть взаимнопротиворечащие друг другу условия? Т.е. когда в принципе невозможно завершить процесс без нарушения хотя бы одного условия?
4. Пример в задаче какой-то совсем абсурдный, даже если исправить опечатки и предположить, что взаимнопротиворечащие условия возможны, то все равно как не крути, но эффективность 3.4 для первой строки и 3.3 для второй ну никак не получается.


Это не интересно  


Я думаю, что тут суть не в том, что бы уложить решение задачи во времени в 10с, а в том, что бы найти более оптимальный алгоритм, нежели полный перебор всех возможных вариантов.

Это сообщение отредактировал(а) sTa1kEr - 2.12.2009, 00:57

sTa1kEr, 

1.  max(T1,T2+1) или max(T2,T1+1
2. Нет. Главное, чтобы именно перед или после.
3. Нет
4. Ну у меня 3.4 получилось, а 3.3 тоже никак(

Ну да это не важно, что там в примере, главное чтоб хоть как то считал... Хотя бы саму идею в коде, ибо я вообще в шоке от задачи(=)

NFL, 
Найти все комбинации

Добавлено через 1 минуту и 58 секунд

Не прикалывайся. 
Я за свою недолгую жизнь не смог придумать ни одного нового алгоритма. Максимум заново открывал уже существующие.

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

Добавлено через 2 минуты и 26 секунд

Это сильно упрощает задачу, но тогда пример в задаче совершенно не корректен.

Не всех возможных, а всех разрешеных.

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

Разрешены абсолютно все комбинации.


Да неужели? Я уже вижу как можно решить задачу с перебором в лучшем случае только двух вариантов  

Это сообщение отредактировал(а) sTa1kEr - 3.12.2009, 07:26