Найдите максимальную сумму подмножества, кратную D, взяв не более K элементов из заданного массива.

Учитывая массив A[] размера N и два числа K и D , задача состоит в том, чтобы вычислить максимальную сумму подмножества, кратную D , возможную, взяв не более K элементов из A .

Примеры:

Input: A={11, 5, 5, 1, 18}, N=5, K=3, D=7
Output:
28
Explanation:
The subset {5, 5, 18} gives the maximum sum=(5+5+18)=28 that is divisible by 7 and also has contains atmost 3 elements

Input: A={7, 7, 7, 7, 7}, N=5, K=2, D=7
Output:
14

Наивный подход: Наивный подход заключался бы в создании всех подмножеств A (с использованием битовой маскировки) и для каждого подмножества, вычислении суммы и проверке того, не превышает ли длина подмножества K , а сумма делится на D , и вычисление максимального среди них.

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

Временная сложность: O(N.2 ^N )
Вспомогательное пространство: O(1)

Эффективный подход: эта проблема может быть решена с помощью динамического программирования с помощью трехмерного массива dp, где dp[i][j][p] хранит максимально возможную сумму, если элементы j взяты до i -го индекса и его модуля D р . Следуйте инструкциям, чтобы решить проблему:

1. Создайте трехмерный массив dp[][][] размера ( N+1)x(K+1)x(D) и инициализируйте его значением -1.
2. Итерируйте от 1 до N и для каждого текущего индекса i сделайте следующее:
   1. Инициализировать элемент с двумя переменными и изменить их на A[i-1] и A[i-1]%D .
   2. Скопируйте dp[i-1] в dp[i].
   3. Итерируйте от 1 до K и для каждого текущего индекса j сделайте следующее:
      1. Обновите dp[i][j][mod] как максимум из dp[i][j][mod] и элемента.
      2. Итерируйте от 0 до D-1 и для каждого текущего индекса p сделайте следующее:
         1. Если dp[i-1][j-1][p] не равно -1, обновите dp[i][j][(p+mod)%D] как максимальное значение dp[i][j] [(p+mod)%D] и dp[i-1][j-1][p]+элемент.
3. Если dp[N][K][0] равно -1, ответ равен 0.
4. В противном случае ответ будет dp[N][K][0].

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

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