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