 |
 |
 |
 |
 |
|
Programmierung allgemein
Programmieren allgemein
Zahlenreihe in zwei Teile zerlegen -> gleiche Summen
Antwort
|
|
|
Registriert seit: 17. Jul 2005 916 Beiträge Delphi 12 Athens |
#1
Re: Zahlenreihe in zwei Teile zerlegen -> gleiche Summen
2. Aug 2009, 19: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_problemhttp://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.
|
Zitat
|
ForumregelnEs ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.
BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus. Trackbacks are an
Pingbacks are an
Refbacks are aus
|
|
Hybrid-Darstellung
