Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » schnelles Boxenstapeln
Autor
Universität/Hochschule schnelles Boxenstapeln
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Themenstart: 2021-04-18

Hallo, Gegeben ist folgendes Problem: man bekommt eine endliche Folge von Boxen, die durch eine Ganzzahl beschrieben werden. Man kann eine Box in eine größere stellen, falls die größere mindestens doppelt so groß ist wie die kleinere. Man soll für eine Folge von Boxen einen Algorithmus angeben, der ausgibt wie viele Boxen mindestens nach außen hin sichtbar sind. Eine Box ist sichtbar genau dann, wenn sie nicht in einer größeren Box steckt. Habt ihr Ideen wie man das effizient lösen kann? Ich habe es nur asymptotisch in quadratischer Zeit geschafft. Viele Grüße!


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6908
Wohnort: Niedersachsen
  Beitrag No.1, eingetragen 2021-04-18

Mit einer effizienten Programmierung geht das schneller. Üblege Dir mal, wie groß der Aufwand ist, wenn Du als erstes alle Boxen der Größe nach sortierst und dann erst stapelst.


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.2, vom Themenstarter, eingetragen 2021-04-18

Danke für deine Antwort! In meiner implementierung habe ich erst die boxen von klein nach groß sortiert, ich weiß, dass das in \(n \cdot log(n)\) geht. Danach habe ich für jede Box geprüft, ob sie in einer größere gestapelt werden kann. Das habe ich aber nur in asympotisch \(n^2\) hingekriegt. Hast du einen Tipp wie man das eleganter gestalten kann?


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.3, vom Themenstarter, eingetragen 2021-04-18

Hat sich erledigt, danke!


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6908
Wohnort: Niedersachsen
  Beitrag No.4, eingetragen 2021-04-18

Der Vollständigkeit halber: Es reicht nicht, zu prüfen, ob es eine größere Box gibt, da man in jede größere Box nur _eine_ kleinere Box stellen kann. Es reicht aber, die Boxen nach absteigender Größe durchzugehen und zu prüfen, ob es eine größere _freie_ Box gibt und dann die kleinere Box in die größere zu stellen. Mit der richtigen Datenstruktur ist die Suche nach dieser größeren freien Box jeweils mit Aufwand $\log{n}$ möglich.


   Profil
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly hatte hier bereits selbst das Ok-Häkchen gesetzt.
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]