Наибольшее подмножество, сумма которого меньше заданной суммы

Вы можете использовать решение для динамического программирования, на которое ссылается @Apy. Вот пример Python:

def largest_subset(items, k):
    res = 0

    # We can form subset with value 0 from empty set,
    # items[0], items[0...1], items[0...2]
    arr = [[True] * (len(items) + 1)]

    for i in range(1, k + 1):
        # Subset with value i can't be formed from empty set
        cur = [False] * (len(items) + 1)

        for j, val in enumerate(items, 1):
            # cur[j] is True if we can form a set with value of i from
            # items[0...j-1]
            # There are two possibilities
            # - Set can be formed already without even considering item[j-1]
            # - There is a subset with value i - val formed from items[0...j-2]
            cur[j] = cur[j-1] or ((i >= val) and arr[i-val][j-1])
        if cur[-1]:
            # If subset with value of i can be formed store
            # it as current result
            res = i

        arr.append(cur)
    return res

ITEMS = [5, 4, 1]
for i in range(sum(ITEMS) + 1):
    print('{} -> {}'.format(i, largest_subset(ITEMS, i)))

Выход:

0 -> 0
1 -> 1
2 -> 1
3 -> 1
4 -> 4
5 -> 5
6 -> 6
7 -> 6
8 -> 6
9 -> 9
10 -> 10

В приведенном выше arr[i][j] это True, если установлено значение i, которое можно выбрать из items[0...j-1]. Естественно, arr[0] содержит только True значений, так как можно выбрать пустой набор. Точно так же для всех последовательных строк первой ячейкой является False, поскольку не может быть пустого набора с ненулевым значением.

Для остальных ячеек есть два варианта:

1. Если уже есть подмножество со значением i, даже без учета item[j-1] значение равно True
2. Если есть подмножество со значением i - items[j - 1], мы можем добавить к нему элемент и получить подмножество со значением i.

Насколько я вижу (поскольку вы рассматриваете подмассив как любые элементы исходного массива), вы можете использовать жадный алгоритм со сложностью O(N*log(N)) (вам нужно отсортировать массив) :

1. Assign entire array to the sub array
2. If sum(sub array) <= k then stop and return sub array
3. Remove maximim item from the sub array
4. goto 2

Пример

[1, 2, 3, 5, 10, 25] 
 k = 12

Решение

sub array = [1, 2, 3, 5, 10, 25], sum = 46  > 12, remove 25
sub array = [1, 2, 3, 5, 10],     sum = 21  > 12, remove 10
sub array = [1, 2, 3, 5],         sum = 11 <= 12, stop and return       

В качестве альтернативы вы можете начать с пустого подмассива и добавлять элементы от минимума к максимуму, пока сумма меньше или равна k:

sub array = [],               sum =  0 <= 12, add 1
sub array = [1],              sum =  1 <= 12, add 2          
sub array = [1, 2],           sum =  3 <= 12, add 3             
sub array = [1, 2, 3],        sum =  6 <= 12, add 5             
sub array = [1, 2, 3, 5],     sum = 11 <= 12, add 10             
sub array = [1, 2, 3, 5, 10], sum = 21 >  12, stop, 
                              return prior one: [1, 2, 3, 5]           

Посмотрите, для генерации набора мощности требуется время O(2^n). Это очень плохо. Вместо этого вы можете использовать подход динамического программирования.

Загляните сюда, чтобы узнать алгоритм. http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

И да, https://www.youtube.com/watch?v=s6FhG--P7z0 (Тушар все хорошо объясняет) :D

Предположим, что все положительно. (Обработка негативов является простым расширением этого и предоставляется читателю в качестве упражнения). Существует алгоритм O(n) для описанной задачи. Используя выбор медианы O(n), мы разбиваем массив на основе медианы. Находим сумму левой части. Если это больше, чем k, то мы не можем взять все элементы, поэтому мы должны вернуться к левой половине, чтобы попытаться взять меньший набор. В противном случае мы вычитаем сумму левой половины из k, затем возвращаемся к правой половине, чтобы посмотреть, сколько еще элементов мы можем взять.

Разделение массива на основе медианного выбора и повторение только одной из половин дает время выполнения n + n/2 + n/4 + n/8.., что геометрически суммируется до O (n).