hallo,
problem:
ich habe 99 verschiedene cd-titel (elemente) mit einer bestimmten spiellänge (merkmal mit positiver, natürlicher ausprägung) in sekunden
ich will jetzt wissen, welche elemente jeweils einmal in eine play-liste aufgenommen werden müssen, um eine bestimmte summe der einzeln spiellängen, sagen wir 45min=2700sek, nicht zu überschreiten (zwischen den titeln pausen vernachlässigen)
lösung:
bitte ALLGEMEIN verbal oder webpage
danke, bs
hallo bs,
wo steckt hier das Optimierungsziel? Willst Du möglichst viele Titel unterbringen? Dann sortiere absteigend nach der Länge und summiere solange, bis Dein Limit erreicht ist.
Gruß Ralf
problem:
ich habe 99 verschiedene cd-titel (elemente) mit einer
bestimmten spiellänge (merkmal mit positiver, natürlicher
ausprägung) in sekunden
ich will jetzt wissen, welche elemente jeweils einmal in eine
play-liste aufgenommen werden müssen, um eine bestimmte summe
der einzeln spiellängen, sagen wir 45min=2700sek, nicht zu
überschreiten (zwischen den titeln pausen vernachlässigen)lösung:
bitte ALLGEMEIN verbal oder webpagedanke, bs
hallo ralf,
ziel ist es, möglichst nah an die vorgegebene zeit zu kommen
ein langer+ein kurzer titel kann das durchaus besser erfüllen als 5 kurze titel
die frage ist halt nur welche
ich glaube, dass grundsätzlich alle möglichkeiten geprüft werden müssen, aber einige schon grundsätzlich wegfallen
(beispielsweise: titel4+titel7>vorgabe, also ist titel1+titel2+titel4+tite7+titel12+… auch sinnlos)
es gibt bestimmt fertige schnelle algorithmen dafür
bs
Hallo,
tut mir ja leid, Dich enttäuschen zu müssen, aber dafür gibt es KEINEN schnellen Algorithmus und es kann auch mathematisch beweisbar keinen geben.
Wenn Du es etwas theoretischer haben willst: Dein Problem liegt nicht in der Klasse P (der in Polynomialzeit lösbaren Probleme), sondern in NP-schwer (mit Zusammenhang zu NPV), und das sind die am schwersten lösbaren Probleme überhaupt.
Dein Algorithmus, einfach alle (sinnvollen) Kombinationen durchzuprobieren, wird für große n (also viele, viele Titel) einfach zu lange brauchen. Da hilft Dir auch keine schnellerer Computer was.
Den einzigen Rat, den ich Dir geben kann, ist, Dich mit Näherungslösungen zufrieden zu geben.
Viel Erfolg,
Golo Haas
PS: Wenn Du mehr darüber wissen willst, fang an Informatik zu studieren 
.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Simpler Ansatz
Hi bs,
wie wär’s mit ohne Operations research:
Füge immer den größten noch nicht abgelegten Titel ein, vermindere den verfügbaren Rest und wiederhole, bis keiner der Titel mehr in den Rest passt. Damit sollte der Platz optimal ausgefüllt sein.
Gruß Ralf
problem:
ich habe 99 verschiedene cd-titel (elemente) mit einer
bestimmten spiellänge (merkmal mit positiver, natürlicher
ausprägung) in sekunden
ich will jetzt wissen, welche elemente jeweils einmal in eine
play-liste aufgenommen werden müssen, um eine bestimmte summe
der einzeln spiellängen, sagen wir 45min=2700sek, nicht zu
überschreiten (zwischen den titeln pausen vernachlässigen)
Quatsch!
Hallo,
sorry, Dir widersprechen zu müssen, aber ganz so easy geht es nicht. Als Beispiel nimm Dir mal folgende Tracks, die auf eine handelsübliche 74 min-CDR draufsollen …
Track 1: 60 min
Track 2: 38 min
Track 3: 36 min
Track 4: 13 min
Nach Deiner Methode bleiben am Anfang 74 Minuten, also schreibt man den größten Track, der reinpasst, also Track 1. Bleiben noch 14 Minuten. Da als einziger noch Track 4 reinpasst, hat man eine Gesamtspielzeit von 73 Minuten.
Wenn Du aber Track 1 weglässt und statt dessen Track 2 und 3 nimmst, kommst Du genau auf 74 Minuten, was 1 Minute mehr ist, also ein besseres Ergebnis darstellt.
Wenn’s so einfach wäre, das wär schön!
Viele Grüße,
Golo
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo!
Wenn Du es etwas theoretischer haben willst: Dein Problem
liegt nicht in der Klasse P (der in Polynomialzeit lösbaren
Probleme), sondern in NP-schwer (mit Zusammenhang zu NPV), und
das sind die am schwersten lösbaren Probleme überhaupt.Wenn Du mehr darüber wissen willst, fang an Informatik zu
studieren
Ei guck - ist ja zugegebenermaßen schon fast ein Jahr her, dass ich mein Studium beendet habe, aber dass innerhalb dieses Zeitraums „P!=NP“ bewiesen wurde, ist mir neu…
Gruß,
Stefan :-?
Hi,
okay, es ist nicht bewiesen, dass es nicht in P liegt, aber zumindest ist das die gängige Vermutung …
Viele Grüße,
Golo Haas