请问如何在未排序的数组中找到最大的整数之和？
例如：
{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)
谢谢
更新
我已经接受了我使用的方法，但以下一些内容将以编程方式进行更正。
6个回答
3
我建议将整个数组求和，然后找到小数部分等于整个和的最小和。除非数字在小数点后具有非常高的精度，无论采用何种方法找到精确数字，这种反转都可以节省大量计算。
此外，对数组进行排序并从最小数字开始贪心可能会产生良好的结果。但是，最优解非常依赖于初始集合的性质。您能否提供更接近的规格，以了解您期望的数字类型？
此外，对数组进行排序并从最小数字开始贪心可能会产生良好的结果。但是，最优解非常依赖于初始集合的性质。您能否提供更接近的规格，以了解您期望的数字类型？
- David Miler
1
谢谢 David，这与我想的类似。说实话，准确性不是问题，但很好的。所以我对数组求和，然后按升序排列并从总和中取出数组中的第一个数字，并检查它是否为整数。它并不总是能够得到最高的数字，但对我来说足够好了。谢谢 - Matt
1
这段代码的主要作用是获取数组的排列组合。我相信它可以被优化，但是在一个四核单 Xeon 服务器上，计算长度为 4、5 和 6 的三个数组只需要 45 毫秒。如果我添加一个有 7 位小数的第四个数组，时间会跳到约 220 毫秒，如果再添加一个有 8 位小数的第五个数组，则需要长达 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
- Mahdi.Montgomery
1
添加了一个回显，这样你就可以看到它是如何得出答案的。 - Mahdi.Montgomery
0
像这样的东西？
$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循环
- Trey
6
我不熟悉这个语法:-/ - Trey
1@trey：我的意思是，如果你有这些值怎么办？你的代码只会将最高值与其他所有值相加。在这种情况下，得到整数和的总和是
0.7和0.3，但你从未测试过这些值。 - Felix Kling1这个还不错，但是它能处理涉及超过2个数字的求和吗？例如，
{0.1, 0.2, 0.6, 0.7} - 最大的整数求和将是 0.7 + 0.2 + 0.1。 - user212218嗯，确实如此...也许先求和再尝试删除值？我不确定在不进行荒谬的迭代的情况下处理这个问题的最有效方法是什么。 - Trey
@trey：因此这是一个背包问题，除了蛮力算法以外没有简单的解决方案。 - Marc B
是的，我一直在处理这个问题，但似乎情况确实如此。 - Trey
0
好的，我考虑一下。
$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
}
}
}
}
}
}
我有以上代码，但肯定有更简单的方法吧？
- Matt
2
该死，这意味着$floor_sum实际上是可能的。 - Matt
我猜我可以从$floor_sum减去1，然后重新开始...有人有BlueGene吗？ - Matt
0
这是一个很好思考的问题。我能想到的伪代码如下：
- A = 元素数组。
- A' = 排序后的元素数组。
- S = 所有元素的和。
- 当 A' 不为空时：
- V = S 的整数部分。
- R = S 的余数 = S - floor(S)
- 创建 A' 的临时副本 X。
- 从 X 中按照从大到小的顺序迭代 X[i]：
- 如果 X[i] < R，则从 R 中减去 X[i]。从 X 中删除 X[i]。
- 如果 R == 0，则找到了解决方案。V 是整数，X 包含加数。停止。
- 如果 X 为空，则无解。停止。
- 将 A' 中最大值减少。S = S - Max(A')。从 A' 中删除 Max(A')。
- 返回步骤 #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;
乍一看，它看起来是正确的 - 我会让其他人来验证 ;)
- dossy
0
我还没有编写过这段代码，但伪代码如下。 总体思路是计算组合（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);
- Ben Roux
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
{0.1, 0.1, 0.1, 0.2}。 - Fosco