Page 1 of 1
Number crunching
Posted: Mon Oct 11, 2004 7:06 am
by Schizoid
Hey all.
New to the place, so please bear with me. I haven't been programming for some time, and just got started again. This question might be more of a general programming question than an actual PHP question, but I hope someone can point me in the right direction either way.
Here what I want to do:
Currently I have an array filled with values. I also have a max value, which is just a static number.
I want to combine as many values as necessary from the array, to get closest to the max value. All combinations should be attempted. When found, the values found should be recorded, and removed from the array. Then we start all over, and continue this way untill the array is empty.
What am I looking at here? For loop in for loop in for loop...? That won't even do it. Anybody got a point?
Thanks in advance.
Posted: Mon Oct 11, 2004 7:08 am
by patrikG
What's the code you have so far?
Posted: Mon Oct 11, 2004 7:11 am
by Schizoid
Here it is:
Code: Select all
<?php
$indir = "C:\Privat";
$outfile = "results.txt";
$dirarray = array();
$sizearray = array();
$wantedsize = 300;
function getdirs($directory)
{
if ($handle = opendir($directory))
$results = array();
{
while (false !== ($file = readdir($handle)))
{
if ($file != "." && $file != "..")
{
if (is_dir($file))
{
array_push($results, $file);
}
}
}
closedir($handle);
}
return $results;
}
function dirsize($directory)
{
if (!is_dir($directory)) return -1;
$size = 0;
if ($DIR = opendir($directory))
{
while (($dirfile = readdir($DIR)) !== false)
{
if (is_link($directory . '/' . $dirfile) || $dirfile == '.' || $dirfile == '..')
continue;
if (is_file($directory . '/' . $dirfile))
$size += filesize($directory . '/' . $dirfile);
else if (is_dir($directory . '/' . $dirfile))
{
$dirSize = dirsize($directory . '/' . $dirfile);
if ($dirSize >= 0) $size += $dirSize;
else return -1;
}
}
closedir($DIR);
}
return $size;
}
function format_size($rawSize)
{
if ($rawSize / 1048576 > 1)
return round($rawSize/1048576, 1);
// else if ($rawSize / 1024 > 1)
// return round($rawSize/1024, 1) . 'KB';
// else
// return round($rawSize, 1) . 'bytes';
}
$dirarray = getdirs($indir);
foreach ($dirarray as $value)
{
$targetdir = "$indir\\$value";
$targetsize = dirsize($targetdir);
$inmb = format_size($targetsize);
array_push($sizearray, $inmb);
}
?>
That big empty spot at the bottom? That's where the sorting mechanism is supposed to go. As you can see, my code only collects directory names and their size so far. Now I want to combine as I first posted, but haven't got the slightest clue... Thanks for your interest, hope you can help.

Posted: Mon Oct 11, 2004 7:44 am
by patrikG
There are various ways of solving this. One would be to sort the array-elements by their value, and add them until they hit the specified limit at which point the function returns an array containing the sum of added values and the remaining elements of the original array.
Some code that I haven't had the time to test, yet.
Code: Select all
<?php
function array_sum_approximate($array,$limit){
//check if sum of array values <= $limit
if($array_sum=array_sum($array)<=$limit){
return $array_sum;
}
//if not sort array, loop through it until it hits $limit
$array = sort($array);
while($array_sum<=$limit){
list($sum) = array_pop($array);
$array_sum += $sum;
}
$return["array_sum"] = $array_sum;
$return["array_remainder"] = $array;
return $return;
}
?>
Posted: Mon Oct 11, 2004 7:47 am
by Schizoid
I hear you, and thought of something like that to start with as well. Problem is, it doesn't ensure that we get as close to the limit as possible with the given numbers. I want all options to be tried, before the correct one is chosen. Hope you know what I mean.
Posted: Mon Oct 11, 2004 8:08 am
by patrikG
you have to prioritise: do you want as many elements of the array to be used to calculate the total or do you want to simply reach the specified limit?
Posted: Mon Oct 11, 2004 8:12 am
by Schizoid
What I basically want is to be sure that I come as close to the limit as possible, using any number of elements from the array. So nevermind it being fast, I just want to make sure it's the optimal solution.
Posted: Mon Oct 11, 2004 8:23 am
by patrikG
Code: Select all
<?php
function array_sum_approximate($array,$limit){
//check if sum of array values <= $limit
if($array_sum=array_sum($array)<=$limit){
return $array_sum;
}
//if not sort array so that greatest element is first,
// then loop through it and let it approximate to $limit
$array = array_reverse(sort($array));
for($i=0;$i<count($array;$i++){
while($array_sum+$array[$i]<=$limit){
$return["array_sum"]+=$array[$i];
array_push($return["array_remainder"],$array[$i);
}
return $return;
}
?>
Would be something that looks at all values, but it surely is not the optimal solution. You see what I am getting at...