evtl. off-topic: PHP & Mathe

27.06.2005, 15:18

Hallo liebe Leute.

Mein Problem:
Ich habe eine Serie von 30 Bildern mit Breiten von 80 bis 160 Pixel.
Ich möchte nun per Mathematik eine Routine die Bildbreiten so berechnen lassen, daß die Bilder in ungefähr gleichen Breiten (also mehrere Bilder nebeneinander) mit einer Gesamtbreite von 500 Pixeln angezeigt werden.

Optische Darstellung meines Problems:

[XX] [XX] [XX]
[XXXX] [XXX]
[X] [XXX] [XX]
...und so weiter

Leider habe ich keine Idee, wie man so einen Algorithmus programmiert.
Mit arithmetischem Mittel werde ich da wohl nicht vorankommen, oder?

Wäre schön, wenn mich einer von euch in die richtige Richtung stubsen könnte, damit ich dieses Problem vom Tisch bekomme.

Achja - Die Bilder werden von Zeit zu Zeit ausgetauscht, daher ist eine statische Lösung nicht erwünscht.

Herzlichst, Marc

27.06.2005, 15:32

Wäre es nicht besser, die Bilder anhand ihrer Breite erst zu sortieren, und dann auszugeben ?

27.06.2005, 18:17

Mathematisch gesehen vielleicht, aber optisch sieht das dann blöd aus.

Stell Dir folgendes vor: Bilder 1+2 mit 160px und Bilder 3+4 mit 90px Breite.
Optisch wäre es dann am angenehmsten, wenn in Reihe eins Bild 1 und Bild 3 stünden und in Reihe zwei dann die Bilder 4 und 2, also:

[xxx] [x]
[x] [xxx]

Wobei es noch erträglich aussieht, wenn es so

[x] [xxx]
[x] [xxx]

aussähe. Bei Deiner Vorgehensweise käme dann dies hier heraus:

[x] [x] [xxx]
[xxx]

oder so ähnlich - was ich suche ist quasi eine Möglichkeit, Bilder im "Blocksatz" zu platzieren.

Wäre vielleicht auch mal eine interessante Aufgabe für die Programmierecke

Ich komme auf jeden Fall nicht weiter - beziehungsweise, ich finde keinen Ansatz, der irgendwie vernünftig erscheint.

Darum suche ich ja jemanden, der mich in die richtige Richtung dreht. Programmieren kann ich das dann schon alleine

27.06.2005, 18:30

Ohje wird etwas schwierig Optik und die max. Breite einzuhalten.

Muss zugeben, dass ich im Moment noch keine Idee habe, nur Gedanken:

[xxx] [x]
[x] [xxx]

Vieleicht könnte man die Bilder in 2 Bereiche vorsortieren.
Bereich_1 sind alle mit kleinere Breite, Bilder_2 sind praktisch der Rest - also größere Breite.

Beim Ausgeben der Bilder immer ein Bild von Bilder_1 und Bilder_2 bzw. das im wechsel.
Dabei zeitgleich überprüfen, wie breit das alles ist (inkl. Abstände).
erreicht die Überprüfung ein Wert über 500, dann die Ausgabe stoppen bzw. in der nächsten Zeile weitermachen.

Keine Ahnung, ob jemand mein Müll folgen konnte

Aber was anderes fällt mit jetzt nicht ein.

axo · 28.06.2005, 00:04

das ist mal 'ne wirklich interessante frage

ich meine, dass das problem kaum 'sauber' zu lösen ist - es lässt sich auf andere problemstellungen zurückführen, an die ich mich als NP-vollständig erinnere - da gab es mal ein typisches problem, das ähnlich ist:

du hast für eine universität eine liste von räumen (raumid, kapazität), und eine liste von vorlesungen (vorlesungsID, teilnehmer) - und mit diesen daten soll man eine raumbelegung konstruieren, in der die räume optimal ausgenutzt werden, d.h. möglichst wenig freie plätze in einem raum übrigbleiben, aber dass trotzdem alle teilnehmer einen platz finden. das ganze sei anscheinend eine ziemlich üble sache, das zu programmieren.

wenn man das problem aber etwas 'vereinfacht' und die anforderungen nicht so hoch stellt, ist das ganze problemlos lösbar:

PHP-Code:

  <?php

/** 

 * a simple api for an image.

 * you could change the constructor to receive a path to an image

 * and retrieve the width dynamically.

 * @author axo

*/

class Image {

    var $w;

    /** 

     * constructor.

     * @param $w integer the width of the image.

     * this could be changed to take a path to an existing image...

     * @return void

     * @access public

    */

    function Image($w) {

        $this -> w = $w;

    }

    

    /** 

     * returns the width of the image.

     * @param void

     * @return integer

     * @access public

    */

    function getWidth() {

        return $this -> w;

    }

    /** 

     * @access public

    */

    function toString() {

        return '['.$this -> w . '' . str_repeat('x',$this -> w - strlen($this -> w) - 2) .']';

    }

}

 
 
/** 

 * a row contains several images.

 * it can always take at least one image.

*/

class Row {

    /** 

     * the actual width of the row.

     * this is needed in order to be able to say whether

     * add() can take the image or not.

    */

    var $_actualWidth;

    

    /** 

     * the maximum width of the row.

    */

    var $_maxWidth = 500;

    

    /** 

     * contains the images.

    */

    var $_images = array();

    

    /** 

     * constructor.

     * @param $maxWidth the maximum width of the row.

     * @access public

     * @return void

    */

    function Row($maxWidth = 500) {

        $this -> _maxWidth = $maxWidth;

    }

    

    /** 

     * adds an image if it does not exceed the maximum width.

     * the first image can always be taken - this is

     * in order to avoid infinite loops if a given image width

     * is greater than the maximum width of the row.

     * @param $Image Image

     * @return boolean

     * @access public

    */

    function add($Image) {

        if ($this -> _wouldExceed($Image -> getWidth())) {

            return false;

        }

        return $this -> _doAdd($Image);

    }

    

    /** 

     * checks whether the addition of a given width would exceed the maximum width.

     * @param $newWidth integer

     * @return void

     * @access private

    */

    function _wouldExceed($newWidth) {

        if ($this -> _actualWidth < 1) {

            return false;

        }

        return ($this -> _actualWidth + $newWidth > $this -> _maxWidth);

    }

    

    /** 

     * adds the image to the own stack and updates the actual width.

     * @param $Image Image

     * @return boolean (always true)

     * @access private

    */

    function _doAdd($Image) {

        $this -> _actualWidth += $Image -> getWidth();

        $this -> _images[] = &$Image;

        return true;

    }

    

    /** 

     * simple toString  implementation to show the result.

     * @param void

     * @return string

     * @access public

    */

    function toString() {

        $foo = "";

        for ($i=0,$m=count($this -> _images);$i<$m;$i++) {

            $foo .= $this -> _images[$i] -> toString();

        }

        $foo .= "\n".str_repeat('-',$this -> _maxWidth)."\n";

        return $foo;

    }

    

}

 
/** 

 * 

*/

class RowContainer {

 
    var $_rows = array();

    var $_maxWidth = 90;

    

    /** 

     * @param $max integer the maximum width of a row

     * @return void

     * @access public

    */

    function RowContainer($max = 500) {

        $this -> _maxWidth = $max;

    }

    

    /** 

     * builds the rows from a given array of images.

     * @param $images array

     * @return void

    */

    function build(&$images) {

        $i = 0;

        $this -> _rows[0] = & new Row($this -> _maxWidth);

        foreach ($images as $img) {

            $row = & $this -> _rows[$i];

            /* @var $row Row */

            while (false === $this -> _rows[$i] -> add($img)) {

                $i++;

                if (!array_key_exists($i,$this -> _rows)) {

                    $this -> _rows[$i] = & new Row($this -> _maxWidth);

                }

            }

        }

    }

    

    /**

     * @param void

     * @return string

     * @access public

    */

    function toString() {

        $foo = "<pre style='font-family:monospace'>\n"

            .'['.$this -> _maxWidth.str_repeat('x',$this -> _maxWidth - strlen($this -> _maxWidth) - 2) . ']' . "\n";

        $foo .= str_repeat('-',$this -> _maxWidth) . "\n";

        for ($i=0,$m=count($this -> _rows);$i<$m;$i++) {

            $r = & $this -> _rows[$i];

            $foo .= $r -> toString();

        }

        return $foo . "\n</pre>";

    }

}

?>

test:

PHP-Code:

  <?php

$input = array(

    new Image(60),

    new Image(60),

    new Image(60),

    new Image(70),

    new Image(40),

    new Image(40),

    new Image(50),

    new Image(120),

    new Image(10),

    new Image(20),

    new Image(40),

    new Image(60),

    new Image(5),

    new Image(20),

    new Image(6),

    new Image(60),

    new Image(120),

    new Image(30),

    new Image(40),

    new Image(60),

    new Image(40),

);

        

$rowC = & new RowContainer(150);

$rowC -> build($input);

echo $rowC -> toString();

?>

ausgabe:

Code:

[150xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][70xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][50xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[120xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][10xxxxxx][20xxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][5xx][20xxxxxxxxxxxxxxxx][6xxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[120xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][30xxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------

sorry für die objekte - ich kann auf die schnelle so leichter denken ...

wie man sehen kann, ist der algorithmus nicht gerade optimal - eigentlich sollte das dreißiger-bild aus der vorletzten zeile in die drittletzte zeile verschoben werden, damit's schöner aussieht - für so eine operation würde der rechenaufwand aber wieder sehr hoch werden und man kommt nicht mit einer einzigen iteration über die bilder zum ergebnis.

axo · 28.06.2005, 00:11

kleine änderung am code - große wirkung:

wenn man die build() - funktion abändert, und zwar

PHP-Code:

  <?php

    function build(&$images) {

        $this -> _rows[0] = & new Row($this -> _maxWidth);

        foreach ($images as $img) {

            $i=0; // <-- hier ist die änderung: $i ist jetzt im foreach - rumpf

            $row = & $this -> _rows[$i];

            /* @var $row Row */

            

            while (false === $this -> _rows[$i] -> add($img)) {

                $i++;

                if (!array_key_exists($i,$this -> _rows)) {

                    $this -> _rows[$i] = & new Row($this -> _maxWidth);

                }

            }

        }

    }

?>

so dass also bei jedem neuen bild auch die erste 'zeile' wieder in betracht gezogen wird,
kommt ein völlig anderes ergebnis zustande

... das wird zwar langsamer, führt aber dazu, dass die ersten zeilen 'optimaler' gepackt werden.

Code:

[150xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][10xxxxxx][20xxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][70xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][5xx][6xxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][50xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][20xxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[120xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][30xxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[120xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------
[40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
------------------------------------------------------------------------------------------------------------------------------------------------------

... ergibt aber ein völlig anderes 'satzbild'

Waq · 28.06.2005, 00:27

Selbst das Rucksackproblem ist np-Vollständig... das hier ist ja quasi das gleiche mit mehreren Rucksäcken.

Der Beitrag wurde verschoben, wegen...
... falschem Titel, das Problem ist algorithmisch und nicht mathematisch zu lösen
... Postings im falschen Forum. Bitte beim nächsten Mal darauf achten..

moved to PHP - Fortgeschrittene

28.06.2005, 04:35

Hab recht vielen Dank axo.
Das hilft mir sehr weiter.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
PHP kann kein Mathe! ;)	RcRaCk2k	PHP-Fortgeschrittene	36	24.03.2006 18:36
Mathe Aufgabe	matthros	Off-Topic Diskussionen	15	23.03.2006 11:28
Mathe: Schleife in Formel	faux	Off-Topic Diskussionen	2	28.05.2005 00:00
Wie kann ich die Mathe Funktipn geteilt durch führen?		PHP Tipps 2005	2	24.04.2005 20:17
Mathe Problem Streckenberechnung mit bewegung	nilsfeld	Off-Topic Diskussionen	24	10.03.2005 21:12
Mathe problem		PHP Tipps 2007	2	03.01.2005 21:41
Variables Array	Borlox	PHP Tipps 2004	4	29.09.2004 18:56

27.06.2005, 15:18
Gast Beiträge: n/a	evtl. off-topic: PHP & Mathe Hallo liebe Leute. Mein Problem: Ich habe eine Serie von 30 Bildern mit Breiten von 80 bis 160 Pixel. Ich möchte nun per Mathematik eine Routine die Bildbreiten so berechnen lassen, daß die Bilder in ungefähr gleichen Breiten (also mehrere Bilder nebeneinander) mit einer Gesamtbreite von 500 Pixeln angezeigt werden. Optische Darstellung meines Problems: [XX] [XX] [XX] [XXXX] [XXX] [X] [XXX] [XX] ...und so weiter Leider habe ich keine Idee, wie man so einen Algorithmus programmiert. Mit arithmetischem Mittel werde ich da wohl nicht vorankommen, oder? Wäre schön, wenn mich einer von euch in die richtige Richtung stubsen könnte, damit ich dieses Problem vom Tisch bekomme. Achja - Die Bilder werden von Zeit zu Zeit ausgetauscht, daher ist eine statische Lösung nicht erwünscht. Herzlichst, Marc


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

27.06.2005, 15:32
Gast Beiträge: n/a	Wäre es nicht besser, die Bilder anhand ihrer Breite erst zu sortieren, und dann auszugeben ?

27.06.2005, 18:17
Gast Beiträge: n/a	Mathematisch gesehen vielleicht, aber optisch sieht das dann blöd aus. Stell Dir folgendes vor: Bilder 1+2 mit 160px und Bilder 3+4 mit 90px Breite. Optisch wäre es dann am angenehmsten, wenn in Reihe eins Bild 1 und Bild 3 stünden und in Reihe zwei dann die Bilder 4 und 2, also: [xxx] [x] [x] [xxx] Wobei es noch erträglich aussieht, wenn es so [x] [xxx] [x] [xxx] aussähe. Bei Deiner Vorgehensweise käme dann dies hier heraus: [x] [x] [xxx] [xxx] oder so ähnlich - was ich suche ist quasi eine Möglichkeit, Bilder im "Blocksatz" zu platzieren. Wäre vielleicht auch mal eine interessante Aufgabe für die Programmierecke Ich komme auf jeden Fall nicht weiter - beziehungsweise, ich finde keinen Ansatz, der irgendwie vernünftig erscheint. Darum suche ich ja jemanden, der mich in die richtige Richtung dreht. Programmieren kann ich das dann schon alleine

27.06.2005, 18:30
Gast Beiträge: n/a	Ohje wird etwas schwierig Optik und die max. Breite einzuhalten. Muss zugeben, dass ich im Moment noch keine Idee habe, nur Gedanken: [xxx] [x] [x] [xxx] Vieleicht könnte man die Bilder in 2 Bereiche vorsortieren. Bereich_1 sind alle mit kleinere Breite, Bilder_2 sind praktisch der Rest - also größere Breite. Beim Ausgeben der Bilder immer ein Bild von Bilder_1 und Bilder_2 bzw. das im wechsel. Dabei zeitgleich überprüfen, wie breit das alles ist (inkl. Abstände). erreicht die Überprüfung ein Wert über 500, dann die Ausgabe stoppen bzw. in der nächsten Zeile weitermachen. Keine Ahnung, ob jemand mein Müll folgen konnte Aber was anderes fällt mit jetzt nicht ein.

28.06.2005, 00:04
axo Erfahrener Benutzer Registriert seit: 24.12.2004 Beiträge: 1.814	das ist mal 'ne wirklich interessante frage ich meine, dass das problem kaum 'sauber' zu lösen ist - es lässt sich auf andere problemstellungen zurückführen, an die ich mich als NP-vollständig erinnere - da gab es mal ein typisches problem, das ähnlich ist: du hast für eine universität eine liste von räumen (raumid, kapazität), und eine liste von vorlesungen (vorlesungsID, teilnehmer) - und mit diesen daten soll man eine raumbelegung konstruieren, in der die räume optimal ausgenutzt werden, d.h. möglichst wenig freie plätze in einem raum übrigbleiben, aber dass trotzdem alle teilnehmer einen platz finden. das ganze sei anscheinend eine ziemlich üble sache, das zu programmieren. wenn man das problem aber etwas 'vereinfacht' und die anforderungen nicht so hoch stellt, ist das ganze problemlos lösbar: PHP-Code: <?php /** * a simple api for an image. * you could change the constructor to receive a path to an image * and retrieve the width dynamically. * @author axo / class Image { var $w; /* * constructor. * @param $w integer the width of the image. * this could be changed to take a path to an existing image... * @return void * @access public / function Image($w) { $this -> w = $w; } /* * returns the width of the image. * @param void * @return integer * @access public / function getWidth() { return $this -> w; } /* * @access public / function toString() { return '['.$this -> w . '' . str_repeat('x',$this -> w - strlen($this -> w) - 2) .']'; } } /* * a row contains several images. * it can always take at least one image. / class Row { /* * the actual width of the row. * this is needed in order to be able to say whether * add() can take the image or not. / var $_actualWidth; /* * the maximum width of the row. / var $_maxWidth = 500; /* * contains the images. / var $_images = array(); /* * constructor. * @param $maxWidth the maximum width of the row. * @access public * @return void / function Row($maxWidth = 500) { $this -> _maxWidth = $maxWidth; } /* * adds an image if it does not exceed the maximum width. * the first image can always be taken - this is * in order to avoid infinite loops if a given image width * is greater than the maximum width of the row. * @param $Image Image * @return boolean * @access public / function add($Image) { if ($this -> _wouldExceed($Image -> getWidth())) { return false; } return $this -> _doAdd($Image); } /* * checks whether the addition of a given width would exceed the maximum width. * @param $newWidth integer * @return void * @access private / function _wouldExceed($newWidth) { if ($this -> _actualWidth < 1) { return false; } return ($this -> _actualWidth + $newWidth > $this -> _maxWidth); } /* * adds the image to the own stack and updates the actual width. * @param $Image Image * @return boolean (always true) * @access private / function _doAdd($Image) { $this -> _actualWidth += $Image -> getWidth(); $this -> _images[] = &$Image; return true; } /* * simple toString implementation to show the result. * @param void * @return string * @access public / function toString() { $foo = ""; for ($i=0,$m=count($this -> _images);$i<$m;$i++) { $foo .= $this -> _images[$i] -> toString(); } $foo .= "\n".str_repeat('-',$this -> _maxWidth)."\n"; return $foo; } } /* * / class RowContainer { var $_rows = array(); var $_maxWidth = 90; /* * @param $max integer the maximum width of a row * @return void * @access public / function RowContainer($max = 500) { $this -> _maxWidth = $max; } /* * builds the rows from a given array of images. * @param $images array * @return void / function build(&$images) { $i = 0; $this -> _rows[0] = & new Row($this -> _maxWidth); foreach ($images as $img) { $row = & $this -> _rows[$i]; / @var $row Row / while (false === $this -> _rows[$i] -> add($img)) { $i++; if (!array_key_exists($i,$this -> _rows)) { $this -> _rows[$i] = & new Row($this -> _maxWidth); } } } } /* * @param void * @return string * @access public */ function toString() { $foo = "<pre style='font-family:monospace'>\n" .'['.$this -> _maxWidth.str_repeat('x',$this -> _maxWidth - strlen($this -> _maxWidth) - 2) . ']' . "\n"; $foo .= str_repeat('-',$this -> _maxWidth) . "\n"; for ($i=0,$m=count($this -> _rows);$i<$m;$i++) { $r = & $this -> _rows[$i]; $foo .= $r -> toString(); } return $foo . "\n</pre>"; } } ?> test: PHP-Code: <?php $input = array( new Image(60), new Image(60), new Image(60), new Image(70), new Image(40), new Image(40), new Image(50), new Image(120), new Image(10), new Image(20), new Image(40), new Image(60), new Image(5), new Image(20), new Image(6), new Image(60), new Image(120), new Image(30), new Image(40), new Image(60), new Image(40), ); $rowC = & new RowContainer(150); $rowC -> build($input); echo $rowC -> toString(); ?> ausgabe: Code: [150xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][70xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][50xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [120xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][10xxxxxx][20xxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][5xx][20xxxxxxxxxxxxxxxx][6xxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [120xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][30xxxxxxxxxxxxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ [40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][60xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx][40xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] ------------------------------------------------------------------------------------------------------------------------------------------------------ sorry für die objekte - ich kann auf die schnelle so leichter denken ... wie man sehen kann, ist der algorithmus nicht gerade optimal - eigentlich sollte das dreißiger-bild aus der vorletzten zeile in die drittletzte zeile verschoben werden, damit's schöner aussieht - für so eine operation würde der rechenaufwand aber wieder sehr hoch werden und man kommt nicht mit einer einzigen iteration über die bilder zum ergebnis.

28.06.2005, 00:27
Waq Erfahrener Benutzer Registriert seit: 15.08.2004 Beiträge: 2.473	Selbst das Rucksackproblem ist np-Vollständig... das hier ist ja quasi das gleiche mit mehreren Rucksäcken. Der Beitrag wurde verschoben, wegen... ... falschem Titel, das Problem ist algorithmisch und nicht mathematisch zu lösen ... Postings im falschen Forum. Bitte beim nächsten Mal darauf achten.. moved to PHP - Fortgeschrittene __________________ mod = master of disaster

28.06.2005, 04:35
Gast Beiträge: n/a	Hab recht vielen Dank axo. Das hilft mir sehr weiter.