Напишите программу, которая получает на вход: Таблицу зависимостей курсов (она не обязательно совпадает с кафедральной, соблюдён только принцип)

• Приоритеты для курсов 2-го уровня.
• Выбранные курсы 3-го и 5-го уровней.
• Минимальное число курсов, которое нужно закрыть в каждом семестре

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

Выгрузим scv файл. Удалим лишнюю информацию и распарсим имя курса, его номер и зависимости. Представим всё в виде питоновского словаря.

Теперь по полученному словарю построим граф зависимостей предметов. Наш граф будет являться списком списков. Номер вершины - ключ, а значением будет список выходящих ребер. Для обозначения один из курсов будем использовать фиктивные ноды. Визуализируем наш граф зависимостей курсов с помощью графического дампа и проверим, что все зависимости распарились верно.

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

Оптимизировать его можно следующим образом: сначала найдем ВСЕ предметы, которые надо закрыть, считая опциональные как обязательные. Затем создадим фиктивную ноду в начале нашего академического пути, к которой подвяжем все ноды нулевого уровня. Дальше у ребер, идущих из вершин без зависимостей сделаем capacity равным единице. У ребер, идущих из вершин с обязательными зависимостями сделаем capacity равным сумме capacity зависимостей. И наконец у ребер, идущих от вершин с опциональными зависимостями сделаем capacity равным максимальной сумме capacity зависимостей. Стоимостью прохода по ребру сделаем единицу, а потока пускать будем <количество предметов в семестр> * <количество семестров>.

Подробнее читайте в 1C-task.ipynb.

Входные данные: на вход программа принимает номера курсов, которые необходимо закрыть.

Пример:

36 # приоритеты для курсов второго уровня.
48, 50, 52, 59 # выбранные курсы 3-го и 5-го уровней
3 # минимальное число курсов, которые нужно закрыть в каждом семестре

Вывод: номера курсов удовлетворяющих условию задачи. А именно: наименьшее число таких курсов с учетов приоритетов студента и с ограничением не менее 3-ёх курсов в семестр.

Пример:

59, 48, 58, 19, 36, 3, 31, 44, 6, 11, 2, 62, 43, 7