Strange! The german wikipedia page states "Gesucht wird eine Aufteilung dieser Zahlen auf zwei Haufen, so dass die Differenz der Summen der Zahlen in den beiden Haufen möglichst klein ist." (Find a partition such that the diffference of the sum of each heap is minimal). And this is exactly what you're after.
s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%
+.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e
| [reply]
[d/l]
[select] |
I guess I'll be totally fine with that if the German definition is true and there is a way of implementing that in perl.
Any ideas on how to do it? I can't read German.
| [reply] |
| [reply]
[d/l]
[select] |
I read about it, but the Partition Problem just tells you if the list of numbers can be partitioned into 2 halves that have the same sum. I'm not really interested into checking that. I don't mind them having the same or different sum. I only want the best possible partition. Thanks anyway.
Note that the problem you are describing is (at best) just as hard as the original. Namely, if you can solve your problem, then you can solve the problem of finding a partition into equal halves by finding the best partition, and noting whether the difference in sums is 0.
UPDATE: Oops, sorry, both moritz and jethro pointed that out already.
| [reply] |
If you had an algorithm that found the best possible partition and there is one with difference 0 (for some array of integers) then your algorithm would find that one, otherwise you would find a difference>0. So your algorithm would be a solution to the partition problem.
| [reply] |
But to find out if your solution is the best partition (and it's value is not sum/2) you have to check if there is a possible better partition, which means checking if the partition with the value sum/2 exists. Thus you have to solve the partition problem. D'oh. | [reply] |