Algorithmus - Platz optimal nutzen

  • hi leute!

    bin grade auf der suche nach einem algorithmus mit dessen hilfe ich den platz auf einem datenträger optimal ausnutzen kann, sprich es geht darum dateien bestmöglich aufzuteilen sodass möglichst wenig platz verschwendet wird. zuerst dachte ich ja an das rucksack problem ... aber dort wird ja der wert optimiert. bei mir soll aber der verschwendete platz gegen 0 gehen. hat vlt irgendjemand eine idee?? :engel::engel:

  • Wenn du den Wert gleich der Größe der Datei setzt, ist die Lösung deines Problems äquivalent zur Lösung des Rucksackproblems (weil Wert->max => freier Platz->min).

    Why bother spending time reading up on things? Everybody's an authority, in a free land.

  • danke für deine schnelle antwort! hab mich nochmal ein wenig schlau gemacht. dürfte sich eher um ein eindimensionales bin-packing handeln .... naja np-vollständig .... macht die sache nicht grade einfacher ... gibt ein paar ganz gute ansätze aber die garantieren nur eine näherung an die optimale lösung ... mal weitersuchen .. danke nochmal! :D

  • Solange du net mit millionen kleiner Files zu tun hast kannst du auch NP-complete-Probleme in einer annehmbaren Zeit lösen.

    [font=verdana,sans-serif]"An über-programmer is likely to be someone who stares quietly into space and then says 'Hmm. I think I've seen something like this before.'" -- John D. Cock[/font]

    opentu.net - freier, unzensierter Informationsaustausch via IRC-Channel!
    Hilfe und Support in Studienangelegenheiten, gemütliches Beisammensein, von und mit Leuten aus dem Informatik-Forum!

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!