Максимальное количество групп, которые могут получить свежие пончики, распределенные партиями размера K

Опубликовано: 22 Сентября, 2022

Дан массив 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}.

  1. arr[0](= 6), The shops serve two batches of 3 donuts. So everyone gets fresh donuts.
  2. arr[1](= 2), The shop serves 3 fresh donuts, among which 1 gets left out. So everyone gets fresh donuts.
  3. arr[2](= 4), The shop serves first 1 leftover donut and then serves 3 fresh donuts.
  4. arr[1](= 5), The shop serves 6 fresh donuts, among which 1 is left out. So everyone gets fresh donuts.
  5. arr[1](= 1), The shop serves 1 leftover donut.
  6. 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ