Подсчитать количество подпоследовательностей данного массива так, чтобы их сумма была меньше или равна заданному числу?
У меня есть массив размера n целочисленных значений и заданного числа S,
1<=n<=30
Я хочу найти общее количество подпоследовательности такой, что для каждого подпоследовательности сумма элементов меньше чем S,
Например: позволять n=3 , S=5и элементы массива будут как {1,2,3}тогда его общие подпоследовательности будут 7 как-
{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}
но необходимые подпоследовательности:
{1},{2},{3},{1,2},{1,3},{2,3}
то есть {1,2,3}не берется, потому что его сумма элемента (1+2+3)=6который больше чем S то есть 6>S, Другие взяты потому, что для других элементов подпоследовательностей сумма меньше S,
Таким образом, общее количество возможных подпоследовательностей будет 6,
Таким образом, мой ответ является подсчет, который6,
Я пробовал рекурсивный метод, но сложность его времени 2^n,
Пожалуйста, помогите нам сделать это за полиномиальное время.
Решение
Вы можете решить это за разумное время (возможно), используя псевдополиномиальный алгоритм для задачи о ранце, если числа ограничены положительными (или, технически, нулевыми, но я собираюсь предположить положительными). Это называется псевдополином, потому что он работает в nS время. Это выглядит полиномом. Но это не так, потому что проблема имеет два параметра сложности: первый — это n, а второй — это «размер» Sколичество цифр в SНазовите его М. Так что этот алгоритм на самом деле n 2^M,
Чтобы решить эту проблему, давайте определим двумерную матрицу A, Она имеет n строки и S колонны. Мы скажем, что A[i][j] количество подпоследовательностей, которые могут быть сформированы с использованием первого i элементы и с максимальной суммой не более j, Сразу отметим, что нижний правый элемент А является решением, т.е. A[n][S] (да, мы используем индексирование на основе 1).
Теперь мы хотим формулу для A[i][j], Обратите внимание, что все подпоследовательности, использующие первый i элементы либо включают в себя ith элемент или нет. Количество подпоследовательностей, которые не являются просто A[i-1][j], Количество подпоследовательностей, которые делают это просто A[i-1][j-v[i]], где v[i] это просто значение i-го элемента. Это потому, что, включив i-й элемент, нам нужно сохранить остаток суммы ниже j-v[i], Таким образом, добавив эти два числа, мы можем объединить подпоследовательности, которые содержат и не включают j-й элемент, чтобы получить общее число. Таким образом, это приводит нас к следующему алгоритму (примечание: я использую индексирование на основе нуля для элементов и i, но 1 основано на j):
std::vector<int> elements{1,2,3};
int S = 5;
auto N = elements.size();
std::vector<std::vector<int>> A;
A.resize(N);
for (auto& v : A) {
v.resize(S+1); // 1 based indexing for j/S, otherwise too annoying
}
// Number of subsequences using only first element is either 0 or 1
for (int j = 1; j != S+1; ++j) {
A[0][j] = (elements[0] <= j);
}
for (int i = 1; i != N; ++i) {
for (int j = 1; j != S+1; ++j) {
A[i][j] = A[i-1][j]; // sequences that don't use ith element
auto leftover = j - elements[i];
if (leftover >= 0) ++A[i][j]; // sequence with only ith element, if i fits
if (leftover >= 1) { // sequences with i and other elements
A[i][j] += A[i-1][leftover];
}
}
}
Запуск этой программы, а затем вывод A[N-1][S] дает 6 по мере необходимости. Если эта программа не работает достаточно быстро, вы можете значительно улучшить производительность, используя один вектор вместо вектора векторов (и вы можете сэкономить немного места / перфорации, не тратя впустую столбец для 1-индекса, как я сделал ).
Другие решения
Да. Эта проблема может быть решена за псевдополиномиальное время.
Позвольте мне переопределить постановку задачи как «Подсчитать количество подмножеств, которые имеют SUM <= К «.
Ниже приведено решение, которое работает в O (N * K),
где N — количество элементов, а K — целевое значение.
int countSubsets (int set[], int K) {
int dp[N][K];
//1. Iterate through all the elements in the set.
for (int i = 0; i < N; i++) {
dp[i][set[i]] = 1;
if (i == 0) continue;
//2. Include the count of subsets that doesn't include the element set[i]
for (int k = 1; k < K; k++) {
dp[i][k] += dp[i-1][k];
}
//3. Now count subsets that includes element set[i]
for (int k = 0; k < K; k++) {
if (k + set[i] >= K) {
break;
}
dp[i][k+set[i]] += dp[i-1][k];
}
}
//4. Return the sum of the last row of the dp table.
int count = 0;
for (int k = 0; k < K; k++) {
count += dp[N-1][k];
}
// here -1 is to remove the empty subset
return count - 1;
}