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?
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.