nicht angemeldet
Suche Algorithmus ähnlich dem Rucksackproblem
Hallo Leute,
ich suche für eine Aufgabe einen effizienten Algorithmus, der folgendes lösen soll:
- Es gibt einen Parkplatz mit 30 Stellplätzen
- Es gibt 100 Fahrzeuge, die in 8 Kategorien eingeteilt sind (z.B. PKW, Roller, LKW, Busse etc.)
Ermittelt werden soll die maximale Parkplatzauslastung unter der Bedingung, daß von jeder Kategorie maximal 5 Exemplare auf dem Parkplatz stehen.
Das ganze möchte ich in php umsetzen.
Gegeben ist am Anfang ein array, in dem die 100 Fahrzeuge jeweils mit Kennzeichen und Kategorienummer stehen.
Kann mir jemand einen Algorithmus nennen, der das Gewünschte leistet?
Es grüßt
Mike
-
Ermittelt werden soll die maximale Parkplatzauslastung
Wie definiert sich die? Gibts sonstige Angaben?
Bisher würd ich halt sagen, die maximale Auslastung ist nur eine einzige Zahl, nämlich 30 Fahrzeug. Denn die lassen sich mit max. 5 pro Kategorie erreichen.
-
Ermittelt werden soll die maximale Parkplatzauslastung
Wie definiert sich die? Gibts sonstige Angaben?Bisher würd ich halt sagen, die maximale Auslastung ist nur eine einzige Zahl, nämlich 30 Fahrzeug. Denn die lassen sich mit max. 5 pro Kategorie erreichen.
Ja, das hatte ich gestern abend auch schon ;)
Es fehlt wohl auch eine weitere Bedingung, was die Auswahl der Fahrzeuge betrifft, die auf den Parkplatz dürfen (oder nicht dürfen). Ansosnten gäbe es mehrere Lösungen.
Im Zweifelsfall (Default) entscheidet der Parkplatzwächter (Anm. 1) ;)
Schönen Sonntag,
Horst Heimtz-WürfelspilzAnm. 1) Der ist mit Sicherheit bestochen und korrupt!
-
-
Hallo,
Kann mir jemand einen Algorithmus nennen, der das Gewünschte leistet?
Nach deiner Beschreibung wäre das genau das Rucksackproblem. Dein Parkplatz ist der Rucksack/Behälter und deine Fahrzeuge sind die Gegenstände, die im Rucksack mitgenommen werden sollen.
Grüße
-
Nach deiner Beschreibung wäre das genau das Rucksackproblem.
Find ich nicht. Dazu fehlt noch eine Bedingung, nämlich wie Hotti ja auch schon sagte, etwas das die Belegung genauer beschreibt.
Wenn es egal ist wer da drauf steht, kriegt man den Parkplatz unter gegebenen Bedingungen komplett voll, also alle Plätze belegt. Alles weitere müsste noch festgelegt werden.Auch sonst ist ein Parkplatz nicht unbedingt ein Rucksackproblem. Pro Platz kommt genau ein Fahrzeug unterstelle ich mal. Sonst fehlt wie gesagt noch eine Definition wie es sonst sein soll.
Dann fragt sich was die maximale Auslastung ist. Möglichst große Fahrzeuge? Dann nimmt man eben zuerst die 5 größten, danach die kleineren usw...
Hier fehlt also schon noch einiges an Definition.-
Hallo,
Nach deiner Beschreibung wäre das genau das Rucksackproblem.
Find ich nicht. Dazu fehlt noch eine Bedingung, nämlich wie Hotti ja auch schon sagte, etwas das die Belegung genauer beschreibt.Ja, natürlich. Aber das schiebe ich mal auf die "Faulheit" des Fragenden. Aber vom Prinzip her ist es dieses Problem.
Grüße
-
-