2

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}. Задача именно в том, чтобы найти такие подмножества.

5
  • Если значения целые, то динамическое программирование
    – MBo
    14 мар 2020 в 16:47
  • Подмножество - это маска или набор различных элементов? Если множество {1,1,1,1}, выбираем 3 элемента с суммой 3, то ответ 1 или 4? Или там изначально одинаковых элементов нет?
    – Qwertiy
    17 мар 2020 в 17:11
  • Надо помимо значения максимума хранить способ перехода. Кстати, а почему тут вообще максимум?
    – Qwertiy
    17 мар 2020 в 17:15
  • Насчет масок — подозреваю, это больше про реализацию, чем про сам алгоритм, если я правильно Вас понял. В данном случае, кажется, это неважно, потому что по маске можно восстановить значения, но оперировать подмножествами с уже внесёнными элементами, пожалуй, проще. Во множестве отсутствуют повторяющиеся значения, однако многократное использование одних и тех же элементов в подмножестве допускается. Формулировка задачи предполагает ограничение суммы элементов подмножества, — вроде, это вполне типично (та же задача о рюкзаке).
    – Marionette
    17 мар 2020 в 17:43
  • "многократное использование одних и тех же элементов в подмножестве" - звучит противоречиво. Или (под)множество, или сочетание с повторениями. Нужно уточнить постановку задачи. 30 ноя 2021 в 11:41

3 ответа 3

1

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

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]

10
  • Кажется, при v = 1, то есть при первой итерации, значения i будут находится в пределе [0; 5], соответственно, в строке for p in a[i - v] программа попытается обратиться к a[-1].
    – Marionette
    27 мар 2020 в 9:10
  • @Marionette Список обходится в обратном порядке, последнее значение i будет 1 (второй аргумент for в Python не входит в перечисление)
    – MBo
    27 мар 2020 в 9:21
  • Точно, извините, – нечасто приходится сталкиваться с Python. Есть еще вопрос – уточните, пожалуйста, функционирует ли алгоритм с произвольными множествами? Говоря в контексте C{'0','1','2','a','b'}, например, – не совсем разобрался. В этом случае требуется, чтобы сумма символов, вернее, их кодов, равнялась определенной сумме.
    – Marionette
    27 мар 2020 в 9:41
  • Да, будет, если на Python использовать ord('0') и т.д. для получения кода символов
    – MBo
    27 мар 2020 в 9:51
  • Большое время работы и огромное потребление памяти при мощности множества – 36, n – 12 и summ – 900. Хотя, судя по сложности, O(ns), работать должно весьма быстро.
    – Marionette
    27 мар 2020 в 11:56
0

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

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

5
  • Вы имеете в виду именно n – необходимое количество элементов в подмножестве B, – или все же N – мощность множества A? Если N, то, кажется, для первого алгоритма потребуется весьма много времени и памяти.
    – Marionette
    15 мар 2020 в 17:45
  • По ссылке указано, что полное число N
    – MBo
    16 мар 2020 в 5:12
  • Задача о рюкзаке принадлежит к NP-полным, поэтому алгоритм за 2^n это нормально. Вы не указали ограничения на числа, которые могут быть даны. n это мощность A, то есть n = N. По времени зайдет, с теми ограничениями, которые показали вы.
    – Gorix
    16 мар 2020 в 8:56
  • Можете, пожалуйста, подробнее описать применение динамического программирования? Нашел довольно много статей, но не совсем понял принцип работы и, соответственно, есть трудности с реализацией (обновил вопрос, посмотрите). Скажем, по формуле сочетаний удалось определить количество подмножеств с необходимым числом элементов, но как их найти? Или, вернее, как найти среди них все то, что также удовлетворяют ограничению по сумме?
    – Marionette
    17 мар 2020 в 13:15
  • С помощью динамического программирования можно посчитать только количество подходящих наборов, а вам нужно их вывести. Количество наборов может быть довольно велико, чтобы все наборы вывести нужно написать просто перебор.
    – Gorix
    18 мар 2020 в 17:13
0

Если сделать динамику по двум состояниям 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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.