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