Эффективный по времени алгоритм для решения «задачи о сумме подмножеств»

Question

A – множество целых чисел, B – подмножество множества A, состоящее из констатного числа элементов. N – количество элементов множества A, S – сумма элементов подмножества B.

То есть B – подмножество множества A, имеющее n элементов, где n < N, сумма которых равняется S.

N – 36, P – число бит для кодирования наибольшего числа множества A – 7.

Требуется определить количество подмножеств B и найти их. Упрощая, задача звучит так: нужно найти такие элементы из заданного набора, чтобы их количество равнялось n, а сумма была строго равна S.

Можете подсказать наиболее эффективный алгоритм для решения этой задачи?

Обновление: так сейчас выглядит функция (динамическое программрование):

int results[A_SET_SIZE][B_SET_SUM];
for (size_t i = 0; i < A_SET_SIZE; i++) {
    results[0][B_SET_SUM - 1] = 0;
}
for (size_t i = 1; i < A_SET_SIZE; i++) {
    for (size_t j = 0; j < B_SET_SUM; j++) {
        if (j > A[i]) {
            results[i][j] = max(results[i - 1][j], results[i - 1][j - A[i]] + A[i]);
        } else {
            results[i][j] = results[i - 1][j];
        }
    }
}

По формуле сочетаний удалось определить общее количество подмножеств с необходимым числом элементов – но как найти подходящие? Или, вернее, как найти среди них все те подмножества, что также удовлетворяют ограничению по сумме?

Пример: множество состоит из 4 элементов (A = {1, 2, 3, 4}). Нужно найти все такие подмножества, мощность которых равна 2, а сумма – 5. Получается, этим условиям удовлетворяют два подмножества: {1, 4} и {2, 3}. Задача именно в том, чтобы найти такие подмножества.

Answer 1

Эта задача решается с помощью meet-in-the-middle. Задача о рюкзаке. Работает за 2^{n/2}.

Однако, если число S невелико, можно использовать динамическое программирование, получится обычная задача о рюкзаке. В таком случае время работы будет составлять O(nS)

Answer 2

Для демонстрации подхода с динамическим программированием:

def findsums(l, n, summ):
    a = [[] for i in range(summ + 1)]  
    a[0].append((0,0))
    for v in l:
        for i in range(summ, v-1,-1):
            for p in a[i - v]:
                if p[1] < n:
                    a[i].append((v, p[1] + 1))
    print(a)
    return

findsums([1,2,3,4,5],2,5)

[[(0, 0)], [(1, 1)], [(2, 1)], [(2, 2), (3, 1)], [(3, 2), (4, 1)], [(3, 2), (4, 2), (5, 1)]]

Ячейки a содержат списки туплей (можно вместо списка туплей использовать мап или массив), в которых первый элемент - последнее использованное значение из списка, а второй - количество чисел в наборе, составляющий данную сумму. Сумма соответствует индексу ячейки

В последней ячейке списка лежит три варианта составить сумму 5, но третий - из одного слагаемого (я добавил в список 5), и не подходит. Вариант (3, 2) означает, что сумма 5 составлена из двух слагаемых, последнее из которых 3. Для получения набора слагаемых записываем 3, переходим в 5-3=2 ячейку. Там лежит (2, 1), значит, ещё одно слагаемое - 2. Аналогично находим вариант из слагаемых [4,1]

Answer 3

Если сделать динамику по двум состояниям dp[i][j], где i это сумма взытых элементов, и мы использовали предметы с индексами не больше j. Тогда ответом будет dp[S][N]. Мы учтем все множества с суммой равной S, но так же если сумма A равна S то мы посчитаем и полное множество. При случае когда суммы равны нам надо просто вычесть один вариант.

dp[0][0] = 1;
for(int j = 1; j <= N; ++j) {
    for(int i = 0; i <= S; ++i){
        if(A[j] <= i){
            dp[i][j] += dp[i - A[j]][j - 1];
        }
    }
}
int ans = dp[S][N];
if(sum(A) == S) {
    ans--;
}

Внимание, индексы в множестве A нумеруются с 1

БЛОГ НА HUSL

Эффективный по времени алгоритм для решения «задачи о сумме подмножеств»

Ответы (3 шт):