Selecting elements from two arrays to get a target sum

Question

Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.

Design an algorithm to solve the following problem.

For each index $i$ ($1\leq i \leq n$) either select $A[i]$ or $B[i]$ but not both such that the total sum of the picked elements from each of the arrays is at least $k$?

For example $A=[1,2,3,4,5,49]$ and $B=[1,10,10,10,22,12]$, target $k=50$.

Solution

Pick the first and the last elements from A whose sum is 50.

Pick the rest (all but the first and the last elements) from B. That sums up to 52.

So in both Arrays we get a sum at least the target value 50.

Can someone help me to find the algorithm to solve this problem?

Answer 1

Here is an algorithm using dynamic programming. Let us define the function $C:V\times \mathbb{N} \rightarrow \mathbb{N}$ as $C(i, s) = r$, if using only the first $i$ indices we can achieve a sum of at least $r$ in B, when having a sum at list $s$ in $A$. This means $C(i, s) = r$ if there is an index set $I \subseteq [i]$, such that $\sum_{j \in I} A[j] \geq s$ and $\sum_{j \in [i] \setminus I} B[j] \geq r$. If $s$ is greater than the sum of the first $i$ elements in $A$, then set $C(i, s) = -\infty$ It is easy to build the transitions of the dynamic programming as follows. For each $i$ and $s$: $$C(i+1, s) = \max\{C(i+1,s), C(i, s) + B[i]\}$$ $$C(i+1, s+A[i]) = \max\{C(i+1, s+A[i]), C(i, s) \}$$ The output is yes, if there is $s \geq k$ such that $C(n+1, s)\geq k$.

The correctness is pretty straight forward. The running time can be bounded in $O(nk)$.

On the other hand, this problem is NP-hard. It is easy to reduce the set partitioning problem to this problem. In the set partitioning problem, given a set of integers, you are asked to partition the set into two subsets having equal sums. Let $S$ be an instance of the set partitioning problem and $s$ be the sum of elements in $S$. Set $A = B = S$ and $k = s/2$. The correctness of the reduction is quite straight forward. That is why a pseudo polynomial algorithm (polinomial in the value of the input instead of its size) is the best we can hope for.