PHP largest whole number from sum of unsorted array

Question

Can someone tell me the best way to find the largest whole number summed from an unsorted array?

e.g.

{0.1, 0.2, 0.9, 0.5}

Largest whole number possible is 1 (0.1 + 0.9).

{0.9, 0.2, 0.5, 0.3, 0.9}

Largest possible is 2 (0.9 + 0.9 + 0.2)

thanks

Update

I've accepted the method that i used but some of the below will be programmatically correct

Answer 1

I would suggest summing up the whole array and then finding the smallest sum with the decimal part equal to that of the whole sum. Unless the numbers have very high precision after the decimal point, whatever the approach to finding the exact number is, this reversal should save a lot of computation.

Also, sorting the array and going greedy from the smallest numbers might yield nice results. However, the optimal solution is very dependent on the nature of the initial set. Could you provide any closer specifications on what kind of numbers you expect?

Answer 2

The bulk of this code is for getting the permutations of an array. I'm sure it can be optimized, but this is calculating 3 arrays with lengths of 4, 5 and 6 in 45ms on a quad core single Xeon server. Jumps to about 220ms when I add a 4th array with 7 decimals and a whopping 2 seconds if I add a 5th with 8.

Basically, all this does is get all of the permutations of the array containing the floats, adds each one together key by key, and if a the sum is a whole number larger than the current whole number, updates that number.. Eventually returning the largest possible number.

$set1 = array(0.1, 0.2, 0.9, 0.5);
$set2 = array(0.9, 0.2, 0.5, 0.3, 0.9);
$set3 = array(0.9, 0.2, 0.5, 0.3, 0.9, 0.4);

function largestWholeNumber($decimals){
    echo "Calculating largest whole number for decimal set '"
    . implode(",", $decimals)
    . "'<br />";
    $perms = perms($decimals);
    $answer = 0;
    foreach($perms as $dec_array){
        $current_guess = 0;
        foreach($dec_array as $dec){
            $current_guess += $dec;
            if (!preg_match("/[^0-9]+/", $current_guess)){
                if ($answer < $current_guess){
                    $answer = $current_guess;
                    echo "New whole number found " 
                    ."'$answer'"
                    ." with permutation: <br />";
                    print_r($dec_array);
                    echo "<br />";
                }
            }
        }
    }
    echo "Result: $answer<br /><br />";
    return $answer;
}

function factorial($int){
if($int < 2) {
       return 1;
}

for($f = 2; $int-1 > 1; $f *= $int--);

return $f;
}


function perms($arr) {
    $p = array();
    for ($i=0; $i < factorial(count($arr)); $i++) {
        $p[] = perm($arr, $i);
    }
    return $p;
}


function perm($arr, $nth = null) {

    if ($nth === null) {
        return perms($arr);
    }

    $result = array();
    $length = count($arr);

    while ($length--) {
        $f = factorial($length);
        $p = floor($nth / $f);
        $result[] = $arr[$p];
        array_delete_by_key($arr, $p);
        $nth -= $p * $f;
    }

    $result = array_merge($result,$arr);
    return $result;
}
function array_delete_by_key(&$array, $delete_key, $use_old_keys = FALSE) {

    unset($array[$delete_key]);

    if(!$use_old_keys) {
        $array = array_values($array);
    }

    return TRUE;
}

largestWholeNumber($set1); // 1
largestWholeNumber($set2); // 2
largestWholeNumber($set3); // 3

Credit to the array permutation function goes to dirk dot avery a t gmail at http://php.net/manual/en/function.shuffle.php