请问如何在未排序的数组中找到最大的整数之和?
例如:
{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)
谢谢
更新
我已经接受了我使用的方法,但以下一些内容将以编程方式进行更正。
$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
像这样的东西?
$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循环
0.7
和0.3
,但你从未测试过这些值。 - Felix Kling{0.1, 0.2, 0.6, 0.7}
- 最大的整数求和将是 0.7 + 0.2 + 0.1
。 - user212218好的,我考虑一下。
$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
}
}
}
}
}
}
这是一个很好思考的问题。我能想到的伪代码如下:
当然,我必须测试一下这是否真的可行。以下是我编写的(非常混乱、一次性的)代码来测试它:
<?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;
我还没有编写过这段代码,但伪代码如下。 总体思路是计算组合(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);
{0.1, 0.1, 0.1, 0.2}
。 - Fosco