# Selecting elements from two arrays to get a target sum

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?

• cs.stackexchange.com/tags/dynamic-programming/info – D.W. Dec 4 '19 at 6:29
• You tagged this dynamic-programming from the start. D.W. supplied a link to the tag's info: Please follow the last paragraph's prompt to show your progress so far. – greybeard Dec 7 '19 at 4:42
• There's greedy (take next value from array with smaller partial sum), and there's greedy (in order of decreasing absolute differences, accumulate larger values until one partial sum reaches $k$, rest goes to the other one). – greybeard Dec 8 '19 at 9:13
• what running time are you looking for? would something like $O(kn)$ be good or is $k$ very large? – narek Bojikian Dec 8 '19 at 22:56

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.

• Is it not $c[i,s]+B[i+1]$ in the first line of the recursion. Also, can you cross-check the indices once. – Kumar Dec 16 '19 at 9:51
• Well you are right I made a small indexing mistake but $B[i+1]$ would miss the first element in $B$ (unless i starts with 0 but then we have to define everything for 0), I prefer to check $C(n+1,-)$ at the end instead – narek Bojikian Dec 16 '19 at 10:07