| Autor |
Beitrag |
    
Wolfgang Gahrig (Coromandel)
| | Veröffentlicht am Freitag, den 01. Februar, 2002 - 09:35: | 
|
Nach welchem Verfahren kann man z.B. aus den Zahlen 561, 503, 419, 386, 269, 167, 147, 80, 52, 47, 34, 33, 26, 16, 15, 14, 6, 6, 4, 4, 4, 3, 2
diejenigen herausfinden, die die Summe 737 ergeben.
Das Resultat ist 419 + 167 + 147 + 4 = 737
Wie findet man diese Zahlen? |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 02. Februar, 2002 - 18:19: |
|
Das ist das so genannte Rucksackproblem. Hierfür gibt es keinen effizienten Algorithmus. Du musst probieren! |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 02. Februar, 2002 - 18:21: |
|
Ich muss mich korrigieren: Es ist kein effizienter Algorithnmus bekannt, aber die gesamte mathematische Welt glaubt, dass es keinen gibt. Falls du einen findest, kannst du Millionär werden ;-) |
Luis
| | Veröffentlicht am Samstag, den 02. Februar, 2002 - 20:37: |
|
Hallo Zaph, was genau verstehst du unter "effizient"?
nehme an, ein Algorithmus, bei dem alle Teilmengen der gegebenen Zahlenmenge auf ihre Summe hin ausgewertet werden, ist dann als "ineffizient" durchgefallen? |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 02. Februar, 2002 - 21:11: |
|
Es sind n Zahlen mit maximal m Ziffern. Setze k = max(m,n). Ein Algorithmus heißt dann "effizient", wenn es ein Polynom p(x) gibt, sodass der Algorithmus in maximal p(k) Schritten die Lösung berechnet.
Ein Algorithmus, der alle Teilmengen durchforstet, braucht dazu mindestens 2^n Schritte, da es so viele Teilmengen gibt, ist also nicht "effizient".
Du kannst übrigens nicht nur Millionär werden, sondern du wirst es - es gibt einen Wettbewerb, der diesen Preis für die Lösung ausgeschrieben hat!! |
|
