Skip to content

Instantly share code, notes, and snippets.

@kingkarki
Created December 23, 2013 04:45
Show Gist options
  • Save kingkarki/8091739 to your computer and use it in GitHub Desktop.
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.
<?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