Das deutsche Python-Forum

Hallo,
es sollen Plätze Liegewiese vermietet werden (z.B. pro Tag) in einem Zeitfenster von z.B. 10-17 Uhr --z.B. stundenweise . Es gibt 100 m Platz der gleichzeitig streifenweise am laufenden Meter gebucht werden kann und man kann Zentimeter genau Platz reservieren. Wenn ich zu bestimmten Zeiten zu viele Buchunge habe, möchte ich Buchungen so streichen, das insgesamt möglichst viel Platz vermietet ist, also die Einnahmen maximal sind (Meter =Euro).

Ich habe einen Datenset aus z.B
6 (Anzahl Buchungen)
6 17 30 (AnfangszeitBuchung/ Endzeit Buchung/Meter gebucht)
14 17 50
15 17 20
16 17 10

Also habe ich von 16-17 Uhr 110 m vermietet (Zeile 2,3,4,5), wa szuveiel ist - wenn ich Zeile 5 streiche, mach eich den kleinsten Verlust und leige nicht über 100m Vermietung

Das Skript soll die Buchungen einlesen und bei Buchungenszeiträumen - also z.B Stunden- wo mehr als 100m gebucht sind , diejenige Buchungen streichen, die am Kleinsten ist, also am wenigsten Meter gebucht hat, so dass die Vermietungseinnahmen optimal sind.

Ich habe schon mehrere Ansätze- mit denen ich nicht nerven will, die mir aber unnötig kompliziert erscheinen.Der FAll ist simpel also kein multiple constrained Problem - keine wikrlich compinatorial optimization, - ich sehe den Wald vor lauter Bäumen nicht. Ich denke es muss doch ganz elementar und elegant zu lösen sein. oder kapier ich was nicht? Kennt jemand einen Skript, auf das ich aufbauen kann. Damit der Knoten platzt?

Danke im voraus. Gruss

@ALSO: Ist der Fall wirklich so simpel das man einfach bei Überlappungen die Buchung streichen darf die am wenigsten Meter belegt? Warum sollte das gehen? Warum kann die kleinste Buchung nicht später zu mehr Gewinn führen als man während der Zeit der Überlappung durch streichen einer grösseren Buchung verliert?

Es ist ein Strandliegeplatz. Bei Überbuchung streiche ich die Buchung, die gesamt am wenigsten Geld einbringt (also gebuchte cm und Zeitdauer) Es ist ein simples Constraint satisfaction problems (CSPs- are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations)

@ALSO: Also nicht nur die Meter sondern auch die Zeit. Trotzdem: Warum bist Du Dir sicher, dass das nicht zu einer Situation führen kann wo man weniger Platz belegen kann als wenn man eine grössere Buchung gestrichen hätte? Die grössere Buchung kann ja beispielsweise zu grösseren Überlappungen führen wo dann weitere Buchungen gestrichen werden müssen, die mit der kleinsten Buchung gepasst hätten.

Für mich sieht das ja sehr nach einer Variante des Rucksackproblems aus, und das ist nicht so einfach lösbar, das ist NP-vollständig.

Danke. Ja klar. Knapsack. Aber ich habe einen simplen, aufwandsarmen Näherungsansatz gefunden- den vergleiche ich mit dem normalen Ansatz - hat jemand so einen normale Ansatz als code irgendwo?