3
$\begingroup$

I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!

Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{N}$ for $i=1,...,n$.

The goal is to determine whether there exist two disjoint subsets $M,N \subset A$ such that the sum of all elements in $M$ is equal to exactly $\textit{twice}$ the sum of all elements in $N,$ and $M \not = \emptyset$ and $N \not = \emptyset.$

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Let $t$ be the sum of all input values. I think your best bet will be an $O(nt^2)$-time, $O(t^2)$-space algorithm that generalises the usual Knapsack algorithm by looping through all items in some order, and generating all pairs of sums that can be formed from the first $i$ elements -- by adding the $i$-th item to either element of all pairs of sums $(a, b)$ that can be formed from the first $i-1$ items. At the end, look for pairs of the form $(a, 2a)$. This is only pseudopolynomial time, but I'm certain ordinary Knapsack can be reduced to this. $\endgroup$
    – j_random_hacker
    Apr 9, 2020 at 0:58
  • $\begingroup$ Ins't the answer trivially yes? Pick $M=N=\emptyset$. $\endgroup$
    – Steven
    Apr 9, 2020 at 16:00
  • $\begingroup$ That's my bad, both $M$ and $N$ must not be empty. Will add that in now. $\endgroup$
    – yellowsuzuki
    Apr 9, 2020 at 16:13
  • $\begingroup$ Thank you both for your answers! $\endgroup$
    – yellowsuzuki
    Apr 9, 2020 at 21:22

1 Answer 1

Reset to default
2
$\begingroup$

Let $\sigma(S)$ denote the sum of all the elements in $S$ and $A_i = \{a_1, \dots, a_i\}$.

Given, $i=0,\dots,n$ and $w \in \mathbb{Z}$, define $OPT[i,w]$ as the mazimum cardinality of a subset $S \cup S' \subseteq A_i$ where $S \cap S' = \emptyset$ and $\sigma(S) - 2\sigma(S') = w$. If no possible choice for $S$ and $S'$ exists, then let $OPT[i,w]=-\infty$.

According to the above definition: $$ OPT[0, w] = \begin{cases} 0 & \text{if } w=0 \\ -\infty & \text{if } w \neq 0 \\ \end{cases} $$

For $i>0$: $$ OPT[i, w] = \max\{ OPT[i-1, w], 1 + OPT[i-1, w-a_i], 1+ OPT[i-1, w+2a_i] \}. $$

The answer to your problem is true iff $OPT[n, 0] > 0$. Each $OPT[i, w]$ can be computed in constant time (if you have already computed the values of $OPT[i-1, \cdot]$). Moreover, there are only $O(n)$ possible choices for $i$ and $O(t)$ sensible choices for $w$, where $t = \sum_{i=1}^n a_i$. This gives you a dynamic programming algorithm with time complexity $O(n t)$ and space complexity $O(t)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That checks out!! Thanks a lot for the answer, appreciate it!! $\endgroup$
    – yellowsuzuki
    Apr 9, 2020 at 21:22
  • $\begingroup$ Nice answer! You could use a single bit for each $OPT[i,w]$, and set a global "solution exists" flag when some $OPT[i, 0]$ can be achieved from some $OPT[i-1, x]$ with $x \ne 0$. $\endgroup$
    – j_random_hacker
    Apr 9, 2020 at 21:51
  • $\begingroup$ @j_random_hacker, yep! My first write up used one bit per $OPT[i,w]$ but then I had the problem that $N=M=\emptyset$ would always be a solution. I thought of keeping two bits per $OPT[i,w]$ ("is there a solution?" and "is there a non-trivial solution?") but it felt "hacky" so I looked for a "natural" subproblem definition that would circumvent the problem altogether. $\endgroup$
    – Steven
    Apr 9, 2020 at 22:04

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.