Проблема суммы подмножества, где сумма массива не превышает N

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

Дан массив arr[] размера N такой, что сумма всех элементов массива не превышает N, и массив query[] , содержащий Q запросов. Для каждого запроса задача состоит в том, чтобы найти, существует ли подмножество массива, сумма которого совпадает с query[i] .

Примеры:

Input: arr[] = {1, 0, 0, 0, 0, 2, 3}, queries[] = {3, 7, 6}
Output: 
Possible
Not Possible
Possible
Explanation: 3 is spossible. 6 can be obtained by the subset {1, 2, 3}
7 is greater than the sum o fall array elements.

Input: arr[] = {0, 1, 2}, queries[] = {1, 2, 3, 0}
Output:
Possible
Possible
Possible
Possible
Explanation: All the sums can be obtained by using the elements.

Подход : проблема может быть решена с использованием подхода, как в задаче о сумме подмножеств.
Однако временную сложность можно уменьшить, используя тот факт, что сумма может быть не больше N. Поскольку сумма может быть не больше N, можно доказать, что существует не более √2N уникальных положительных элементов, все из которых имеют частоту 1.

Say there are √2N unique positive elements starting from 1 to  √2N.
Therefore the sum of those numbers is N + √(N/2).
This sum is more than N itself. So there can be at most √2N unique elements.

Вышеизложенный факт может быть использован и реализован в динамическом программировании. Используя сжатие координат, все эти уникальные элементы можно хранить в минимальном пространстве.

For each element check what is the minimum contribution of that element to achieve a sum j (j in the range [0, N]) or if it is not possible to achieve the sum j. The contribution of each item (say i) depends on the contribution of the other smaller items till the sum (j – i). 

Следуйте изображению, показанному ниже, чтобы лучше понять разницу неиспользуемых состояний для нормального подмножества и когда сумма равна N при максимуме:

Сравнение:

Say the arr[] = {1, 2, 2, 2, 3, 3}. (Here sum is greater, so does not follow the condition of sum at most N. But here unique elements maintain the threshold. That’s why it is used here just for understanding purpose)

Red cells signify the useless states, these are much more in traditional algorithm than optimized one.

Traditional Subset-Sum vs Frequency Optimized DP, Useless States

Следуйте шагам, указанным ниже, чтобы реализовать подход;

  • Используйте сжатие координат для всех уникальных элементов.
  • Создайте двумерный массив dp[][] , где dp[i][j] хранит вклад i -го элемента для получения суммы j . (Если это невозможно, то сохраните – 1 , а если i -й элемент не нужен, то сохраните 0 в dp[i][j] ).
  • Итерация от i = 0 до максимального элемента:
    • Итерация для j = 0 до N :
      • Если значение dp[i][j-arr[i]] + 1 < dp[i][j] обновите его.
      • В противном случае оставить как было.
  • Затем выполните итерацию от i = 0 до Q:
    • Проверьте, возможна ли эта сумма (запрос [i]) или нет.
    • Это невозможно, если он превышает сумму массива или все элементы вместе не могут получить определенную сумму, т.е. dp[len][query[i]] = -1 . (len — общее количество уникальных элементов)

Ниже приведена реализация описанного выше подхода.

Временная сложность : O(N * √N)
Вспомогательное пространство: O(N * √N)

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