1

Тема: NP-полная задача

Условие:

Группа студентов сдает экзамен. В билете 2 вопроса и задача. Экзамен принимают 2 преподавателя, один принимает теорию, другой задачу, порядок сдачи вопросов билета фиксирован. Время, требующееся для сдачи каждым студентом каждой части билета известно. Успеют ли преподаватели принять экзамен в течение N часов? Предложить порядок сдачи экзамена, чтобы время сдачи было минимально.

class Program
    {
        static int Count = 0, N = 0; // кол-во студентов и время экзамена
        static int[] timeT; // время требующееся для сдачи теории каждым студентом
        static int[] timeZ; // то же для задачи
        static bool[] sdalT;// сдал теорию
        static bool[] sdalZ;//задачу

        static bool solve(int k)
        {
            // ??

        }

        static void Main(string[] args)
        {
            //ввод
            StreamReader r = new StreamReader("input.txt");
            string[] tmp = r.ReadLine().Split(' ');
            Count = Convert.ToInt32(tmp[0]);
            N = Convert.ToInt32(tmp[1]);
            string[] tmp1 = r.ReadLine().Split(' ');
            string[] tmp2 = r.ReadLine().Split(' ');
            timeT = new int[Count];
            timeZ = new int[Count];
            sdalT = new bool[Count];
            sdalZ = new bool[Count];

            for (int i = 0; i < Count; i++)
            {
                timeT[i] = Convert.ToInt32(tmp1[i]);
                timeZ[i] = Convert.ToInt32(tmp2[i]);
            }
            r.Close();
            //
            // решение
            if (solve(0))
            {
                // вывод ответа
            }
            else Console.WriteLine("Преподы не успеют принять экзамен за {0} минут", N);
            Console.ReadKey();
        }
    }

Не удается решить рекурсивно sad Задача вроде как о составлении расписания для 2х процессоров

2

Re: NP-полная задача

Неужели никто не знает?

3

Re: NP-полная задача

Ограничения хоть бы написал.

4

Re: NP-полная задача

Какие ограничения ?

5

Re: NP-полная задача

Известно в этой задаче какое максимальное количество студентов может быть ?

6

Re: NP-полная задача

Нет, максимальное кол-во не известно

7

Re: NP-полная задача

Вроде http://e-maxx.ru/algo/johnson_problem_2 твой случай.

8

Re: NP-полная задача

Oleg, спасибо!

А реально ли этот алгоритм свернуть в рекурсию ?

9

Re: NP-полная задача

Рекурсия / бектракинг / перебор / динамику тут можно сделать если бы точно можно было бы сказать что студентов не больше 20.  А так - даже не знаю smile