Rucksackproblem durch vollständige Enumeration |
| 28.03.2020, 13:22 | Thessa | Auf diesen Beitrag antworten » |
| Rucksackproblem durch vollständige Enumeration Liebe Community, ich hänge an einem Beispiel fest, das ich für einen Kurs lösen muss: Stellen Sie eine grobe Überschlagsrechnung an, bis zu welcher Instanzgröße n sich Instanzen eines Rucksackproblems, auf einem handelsüblichen PC innerhalb einer Stunde Laufzeit durch vollständige Enumeration, d.h. Durchprobieren aller zulässigen Lösungen, lösen lassen. Nehmen Sie dafür an, dass der PC 1 Million arithmetische Operationen pro Sekunde schafft. Konzentrieren Sie sich auf die Additionen, vernachlässigen Sie die Multiplikationen. Berechnen Sie außerdem jeweils Laufzeitschätzungen für n = 100. Meine Ideen: Ich hätte gedacht, dass die Anzahl der möglichen Teilmengen bei n Gegenständen 2^n beträgt. Wenn der PC 1 Mio in 1 sec schafft, so sind dies 60 Mio in 1h. Demnach sollte die Rechnung doch 2^n < 60.000.000 lauten und demnach darf n nicht größer als 25 sein. Aber warum der Hinweis mit der Vernachlässigung der Multiplikationen? Und die Laufzeitschätzung schaffe ich leider gar nicht... |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
