0
$\begingroup$

For problem explanation: https://www.geeksforgeeks.org/tug-of-war/

I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ideology of the solution. Also please mention if there are exceptions to this greedy or DP solution where it may not apply.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Can you explain what the tug of war problem is? $\endgroup$ – Yuval Filmus Jul 27 '18 at 10:42
  • $\begingroup$ geeksforgeeks.org/tug-of-war for problem explanation. $\endgroup$ – Navjot Singh Jul 27 '18 at 14:09
  • 1
    $\begingroup$ Your problem is NP-hard, by reduction from PARTITION. $\endgroup$ – Yuval Filmus Jul 27 '18 at 14:13
  • 1
    $\begingroup$ Please make your question self-contained, so we can understand the problem without visiting the link (and so if the link stops working the question still makes sense). Also, what have you tried? We have a guide on dynamic programming: cs.stackexchange.com/tags/dynamic-programming/info. It would be more helpful for you to try the systematic approach listed there, then show what progress you've made so far in the question, before asking. $\endgroup$ – D.W.♦ Jul 27 '18 at 19:23
0
$\begingroup$

There is a pseudo-polynomial solution with dynamic programming which runs in $O(S n^2)$ with $S = \sum_{i=1}^n |a_i|$.

Namely for each possible sum $s$ (between $\sum_{a_i < 0} a_i$ and $\sum_{a_i > 0} a_i$) compute, if you can choose a subset of size $\lfloor n/2 \rfloor$ with sum $s$. Using this information you can directly find the optimal solution.

You can compute this information it in a similar way as you would for a 0/1 knapsack problem, just with one dimension more:

$$f(s, m, i) = f(s-a_i, m-1, i-1) ~\vee~ f(s, m, i-1)$$ if $i > 0$ and $m > 0$, where $f(s, m, i)$ means "is it possible to choose a subset of size $m$ with sum $s$ using the first $i$ elements of the original array?".

| cite | improve this answer | |
$\endgroup$

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.