Hallo zusammen,
ich hab da eine auf den ersten Blick vieleicht einfache aber doch etwas komplexere Aufgabe. Vieleicht habt Ihr ja einen besseren Ansatz um an die Problematik heran zu gehen.
Es geht um folgendes:
Ein Bauer hat 12 Kisten mit Kartoffeln, von denen er jedes Gewicht der Kisten kennt. Jede der Kisten wiegt in etwa 2-3 kg.
Er möchte nun aus diesen 12 Kisten einen Kartoffelsack zusammenstellen, dessen Inhalt letztendlich möglichst genau oder nur wenig mehr als 10 kg Kartoffeln wiegen soll.
Natürlich will der Bauer nicht zuviel Zeit mit dieser Aufgabe verbringen also sucht er die schnellste (Laufzeitoptimierte Lösung).
Natürlich ist das ganze ein bisschen in Prosa aber im wesentlichen beschreibt es das Problem.
Mein erster Ansatz war nun jede Kombination von Kisten auszutesten und die Kombination zu wählen welche dem Ziel am nähesten kamm.
Hierzu müssen natürlich bei 12 Kisten 2^12=4096 Kombinationen durchlaufen werden und zu allem Überfluß für jede Kombination öfters mehr als nur eine Addition oder Subtraktion durchgeführt werden. Das kostet natürlich Zeit.
Mein nächster Ansatz war nun für das Durchlaufen der Kombinationen den Gray-Code anzuwenden, bei dem sich von einer Kombination zur nächsten lediglich eine Stelle ändert und somit auch nur eine Subtraktion bzw. Addition durchzuführen ist.
Das war schon etwas schneller.
Die Frage ist nun gibt es nicht vieleicht einen ganz anderen Lösungsansatz für die Problematik.
Vieleicht fällt Euch ja was ein.
Ich bin für jeden Ratschlag dankbar.
Gruß
Matthias