2
$\begingroup$

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next?

To illustrate this problem let's take a look at this example: {100,1,2,3}.

The p-p algorithm will give an answer False, and then I can end with result: This set can be partitioned into two set with different 106-6 = 100

(The 6 is the last result from p-p algorithm on with [_][vector.size()] = True, the 106 is the sum of all digits).

But what if I really would like to know the maximum by sum two-split of this set in which every subset has the same sum - for example the result that I'm looking for should be 3. This set - {100,1,2,3} can be split (by bypassing the 100) into two subset with the same sum - {1,2} and {3}.

How can I achieve this result?

$\endgroup$
2
$\begingroup$

You can extend the dynamic programming algorithm to handle this variant. Suppose that the weights are $w_1,\ldots,w_n$. You are looking for a vector $x \in \{0,\pm 1\}^n$ such that $\sum_{i=1}^n x_i w_i = 0$, and $\sum_{i=1}^n |x_i| w_i$ is as large as possible. This suggests two possible approaches. The first approach is to construct a large table keeping track of all possible pairs of values $(\sum_{i=1}^m x_i w_i, \sum_{i=1}^m |x_i| w_i)$, where $x_1,\ldots,x_m \in \{0,\pm 1\}^m$. This leads to an $O(nM^2)$ algorithm, compared to the $O(nM)$ subset-sum or partition algorithms.

The second approach is to explicitly list all vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$ (using dynamic programming), and choose the one maximizing $\sum_{i=1}^n |x_i| w_i$. This takes time $O(nM + nS)$, where $S$ is the number of vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$. In practice $S$ might be small enough for this approach to be practical.

$\endgroup$
  • $\begingroup$ It should be more simple if I know that all of the numers are positive integers and the sum S is less then 10^6. $\endgroup$ – kowal66b Mar 27 '15 at 11:06
  • $\begingroup$ could you please help with this second approach and write down the simple pseudo code with I can fallow. Thank you. $\endgroup$ – kowal66b Mar 27 '15 at 12:32
  • $\begingroup$ No, writing pseudocode is your job. $\endgroup$ – Yuval Filmus Mar 27 '15 at 13:34
  • $\begingroup$ Ok, but I'm just wondering about the proccess of filling the table. Should I fill it with minimal value of previous states (set with less numbers) + {-1,0,1}*(next w_i) and after that backtracking the result that have sum of all = 0? $\endgroup$ – kowal66b Mar 27 '15 at 13:47
  • $\begingroup$ You should keep track of all possible values of $\sum_{i=1}^m x_i w_i$ at any given point. Whenever you find that $0$ is possible, you go back and construct the corresponding $x$s. That's the basic idea. $\endgroup$ – Yuval Filmus Mar 27 '15 at 13:49

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.