StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The problem you're asking about is <b>NP-Complete</b>, as it can be reduced to the <a href="https://en.wikipedia.org/wiki/Partition_problem" rel="nofollow">Partition Problem</a> (and the <a href="https://en.wikipedia.org/wiki/3-partition_problem" rel="nofollow">3-parition problem</a>). To see why, suppose <b>m = 2</b> and that the sum of weights of all objects is <i>S</i>. If the first set's sum is <i>S<sub>1</sub></i>, then obviously the the other set's sum <i>S<sub>2</sub></i> = S - <i>S<sub>1</sub></i>. Let's prove that if we can make <i>S<sub>1</sub></i> and <i>S<sub>2</sub></i> equal (the solution to partition problem), then this is the optimal solution for your problem.</p> <p>If <i>S<sub>1</sub></i> = <i>S<sub>2</sub></i> wasn't optimal, that means that there exists some way of partitioning such that the first set has a sum <i>S<sub>1</sub>'</i> that would yield a better solution (a smaller maximum number). Let's consider two cases:</p> <ul> <li><i>S<sub>1</sub>'</i> < <i>S<sub>1</sub></i>. In that case, -<i>S<sub>1</sub>'</i> > -<i>S<sub>1</sub></i> and thus S - <i>S<sub>1</sub>'</i> > S - <i>S<sub>1</sub></i>. Therfore the new maximum is larger (worse) than in the case of equal sums.</li> <li><i>S<sub>1</sub>'</i> > <i>S<sub>1</sub></i>. In this case, it immediately follows that the maximum in the case of the new partition is larger (worse) than in the case of equal sums.</li> </ul> <p>Similarly, you can show how you can reduce you problem to the 3-paritition problem. However, there are some heuristics that can help in solving the partition problem, you can read about them in the Wikipedia pages I linked to earlier; I doubt there's anything better than brute force for your more-generic version (unless there's some kind of restriction you didn't mention).</p> <p>Hope that helped you in any manner!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload