來自未分類數組總和的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

這樣的事情？

$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克林你是絕對正確的，添加了一個while循環

Answer 3

我沒有寫這個代碼，但僞代碼如下。一般的想法是，你計算組合（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 4

一下OK思考。

$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

該代碼的大部分用於獲取數組的排列。我確信它可以被優化，但是這是在四核心單Xeon服務器上計算45個長度爲4,5和6的3個陣列。當我添加第7個小數點的第4個數組時跳到大約220ms，如果我用第8個數添加第5個數列，跳到大約220ms。

基本上，所有這些都是獲取包含浮點數的所有數組的排列，一個按鍵一起按鍵，如果總和是一個大於當前整數的整數，則更新該數字。最終返回儘可能大的數字。

$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 6

這是思考一個很大的問題。關閉我的頭頂，這是我使用的僞代碼：

1. A =元素數組。
2. A'=排序的元素數組。
3. S =所有元素的總和。
4. 雖然A '不爲空：
   1. V = S. S = S的
   2. R =餘數的整數部分 - 地板（S）
   3. 使一個的臨時副本'，X。
   4. 迭代從最大到作爲X X的最小值[I]：
      1. 如果X [I] < R，減去X [I]從R.移去X [I]從X.
      2. 若R == 0，我們找到了解決方案。 V是整數，X包含加數。停。
   5. 如果X爲空，則沒有解決方案。停。
   6. 將A減小到最大值。 S = S - Max（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; 

一目瞭然，它看起來正確 - 我會離開驗證了別人;）