Das deutsche Python-Forum

Hallo,

ich brauche mal einen kleinen Denkanstoß. Ich habe z.B. 64 Waagen und möchte möglichst genau an ein Wunschgewicht als Summe kommen.

z.B: Waage 1 = 60g, Waage 2 = 70, Waage 3 = 80 g, Waage 4 = 72 g
Das Ziel ist 131g, also soll das Ergebnis Waage 1 + Waage 2 oder Wage 1 + Waage 4 sein.

Wenn ich das allerding für alle 2^64 Kombinationen ausführen lasse dauert es ewig ...

Wie löst man solche Aufgaben?

Hardy

@HFlor: Grundsätzliche Überlegung: Du musst alle Möglichkeiten berücksichtigen, denn wenn Du ein Ergebnis hast, aber noch nicht alle Kombinationen geprüft hast, kann es ja sein, dass in den nicht geprüften ein besseres Ergebnis steckt.

Was man machen kann ist „branch and bound“, also schauen das man Wege im Suchraum nicht weiter verfolgt, die beispielsweise schlechter sind als das bisher beste Ergebnis, und da es keine negativen Gewichte gibt, auch nicht besser werden können. Falls „möglichst nahe“ bedeutet, dass das Wunschgewicht auch tatsächlich die Obergrenze ist, dann braucht man auch keine Wege zu verfolgen, deren Summe das Wunschgewicht überschreiten.

Nähere dich der Lösung schrittweise und werfe möglichst früh die Kombinationen raus, die garantiert nicht zum Ziel führen. So könntest du dir erstmal alle Kombinationen mit zwei Waagen ansehen. Ich würde dann bloß die Kombis behalten, die kleiner sind als das Ziel, sowie von den zu großen nur noch diejenige mit dem kleinsten Übergewicht. Die berechneten Kombis samt Gewichte kann man dabei zwischenspeichern, wenn sie ein vielversprechender Kandidat sind. Anschließend die verbliebenen Zweier-Kombis durchgehen und dabei eine dritte Waage hinzunehmen. Mit denen das gleiche Verfahren benutzen wie vorher, usw. Wenn man das halbwegs durchdacht hinbekommt, dann landet man letztlich bei dynamischer Programmierung.

Ich werfe mal zwei Möglichkeiten ein:

Genetische Algorithmen: https://www.pythonpool.com/python-genetic-algorithm/

und https://de.wikipedia.org/wiki/Simulated_Annealing