UNItopia News: Brett Computer, Gruppe Allgemeines, Artikel 1737

-------------------------------------------------------------------------------
Titel: Idee oder Algorithmus gesucht
Artikel: 1737                                          Bezug: 0
Verfasser: Serrin                                      Datum: 03.03.05 16:34:13
-------------------------------------------------------------------------------
Ich verzweifele hier an einem Problem und hoffe, dass einer von
Euch vielleicht eine Idee hat, wie man das am geschicktesten
loesen kann.

Ich habe eine Reihe von unterschiedlichen Werten, von denen (ein
Teil) so addiert werden soll, dass sie eine gesuchte Summe x ergeben.
Die addierten Teilwerte duerfen x nicht unterschreiten, sollen es aber,
wenn x nicht exakt gebildet werden kann nur minimal uebersteigen.

Ein einfaches Beispiel:

x   = 11
v[] = { 6, 4, 4, 3 }

Optimale Kombination: 4 + 4 + 3 = 11


x = 11
v[] = { 7, 5, 3, 2 }

Optimale Kombination: 7 + 3 + 2 = 12 oder 7 + 5 = 12



Mein Problem ist nun, dass sowohl x als auch die Anzahl der Teilwerte
sehr gross sein kann.
Meine erste Idee war, zuerst den groessten Teilwert zu nehmen der
kleiner als x ist, dann den naechsten Teilwert der kleiner als der
Rest ist, und so weiter.
Leider ergibt das in den seltensten Faellen eine optimale Loesung,
sondern ist ueberschreitet x mehr als notwendig.

Ich hoffe ich hab das Problem halbwegs verstaendlich formuliert, bei
sowas bin ich nicht wirklich begabt :)

Gruss, Serrin.