[DieKillerhuhn]

Guten Tag,

ich muss ein C++ Programm schreiben. Ich habe auch schon eine Idee, wie ich da vorgehen kann, allerdings fehlt mir der Ansatz.

Welche Datenstruktur würdet ihr vorschlagen für Folgendes:

Es gibt eine "Maxikiste" in der 12 verschiedene Kisten drin sind , von 0 bis 12.
Ich muss auf jede Kiste zugreifen , bzw diese mit Schätzen füllen können.

Im Anhang ist ein Bild dazu!

Mfg

Angehängte Miniaturbilder

• 

[RalphS]

Versteh ich das richtig:

Es gibt 12 Kisten.
Die erste Kiste faßt nichts.
Jede weitere Kiste faßt (vorherige Kiste + 1) Einheiten.
Ergo, effektiv nutzbare 11 Kisten.

Und das Programm soll die füllen: jeweils eine Einheit pro Platzeinheit in der Kiste.
Richtig?

Falls ja, würd ich das zuallererstmal in zwei Segmente aufteilen - nur bis 6 iterieren und dann 1 und 7, 2 und 8 etc gemeinsam abhandeln. Hab da jetzt nicht genau draufgeschaut und schon gar nicht mathematisch, aber so auf den ersten Blick sollten sich dann jeweils die "Gesamtschätze" über alle 6 Iterationen gleichen, nur daß sich die Aufteilung auf Kiste k und (12-k) jedesmal ändert.

Dann hätte man das in O(n/2) weg. Aber man müßte halt natürlich gucken, wie die Beziehung zwischen Einheit k und (12-k) ganz genau aussieht.

Datenstruktur denk ich grad an Binärbaum. Aber 100%ig sicher bin ich mir da nicht. Ist eher so ein Bauchgefühl.

Dieser Beitrag wurde von RalphS bearbeitet: 04. Januar 2014 - 17:30

[DieKillerhuhn]

also das mit dem Füllen ist ein bisschen anders, es gibt verschieden große Schätze mit verschiedenen Werten, z.B. eine Golddublone nimmt 2 Plätze ein und hat einen Wert von 6 usw und ich muss den Algorithmus programmieren das in jeder Kiste der maximal erreichbare Wert ist. Den Algorithmus dazu habe ich schon entwickelt, mir fehlt nur eine geeignete Datenstruktur, in der ich die "Maxikiste" samt ihres Inhaltes im Rechner speichern kann. das möchte ich so lösen, dass ich eine Funktion schreiben kann, welche die "Maxikiste" als Parameter übergeben bekommt und jede Kiste in der Maxikiste soweit möglich erstmal mit ersten Schatz füllt.

das hier ist der Rohbau des Programms


und hier die ersten aufgabenteile

[RalphS]

Algorithmus ohne Datenstruktur? Das bedingt sich doch eigentlich.

Wie sieht der Algorithmus denn grob aus?

[DieKillerhuhn]

Ok, also der Algorithmus sieht wie folgt aus:

Es gibt Folgende Schätze:

Dann füllt man erstmal jede Kiste mit dem kleinsten Schatz so gut wie möglich :


Dann nimmt man den nächstgrößeren Schatz ( Geldbündel) . Größe 3, also kann es in die 3. Kiste, es folgt ein Wertvergleich:

[Sturmovik]

Mal ne ganz doofe Frage... wärs nich sinnvoller erstmal die großen Schätze zu verpacken, ehe die Kisten mit Kleinkram zugemüllt werden?

[RalphS]

Denke mal, da macht sich ein Hash ganz gut, mit 12 Buckets für 12 verschiedene Maximallängen. Außerdem noch eine zusätzliche Variable für den verbleibenden freien Platz im Bucket. Nennen wir sie "free".

Eine Kiste wäre eine Struktur (Größe, Wert).

Dann müßtest Du nur noch, nach Wert(Kiste) aufsteigend sortiert, den Hash befüllen. Dabei ist es dann egal, was im Durchlauf vorher passiert ist - entweder die neue Kiste paßt rein oder sie tut es eben nicht. Hierfür macht sich erwartungsgemäß eine eigene Funktion tausche(Kiste k1, Kiste k2) gut.

... Oder auch nicht: sind die Schätze denn endlich? Wenn nicht, brauchst Du natürlich keine Funktion zum Tauschen. Neue Kiste rein, alte Kiste raus hätte ja dann keine weiteren Effekte, vom Füllstand des Hashes mal abgesehen.

Zum Einfügen müßtest Du dann für jede Kiste schauen, ob die Kistengröße des letzten Durchlaufs plus free kleiner oder gleich der neuen Kistengröße ist (andersherum: ob die neue Kiste in den Bucket paßt, wenn man die alte rausnimmt und den vorhandenen Platz berücksichtigt). Wenn das dann platzmäßig paßt, sollte die Kiste eingefügt werden können (da nach Wert vorsortiert und die neue Kiste daher immer wertvoller ist als die alte). Abschließend wäre 'free' zu aktualisieren (free = free -Größe[altekiste] + Größe[neukiste]).

Die Sache hat aber einen Haken: wenn durch das Einfügen der neuen, wertvolleren Kiste wieder Platz im Bucket frei wird, wo ggf. eine kleinere Kiste eigentlich wieder passen würde, wird das Ergebnis suboptimal. Möglicherweise (aber keine Ahnung, wieviel davon vorgegeben ist) lohnt es sich, nicht beim "wertlosesten", sondern beim "wertvollsten" Element anzufangen; damit umgeht man das Risiko, weil nur dann eingefügt wird, wenn auch Platz ist (unabhängig vom Wert -> man muß nichts rausnehmen, alles was drin ist, hat auch Daseinsberechtigung).

Dieser Beitrag wurde von RalphS bearbeitet: 05. Januar 2014 - 02:26