Подсчет подмножеств индексов, для которых максимум значений этих индексов в A равен как минимум общей сумме по B

Опубликовано: 21 Сентября, 2022

Даны два массива A[] и B[] , состоящие из N положительных целых чисел, задача состоит в том, чтобы найти общее количество подмножеств индексов, такое что максимальное значение в массиве A[] по всем этим индексам больше или равно сумма всех значений по этим индексам в массиве B[] .

Примеры:

Input: A[] = {3, 1}, B[] = {1, 2}
Output: 2
Explanation:
The total possible valid subsets of indices are {0}, {0, 1}
{0}: max(3) >= sum(1)
{1, 2}: max(1, 3) >= sum(1, 2)

Input: A[] = {1, 3, 2, 6}, B[] = {7, 3, 2, 1}
Output: 6

Подход: Вышеупомянутая проблема может быть решена с использованием концепции, обсуждаемой в задаче о сумме подмножеств, с помощью динамического программирования. Идея состоит в том, чтобы создать dp[][] размеров N *maximum элемента массива A[]. Теперь каждый узел матрицы dp[][] , т. е. dp[i][j] , представляет количество подмножеств первых i элементов, имеющих сумму j . Выполните следующие шаги, чтобы решить эту проблему:

  • Создайте переменную, скажем , как 0 , чтобы сохранить общее количество необходимых подмножеств.
  • Создайте вектор пар, скажем, AB , и заполните его элементами A и B, т. е. AB[i] = {A[i], B[i]} .
  • Отсортируйте этот вектор пар на основе первого элемента.
  • Изначально таблица dp будет заполнена нулями, кроме dp[0][0] = 1 .
  • Пройдите массив AB[] и считайте значение AB[i].first максимальным, потому что AB сортируется по первому элементу и максимально в диапазоне [0, i] и на каждой итерации проходит через все возможные суммы j и для каждой итерации вычислить подмножества до индекса i , имеющего сумму j , включая и исключая текущий элемент.
  • После выполнения вышеуказанных шагов пройдите по матрице dp[][] и проверьте, сколько сформированных подмножеств допустимо, проверив следующие условия. Если окажется, что это правда , то добавьте значение dp[i – 1][j] к переменной ans .

j + AB[i – 1].second <= AB[i].first

  • После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M), где M — максимальный элемент в массиве .
Вспомогательное пространство: O(N*M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ