Number crunching

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
Schizoid
Forum Newbie
Posts: 4
Joined: Mon Oct 11, 2004 7:06 am
Location: Denmark

Number crunching

Post 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.
User avatar
patrikG
DevNet Master
Posts: 4235
Joined: Thu Aug 15, 2002 5:53 am
Location: Sussex, UK

Post by patrikG »

What's the code you have so far?
Schizoid
Forum Newbie
Posts: 4
Joined: Mon Oct 11, 2004 7:06 am
Location: Denmark

Post 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. :)
User avatar
patrikG
DevNet Master
Posts: 4235
Joined: Thu Aug 15, 2002 5:53 am
Location: Sussex, UK

Post 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;
}
?>
Schizoid
Forum Newbie
Posts: 4
Joined: Mon Oct 11, 2004 7:06 am
Location: Denmark

Post 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.
User avatar
patrikG
DevNet Master
Posts: 4235
Joined: Thu Aug 15, 2002 5:53 am
Location: Sussex, UK

Post 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?
Schizoid
Forum Newbie
Posts: 4
Joined: Mon Oct 11, 2004 7:06 am
Location: Denmark

Post 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.
User avatar
patrikG
DevNet Master
Posts: 4235
Joined: Thu Aug 15, 2002 5:53 am
Location: Sussex, UK

Post 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...
Post Reply