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

#массивы #алгоритм

Здравствуйте. Дан массив A из N натуральных чисел. Нужно найти размер подмассива
A максимальной длины, сумма элементов которого не превосходит K.

Пример:

A = [1, 4, 2, 3]
K = 6

Ответ: 3 (подмассив [1, 2, 3])


Правильно ли я думаю, что если отсортировать массив, то ответом будет количество
первых элементов массива, сумма которых не превосходит К? И есть ли способ получше?
    

Ответы

Ответ 1

Если ваша интерпретация постановки задачи действительно верна, то предложенный вам
алгоритм - верен. Однако можно предложить более эффективное решение. 

Вы можете применить обыкновенный алгоритм quick sort с дополнительной модификацией. 


Если после выполнения partitioning оказывается, что сумма элементов в левой (меньшей)
части массива не меньше чем K, то правая часть массива вас больше не интересует и тратить
время на дальнейшую сортировку правой части никакого смысла нет.
В случае же, когда сумма элементов в левой (меньшей) части массива меньше чем K,
вы сразу знаете, что все элементы левой части заведомо входят в искомый подмассив и
тратить время на дальнейшую сортировку левой части никакого смысла нет.


Это та же самая стратегия, по которой работает классический алгоритм поиска "k наименьших
элементов", с той только разницей, что вы ищете не k наименьших элементов, а неизвестное
число наименьших элементов, чья сумма не превосходит K.

Таким образом на каждом уровне рекурсивного подразбиения вам нужно выполнять рекурсивный
вызов только для одной половины подразбиения, в то время как вторая половина либо полностью
игнорируется, либо просто целиком отправляется на выход (и затем игнорируется). Такой
алгоритм должен легко допускать истинно циклическую реализацию, без использования стека.


Ответ 2

Может, тут подразумевается решение без сортировки?

Типа, может быть и несколько подмассивов, но разной длины (пример не удачный :) три
подмассива одинаковой длины).

subArray[0] {1, 4}; subArray[1] {4, 2}; subArray[2] {2, 3};