Created
December 23, 2013 04:45
-
-
Save kingkarki/8091739 to your computer and use it in GitHub Desktop.
Suppose i have to divide all 7 bags in 4 container equally by balancing there weight. But i cannot break the bag to manage weight. Here is the function which will do it.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
$bags = array(60,80,20,10,80,100,90,20,89,830,88); | |
$containers = array(1=>10000,2=>10000,3=>10000,4=>10000); // number -> free space | |
$placement = array(); | |
function bestContainerFor($weight) { | |
global $containers; | |
$rest = 0; | |
$out = 0; // in it won't change $weight fits nowhere | |
foreach($containers as $nr=>$space) { | |
if($space<$weight) continue; // not enough space | |
if($space-$weight<$rest) continue; // we have a better case | |
$rest = $space-$weight; | |
$out = $nr; | |
} | |
if($out) $containers[$out]-=$weight; // occupy the space | |
return $out; | |
} | |
foreach($bags as $nr=>$w) { | |
$p = bestContainerFor($w); | |
$placement[$nr] = $p; // for later use; in this example it's not needed | |
if( $p) print "Bag $nr fits in $p<br>"; | |
if(!$p) print "Bag $nr fits nowhere<br>"; | |
$data[$p][]=$bags[$nr]; | |
} | |
echo '<pre>'; | |
print_r($data); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment