Søger en knapsack-bin packing algoritme implementeret PHP

endte med at kode det selv

Du må da gerne dele det med os, hvis du ikke har problemer med ophavsret :)

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);
?>