Минимизируйте операции передачи, чтобы получить заданную сумму массива

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

Примеры

Input: N = 4, M = 3, targetSum = 12,  A[] = {1, 2, 1, 4}, B[] = {5, 12, 11}
Output: 2
Explanation: We can do the following two operations
1) Transfer 1 from A[] to B[]
2) Transfer 5 from B[] to A[]
So, the array becomes 5 + 2 + 1 + 4 = 12, which is equal to the target sum.

Input: N = 4, M = 5, targetSum = 12, A[] = {7, 2, 4, 3], B[] = {8, 1, 1, 7, 9}
Output: 1
Explanation: We can do the following two operations
1) Transfer 4 from A[] to B[]
So, the array becomes 7 + 2 + 3 = 12, which is equal to the target sum.

Подход: Реализуйте идею ниже, чтобы решить проблему:

We can reduce this problem into subproblems. Let’s say elements with sum p are transferred from array A[] to array B[] and elements with sum q are transferred from array B[] to array A[]. So, the number of operations will be minimum when we take minimum number of elements from array A[] with sum p and minimum number of elements from array B[] with sum q. 

This Problem can be solved by using Dynamic Programming, where we have to find minimum number of elements in an array with a given sum.

Для реализации идеи выполните следующие шаги:

• Создайте два динамических массива (скажем, dp1[][] и dp2[][] ).
• Пусть dp1[i][j] представляет собой минимальное количество элементов, необходимых в массиве A для получения суммы j до индекса i – 1, аналогично, dp2[i][j] также может быть определено для массива B[] таким же образом .
• Мы можем создать dp1[][] и dp2[][], используя это преобразование dp[i][j] = min (dp[i – 1][j], dp[i – 1][j – a[i – 1]] + 1).
• Конечным значением массива A[] будет targetSum, пусть p будет суммой, удаленной из массива A[], а q будет суммой, удаленной из массива B[] (добавленной в массив A). Тогда общее количество операций будет dp1[N][p]+dp2[M][q] .
• Итерация от p = 0 до p = sum1 (где sum1 — начальная сумма значений массива A). Мы знаем, что targetSum = sum1 – p + q , тогда q будет targetSum – sum1 + p .
• Ответ будет минимальным из всех dp1[N][p] + dp2[M][q] от p = 0 до p = sum1.

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

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Введение в динамическое программирование — учебные пособия по структурам данных и алгоритмам