Минимальное количество дней для отладки всех программ

Учитывая N программных кодов и их соответствующее время отладки в массиве codeTime и целочисленном рабочем сеансе, i -й программе требуется codeTime[i] часов для завершения. WorkingSessionTime определяет пороговое время, когда вы работаете не более нескольких часов подряд в рамках WorkingSessionTime, а затем делаете перерыв. Если рабочее время сеанса меньше 6 часов, то Можно брать 2 рабочих сессии в день, иначе можно брать только одну рабочую сессию в день.

Отладка должна быть завершена при следующих условиях:

• Одна последовательность отладки должна быть выполнена в одном сеансе (в любом порядке).
• Новую задачу отладки можно запустить сразу после завершения предыдущей.

Задача состоит в том, чтобы напечатать минимальное количество дней , необходимое для отладки всех программ, соответствующих указанным выше условиям. Предположим, что значение WorkingSessionTime больше или равно максимальному элементу в массиве codeTime .

Примеры :

Input: codeTime[] = {1, 2, 3}, WorkingSessionTime = 3
Output: 1
Explanation: In first work session we will finish first and second task in 1+2 = 3 hours and we can finish last task in second work session, so the total 2 work session required to finish the task. WorkingSessionTime is less than 6 so we can take two session per day so minimum number of days  will be 1

Input: codeTime [] = {1, 2, 3, 1, 1, 3},  WorkingSessionTime = 4
Output: 2
Explanation : In first work session we will finish first and third task in 1+3 = 4 hours and in second session we can finish fourth and sixth tasks in 1+3 = 4 hours and in third session we can finish second and fifth tasks 2 + 1 = 3 hours. WorkingSessionTime is less than 6 so we can take two session per day . On first day we will take two working sessions and on next day we will take one working session. So minimum number of days required is 2

Подход: Простое решение — попробовать все возможные порядки задач. Начните с выбора первого элемента из массива, пометьте его как посещенный и выполните рекурсию для оставшихся задач и узнайте минимальные сеансы среди всех возможных заказов. Это в основном решение, основанное на отслеживании. После нахождения минимального количества сеансов мы проверим, меньше ли рабочих часов сеанса 6 или нет. Если оно меньше 6, мы дополнительно проверим, какие минимальные сеансы не являются четными или нечетными.

Оптимальный подход : лучшим решением является использование Битмаскинг и DP

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

• Инициализируйте маску как 000…000, которая представляет начальные (необработанные) состояния всех элементов.
• Передайте оставшееся время как 0, что означает, что для текущего сеанса не осталось времени, и мы должны создать новый сеанс.
• Проверяем, обрабатывается ли i-й бит или нет, делаем вызовы, если задача необработана . если i-я задача отладки программного кода не обработана, пометить ее как обработанную.
• Если оставшееся время больше , чем codeTime[i], мы включим i-ю задачу отладки программного кода в текущую сессию и обновим оставшееся время, иначе нам придется создать новую сессию и увеличить количество сессий на 1.
• Как только все элементы будут обработаны или маска станет равной 1, мы получим минимально возможные сеансы.
• Если время рабочего сеанса меньше 6, мы дополнительно проверим, является ли минимальное количество возможных сеансов четным или нечетным, если четное минимальное количество дней будет составлять половину от минимального количества сеансов, а если оно нечетное, минимальное количество дней половина минимального количества сеансов +1, иначе минимальное количество дней будет равно ответу.

Чтобы справиться с перекрывающимися подзадачами, создайте 2D-таблицу DP для хранения ответов на подзадачи . Для каждого элемента dp[i][j] я — маска, а j — оставшееся время.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(2^N * WorkingSessionTime * N), где N — длина массива codeTime.
Вспомогательное пространство : O(2^N * WorkingSessionTime), размер таблицы dp.