Минимизируйте количество рюкзаков с общим весом W, необходимых для хранения массива, содержащего элементов больше, чем W/3

Учитывая массив, arr[] и вес W . Задача состоит в том, чтобы минимизировать количество Рюкзаков, необходимых для хранения всех элементов массива. В одном рюкзаке может храниться максимальный общий вес W .
ПРИМЕЧАНИЕ. Каждое целое число в массиве больше (W/3).

Примеры:

Input: arr[] = {150, 150, 150, 150, 150},  W = 300
Output: 3
Explanation: Minimum of 3 Knapsacks are required to store all elements
Knapsack 1 – {150, 150}, Knapsack 2 – {150, 150}, Knapsack 3 – {150}. The weight of each knapsack is <= W.

Input: arr[] = {130, 140, 150, 160}, W = 300
Output: 2
Explanation: The knapsacks can be filled as {130, 150}, {140, 160}.

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

• Отсортируйте массив в порядке неубывания.
• Поскольку массив содержит элементы со значениями больше, чем W/3 , ни один рюкзак не может содержать более двух элементов.
• Сохраняйте два указателя L и R . Первоначально L = 0 , R = N-1 .
• Поддерживайте цикл while для значений L <= R .
• Для каждого L и R проверьте значение arr[L] + A[R] <= W . Если это так, то можно положить эти блоки в один и тот же рюкзак. Увеличьте L на 1 и уменьшите R на 1 .
• В противном случае в рюкзаке будет один элемент со значением arr[i] . Уменьшите R на 1 .
• Увеличивайте ответ для каждого допустимого шага.

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

Временная сложность: O (N * log (N))
Вспомогательное пространство: O(1)