Einzelnen Beitrag anzeigen

Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
900 Beiträge
 
Delphi 11 Alexandria
 
#7

Re: Zahlenreihe in zwei Teile zerlegen -> gleiche Summen

  Alt 2. Aug 2009, 20:48
Das Problem nennt sich PARTITION und ist (schwach) NP-vollständig. Einen wirklich effizienten Algorithmus gibt es also höchst wahrscheinlich nicht.
Wenn die Zahlenwerte aber alle nicht zu groß sind, lässt sich das mit dynamischer Programmierung in (pseudo)polynomieller Zeit lösen (ist ja nur schwach NP-vollständig ), mehr dazu in der Wikipedia:

http://en.wikipedia.org/wiki/Partition_problem
http://en.wikipedia.org/wiki/Subset_sum_problem (da wird ein Algorithmus dazu erläutert, den man für Partition leicht modifizieren müsste)
Being smart will count for nothing if you don't make the world better. You have to use your smarts to count for something, to serve life, not death.
  Mit Zitat antworten Zitat