Максимальное количество групп, которые могут получить свежие пончики, распределенные партиями размера K
Дан массив arr[] , состоящий из N положительных целых чисел, таких, что arr[i] обозначает размер i -й группы, сидящей в магазине пончиков, и положительное целое число K , обозначающее максимальное количество пончиков, которые могут быть поданы в партии. , задача состоит в том, чтобы найти максимальное количество групп, которые могут получить свежие пончики, если клиенты одной группы будут обслуживаться вместе.
Примечание. Все клиенты в группе не получают оставшиеся пончики из предыдущей партии.
Примеры:
Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Output: 4
Explanation: One possible way for the ordering of the groups is {6, 2, 4, 5, 1, 3}.
- arr[0](= 6), The shops serve two batches of 3 donuts. So everyone gets fresh donuts.
- arr[1](= 2), The shop serves 3 fresh donuts, among which 1 gets left out. So everyone gets fresh donuts.
- arr[2](= 4), The shop serves first 1 leftover donut and then serves 3 fresh donuts.
- arr[1](= 5), The shop serves 6 fresh donuts, among which 1 is left out. So everyone gets fresh donuts.
- arr[1](= 1), The shop serves 1 leftover donut.
- arr[1](= 3), The shop serves 3 fresh donuts. So everyone gets fresh donuts.
Therefore, a total of 4 groups get fresh donuts which is the maximum possible number of groups.
Input: arr[] = {1, 3, 2, 5, 2, 2, 1, 6}, K = 4
Output: 4
Наивный подход: данная проблема может быть решена с помощью поиска с возвратом для всех возможных порядков, основанных на наблюдении, что необходимо только учитывать остаток каждого размера группы на K . Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте массив, скажем, V[] размером K , где V[i] обозначает количество групп, в которых осталось i человек.
- Пройдите по массиву arr[] с помощью переменной i и для каждого arr[i] увеличьте значение V[arr[i] % K] на 1 .
- Определите рекурсивную функцию, скажем, dfs(V, left) , где left — это количество оставшихся пончиков из предыдущей партии:
- Инициализируйте переменную res как 0 , чтобы сохранить результат текущего состояния.
- Если значение left равно 0 , выполните итерацию в диапазоне [1, K – 1], используя переменную i , и выполните следующие шаги:
- Уменьшите значение V[i] на 1 и рекурсивно вызовите функцию с аргументом left-i.
- Обновите res до максимума dfs(V, left – i) + 1 и res .
- Увеличьте значение V[i] на 1 для шага возврата.
- В противном случае повторите те же действия, что и выше, но в этом случае не прибавляйте к результату 1 , так как выбранная группа получит оставшийся пончик.
- Возвращает значение res .
- Вызовите рекурсивную функцию, определенную выше как dfs(V, 0), и сохраните возвращаемое значение в переменной, скажем, X .
- Наконец, после выполнения вышеуказанных шагов выведите в качестве результата сумму V[0] и X.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N + KK )
Вспомогательное пространство: O(K)
Эффективный подход: вышеприведенный подход имеет оптимальную подструктуру и перекрывающиеся подзадачи, поэтому описанный выше подход также можно оптимизировать, запоминая те же рекурсивные вызовы в HashMap и используя это состояние, когда одна и та же проблема вызывается рекурсивно.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N + K 2 )
Вспомогательное пространство: O(K)