Avatar billede cyberesben Nybegynder
28. januar 2008 - 01:31 Der er 2 kommentarer og
1 løsning

Søger en knapsack-bin packing algoritme implementeret PHP

Jeg sidder og arbejder på et script hvor jeg har brug for flg.

En række elementer med forskellig størrelse skal grupperes, således at hver gruppes størrelse er under en given grænse. elementerne skal arrangeres, så pladsen udnyttes bedst muligt.

Jeg har læst mig til at det er et knapsack problem af typen 1-dimensionel bin packing som jeg sidder med, og leder derfor efter en PHP-implemententation af denne algoritme. Jeg har indtil videre kun kunnet finde kode i Visual Basic format, hvilket ikke er helt let at "oversætte" til PHP...

Så hvis nogen kan linke til et kode-eksempel på en bin packer skrevet i PHP så vil det være rart:)
Avatar billede cyberesben Nybegynder
28. januar 2008 - 06:46 #1
endte med at kode det selv
Avatar billede bobslaede Nybegynder
28. januar 2008 - 15:12 #2
Du må da gerne dele det med os, hvis du ikke har problemer med ophavsret :)
Avatar billede cyberesben Nybegynder
28. januar 2008 - 16:47 #3
her er lidt kode jeg brugte da jeg testede det

<?
function cmp($a,$b) {
    if($a["size"] > $b["size"]) return -1;
    else if($a["size"] < $b["size"]) return 1;
    else return 0;
}

$elements = array(
    array("id"=>0,"size"=>45,"bin"=>-1),
    array("id"=>1,"size"=>91,"bin"=>-1),
    array("id"=>2,"size"=>18,"bin"=>-1),
    array("id"=>3,"size"=>17,"bin"=>-1),
    array("id"=>4,"size"=>29,"bin"=>-1),
    array("id"=>5,"size"=>39,"bin"=>-1),
    array("id"=>6,"size"=>18,"bin"=>-1),
    array("id"=>7,"size"=>18,"bin"=>-1),
    array("id"=>8,"size"=>10,"bin"=>-1),
    array("id"=>9,"size"=>14,"bin"=>-1),
    array("id"=>10,"size"=>93,"bin"=>-1),
    array("id"=>11,"size"=>18,"bin"=>-1),
    array("id"=>12,"size"=>80,"bin"=>-1),
    array("id"=>13,"size"=>87,"bin"=>-1),
    array("id"=>14,"size"=>54,"bin"=>-1),
    array("id"=>15,"size"=>55,"bin"=>-1),
    array("id"=>16,"size"=>5,"bin"=>-1),
    array("id"=>17,"size"=>24,"bin"=>-1)
);
usort($elements, "cmp");

$element_count=count($elements);

foreach($elements as $e) {
    $sum+=$e["size"];
}
echo "sum:$sum\n";

$bins=array(
    array("id"=>1,"size"=>0,"elements"=>array())
);


//print_r($elements);
$binsize=150;
$bin_pointer=0;
$element_pointer=0;
$used_elements=0;
$bin=&$bins[$bin_pointer];
$element=&$elements[$element_pointer];
$bin_elements=&$bin["elements"];
$free_space=$binsize;

while($used_elements<$element_count) {
   
    if($element["size"]>$binsize) die("Element too big\n");

    //insufficient space in current bin
    if($element["size"]>$free_space) {
        echo "not enough space element_pointer: $element_pointer\n";
        //find biggest element that fits
        $found_elements=0;
        for($i=0;$i<$element_count;$i++) {
            $temp_element=&$elements[$i];
            //element found
            if($temp_element["bin"]<0 && !($temp_element["size"]>$free_space) ) {
                echo "fitting element found i: $i\n";
                $found_elements++;

                //put element into bin
                $used_elements++;
                $temp_element["bin"]=$bin_pointer;
                $bin["size"]+=$temp_element["size"];
                $free_space=$binsize-$bin["size"];
                array_push($bin_elements,$temp_element);
            }

        }
        //else make a new bin and put element into
        if($found_elements==0) {
            echo "making new bin element_pointer: $element_pointer\n";
            //make new bin
            $bin_pointer++;
            $new_bin=array("id"=>$bin_pointer,"size"=>0,"elements"=>array());
            array_push($bins,$new_bin);
            $bin=&$bins[$bin_pointer];
            $bin_elements=&$bin["elements"];
           
            //put element into bin
            $used_elements++;
            $element["bin"]=$bin_pointer;
            $bin["size"]+=$element["size"];
            $free_space=$binsize-$bin["size"];
            array_push($bin_elements,$element);
        }
    }
    //enough space
    else {
        //put element into bin
        echo "enough space element_pointer: $element_pointer\n";
        $used_elements++;
        $element["bin"]=$bin_pointer;
        $bin["size"]+=$element["size"];
        $free_space=$binsize-$bin["size"];
        array_push($bin_elements,$element);
    }

    if($element["bin"]>-1) {
        do {
            $element_pointer++;
            $element=&$elements[$element_pointer];
        }
        while($element_pointer<$element_count && $element["bin"]>-1);
    }
}
print_r($elements);
print_r($bins);
?>
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Vi tilbyder markedets bedste kurser inden for webudvikling

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester