PHP наибольшее целое число из суммы несортированного массива

Question

Может кто-нибудь сказать мне лучший способ найти наибольшее целое число, суммированное из несортированного массива?

например,

{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)

спасибо

Обновить

Я принял метод, который использовал, но некоторые из приведенных ниже будут программно правильными

Answer 1

Я бы предложил суммировать весь массив, а затем найти наименьшую сумму с десятичной частью, равной сумме всей суммы.Если числа не имеют очень высокой точности после десятичной точки, каким бы ни был подход к нахождению точного числа, это обращение должно спасти много вычислений.

Кроме того, сортировка массива и жадность от наименьших чисел можетдать хорошие результаты.Тем не менее, оптимальное решение очень зависит от природы исходного набора.Не могли бы вы предоставить более подробные спецификации о том, какие цифры вы ожидаете?

Answer 2

Основная часть этого кода предназначена для получения перестановок массива. Я уверен, что это можно оптимизировать, но это вычисление 3 массивов с длинами 4, 5 и 6 в 45 мс на четырехъядерном одном сервере Xeon. Переход на 220 мс при добавлении 4-го массива с 7 десятичными знаками и огромных 2 секунд, если я добавляю 5-й с 8.

По сути, все, что это делает, это получает все перестановки массива, содержащего числа с плавающей запятой, складывает каждую из них ключ за ключом, и, если сумма является целым числом, превышающим текущее целое число, обновляет это число .. В конечном итоге возвращает максимально возможное число.

$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

Кредит функции перестановки массива переходит в dirk dot avery a t gmail при http://php.net/manual/en/function.shuffle.php

Answer 3

Это большая проблема для размышления.Вдобавок ко всему, это псевдокод, который я бы использовал:

1. A = массив элементов.
2. A '= отсортированный массив элементов.
3. S = сумма всех элементов.
4. Пока A 'не пусто:
   1. V = целая часть S.
   2. R = остаток S = S - этаж(S)
   3. Сделать временную копию A ', X.
   4. Итерировать от наибольшего к наименьшему значению X как X [i]:
      1. Если X [i]
      2. Если R == 0, мы нашли решение.V - целое число, X содержит дополнения.STOP.
   5. Если X пусто, решения не существует.STOP.
   6. Уменьшить S на наибольшее значение в A '.S = S - Макс (A ').Удалите Макс (A ') из A'.
5. Вернитесь к шагу № 4.

Конечно, я должен был посмотреть, сработает ли это на самом деле,Вот код (очень грязный, выбрасываемый), который я написал, чтобы проверить его:

<?php
$AA = $A = array(0.1, 0.2, 0.9, 0.5);

bcscale(8);

sort($AA, SORT_NUMERIC);
echo 'A = ' . implode(', ', $A), PHP_EOL;
echo 'A\' = ' . implode(', ', $AA), PHP_EOL;

$S = array_sum($AA);
echo 'S = ' . $S, PHP_EOL;

while (count($AA)) {
    $V = floor($S);
    echo 'V = ' . $V, PHP_EOL;

    $R = bcsub($S, $V);
    echo 'R = ' . $R, PHP_EOL;

    $X = $AA;
    $XX = array();

    // Look for the largest value that is less than or equal to R.
    for ($i = count($X) - 1; $i >= 0; $i--) {
        echo 'X[i] = ' . $X[$i] . ', R = ' . $R, PHP_EOL;
        $c = bccomp($X[$i], $R);
        if ($c > 0) {
            continue;
        }
        $XX[] = $X[$i];
        $R = bcsub($R, $X[$i]);
        unset($X[$i]);

        if (bccomp($R, '0', strlen($R)) == 0) {
            echo 'Largest whole number sum: ' . $V, PHP_EOL;  
            echo 'Elements: ' . implode(', ', $X), PHP_EOL;   
            break 2;
        }
    }

    if (count($X) == 0) {
        echo 'No sums to a whole number are possible.', PHP_EOL;
        break;
    }

    $t = array_pop($AA);
    $S = bcsub($S, $t);
}

echo 'S = ' . $S, PHP_EOL;
?>

Это уродливый алгоритм O (N ^ 2), но он должен быть правильным.Может кто-нибудь увидеть начальный начальный массив, где это не получится?

Ради интереса, я попробовал с массивом из 50 элементов, заменив первую строку на следующие строки:

$A = array();
for ($i = 0; $i < 50; $i++) {
    $A[] = mt_rand(1, 99) / 100.0;
}
$AA = $A;

Краткий обзор, это выглядит правильно - я оставлю проверку кому-то еще;)

Answer 4

ОК, думая об этом.

$sum = array_sum($arr);
$floor_sum = floor($sum);
if ($sum = $floor_sum){
return $sum
}else{

for ($i = 0; $i < sizeof($arr); $i++){
  if ($sum - $arr[$i] = $floor_sum){
     return $sum - $arr[i];
  }else{
    for ($x = 0; $x < sizeof($arr)- 1; $x++){
      if ($x != $i){
        if ($sum - $arr[$i] - $arr[$x] = $floor_sum){
         return $sum - $arr[$i] - $arr[$x];
        }else {
            //Iterate more times
        }
      }
    }
  }
}

}

У меня есть вышесказанное, но должен быть более простой способ сделать это?

Answer 5

Я не написал код для этого, но код псевдо приведен ниже. Общая идея заключается в том, что вы вычисляете комбинации (x выбираете y ... http://en.wikipedia.org/wiki/Combination), а затем суммируете каждую из этих комбинаций. Вы перебираете это для длины массива, а затем берете свой максимум.

Я также уверен, что есть оптимизация относительно жадности и короткого замыкания в этом цикле.

$len = count($decimals);
$maxVals = array();

for( $choose = $len; $choose > 1; $choose-- ) {
    // get $decimals choose $choose

    // loop and sum each choose array, checking for an integer sum

    // store max if exists
}

return sum($maxVals);

Answer 6

как то так?

 $array=array(0.1, 0.2, 0.9, 0.5);
 arsort($array);
 while($highest=array_shift($array)){
   foreach($array as $val){
    $thisval=($highest+val);
    if(round($thisval)==($thisval)){
     return $thisval;
   }
 }
}

РЕДАКТИРОВАТЬ: @Felix Kling вы абсолютно правы, добавил цикл while