Einzelnen Beitrag anzeigen

Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
885 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)
The angels have the phone box.
  Mit Zitat antworten Zitat