Das deutsche Python-Forum

Sagen wir einmal ich habe folgendes Setting: Ich kann eine bestimmte Ladung verschicken und zwar einmal eine Ladung pro Transport und einmal 4 Einheiten pro Transport, muss allerdings beim 4er Transport zwei "Runden" aussetzen und kann in dieser Zeit keine Ware verschicken. Im Zielort muss ich im Lager eine jeweils wechselnde Zahl an Ladungen hinterlegen, also z. B. 3 Einheiten, 5 Einheiten oder 8 Einheiten.

Man kann recht schnell sehen, dass ich 5 Einheiten am Besten aufbaue nach dem Muster: Verschicke eine Einheit, Warte, Warte, verschicke 4er Transport = 5 Einheiten im Zielort bei nur benötigten 4 Runden ggü. Verschicke, Verschicke, Verschicke, Verschicke, Verschicke = 5 Einheiten, aber 5 Runden.

Wie kann ich so ein Problem elegant berechnen? Ich scheitere im Moment bereits an der Frage der Kombinatorik, also wie ich alle möglichen Kombinationen effizient zusammenstelle (normalerweise würde ich bei itertools schauen, aber das scheint mir hier ein zu komplexes Problem). Gibt es eine geeignete Datenstruktur, die man hier nutzen könnte (Entscheidungsbaum, Graph o. ä. - sagt mir bislang alles noch nichts).

Für dein konkretes Problem reicht der Modulo-Operator.

Und wenn du mehr Transportarten hast, dann sieht das verdächtig nach dem Rucksackproblem aus – und für das existiert (vielleicht) keine effiziente Lösung, weil es NP-vollständig ist.

@narpfel es ist trotzdem interessant Loesungen generieren zu koennen. ZB auch fuer randomisierte Startpunkte oder branch/bound Algorithmen etc. Nur ist halt im konkreten kein Ansatz notwendig. Und bei zb TSP reicht eine Permutation der Knoten-IDs. Andere brauchen eine kanonische oder randomisierte Aufzaehlung von Baeumen... etc.

@pixewakb:
Es ist ja vorab klar, dass jeder 4er Transport eine Runde spart. Du musst also für Lieferungen >= 4 soviel wie möglich mit 4er Transporten abdecken und den Rest mit einzelnen Fahrten. Dafür eignet sich divmod() ganz gut.

pixewakb hat geschrieben:Ich scheitere im Moment bereits an der Frage der Kombinatorik, also wie ich alle möglichen Kombinationen effizient zusammenstelle

Ist das tatsächlich die Aufgabenstellung oder geht es bloß darum, für einen Auftrag die optimale Lieferstrategie zu entwickeln? NIcht dass du mehr machst als gefordert ist. Und ansonsten kann man das ja trotzdem mittels range() und dem o.g. divmod() erledigen...

Es handelt sich um eine Sammlung von Programmieraufgaben, die ich durchgehe, um nicht aus der Übung zu kommen. Bei einigen der Aufgaben vermute ich, dass das eigentlich Graphen-Probleme sind bzw. ausgefeiltere Algorithmen zum Einsatz kommen und es nicht nur um stupides Abprogrammieren der Aufgaben geht, auch deshalb stand ich da etwas auf dem Schlauch.

Mit dem jetzigen Input versuche ich mal wieder mein Glück.

PS: Gibt es eigentlich eine brauchbare Einführung, die so etwas wie Graphentheorie, Entscheidungsbäume usw. leicht verständlich erklärt. Ich kenne das dem Namen nach, wüsste aber auch nicht, wo so etwas sinnvoll zum Einsatz kommt. Bei meiner Arbeit spielte das bislang nie eine Rolle.

Ja, keine Ahnung. Entweder die haben da bewusst ein absolutes Anfängerproblem genommen, wo eigentlich nur logisches Denken zum Verstehen der Aufgabe benötigt wird. Oder es steckt doch mehr dahinter. Vielleicht könntest du mal den Originaltext zur Aufgabenstellung posten...

Ich komme damit erst einmal weiter. (Das Problemsetting ist komplexer, weil gleichzeitig zwei "Spieler" gegeneinander antretend simuliert werden müssen. Ich habe es auf das Problem reduziert, das mich beschäftigt hat. Mit eurem Input komme ich aber erst einmal weiter, denke ich. Vielen Dank!)