1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Dec 4 '19 at 6:29
  • $\begingroup$ 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. $\endgroup$ – greybeard Dec 7 '19 at 4:42
  • $\begingroup$ 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). $\endgroup$ – greybeard Dec 8 '19 at 9:13
  • $\begingroup$ what running time are you looking for? would something like $O(kn)$ be good or is $k$ very large? $\endgroup$ – narek Bojikian Dec 8 '19 at 22:56
3
+25
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Is it not $c[i,s]+B[i+1]$ in the first line of the recursion. Also, can you cross-check the indices once. $\endgroup$ – Kumar Dec 16 '19 at 9:51
  • $\begingroup$ 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 $\endgroup$ – narek Bojikian Dec 16 '19 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.