多个数字组合的代码在 php 中不起作用

Question

我使用以下代码获得给定数组中数字的最佳组合。首先，我想要数字总和小于或等于 15 (<=15) and greater than 14 (>14)，然后找到 12 (>11) 总和的剩余数字的最佳组合，然后将显示剩余总和。我在数组中提供输入值，它将适用于 20 个值，但如果值增加，代码将被挂起，无法正常工作。请建议我任何更改。

$g = array(4.66,4.66,4.54,4.54,2.33,2.33,3.83,3.83,3.91,3.91);


//$g = array(4.66,4.66,4.54,4.54,2.33,2.33,3.83,3.83,3.91,3.91,2.36,5.33,4.59,1.69,4.77,2.10,6.0,3.23,3.98,4.22,1.44,2.78,3.88,3.69,5.55,3.69,2.56,3.55,4.63,1.5,2.8,);   // Code will hang for this input

$total = 0;
for($h=0;$h<count($g);$h++)
{
    $total = $total + $g[$h];   
} 
$fif_sec = intdiv($total,15);

for($q=0;$q<($fif_sec+1);$q++)
{
    $desiredSum = 15;
    $minDist = null;
    $minDist_I = null;
    // Iterate on every possible combination
    $maxI = pow(2,sizeof($g));
    for($i=0;$i<$maxI;$i++) {
    if(!(($i+1) % 1000)) echo ".";

    $sum = 0; $sum1 = 0;
    for($j=0;$j<sizeof($g);$j++) {
        if($i & (1 << $j)) {
            $sum1 += $g[$j];
            if($sum1 < 15)
            {
                $sum += $g[$j];
            }
        }
    }
    $diff = abs($sum - $desiredSum);
    //echo '<br/>!!!'.$diff;
    if($minDist_I === null || $diff < $minDist) {
        $minDist_I = $i;
        $minDist = $diff;
    }

    if($diff == 0) break;
}
$chosen = array();
for($j=0;$j<sizeof($g);$j++) {
    if($minDist_I & (1 << $j)) $chosen[] = $g[$j];
}

if(array_sum($chosen) < ($desiredSum -1))  
{
    for($q12=0;$q12<(array_sum($chosen)/12);$q++)
    {
     //for 12 foot section
       $desiredSum12 = 12;
       $minDist12 = null;
        $minDist_I12 = null;
        
        $maxI12 = pow(2,sizeof($g));
        for($it=0;$it<$maxI12;$it++) {
            if(!(($it+1) % 1000)) echo ".";

            // Figure out which numbers to select in this 
            $sum12 = 0; $sum112 = 0;
            for($jt=0;$jt<sizeof($g);$jt++) {
                if($it & (1 << $jt)) {
                    $sum112 += $g[$jt];
                    if($sum112 < 12)
                    {
                        $sum12 += $g[$jt];
                    }
                }
            }
            $diff12 = abs($sum12 - $desiredSum12);
            //echo '<br/>!!!'.$diff;
            if($minDist_I12 === null || $diff12 < $minDist12) {
                $minDist_I12 = $it;
                $minDist12 = $diff12;
            }

            if($diff12 == 0) break;
        }
        $chosen = array();
        for($jt=0;$jt<sizeof($g);$jt++) {
            if($minDist_I12 & (1 << $jt)) $chosen[] = $g[$jt];
        }

        if(array_sum($chosen) < ($desiredSum12 -1))  //if sum is less 14 (13 < 14) then go for 12 foot
        {
            break;
        }
        else
        {
            $sections .= '<br/><strong>12 Foot</strong>: '. implode(", ", $chosen) .', ';
            $sec12 = $sec12 + 1;
            //delete value from array
            for($p12=0;$p12 < count($chosen); $p12++)
            {
                if (($key = array_search($chosen[$p12], $g)) !== false) {
                unset($g[$key]);
                $g = array_values($g);
                }
            }
            if(array_sum($g) > 12)
            {

            } 
            //var_dump($g); 
        }
    }
}
else
{
    $sections .= '<br/><strong>15 Foot</strong>: '.  implode(", ", $chosen) .', ';
    $sec15 = $sec15 + 1;
    
    for($p=0;$p < count($chosen); $p++)
    {
        if (($key = array_search($chosen[$p], $g)) !== false) {
        unset($g[$key]);
        $g = array_values($g);
        }
    }
    }
}//for

if(count($g) != 0)
{
    $sections .= '<br/><strong>'.ceil(array_sum($chosen))." Foot</strong>: ".  implode(", ", $chosen);
    $secLast = $secLast + 1;
    $secLastN = ceil(array_sum($chosen));
    for($p=0;$p < count($chosen); $p++)
    {
        if (($key = array_search($chosen[$p], $g)) !== false) {
        unset($g[$key]);
        $g = array_values($g);
        }
    }
}
}

if(array_sum($chosen) < 12)
{
for($i=0;$i<count($g);$i++)
{
    if(round($g[$i])!=0)
    {
        $sections .=  '<br/><strong>'.ceil($g[$i]) . ' Remaining Foot:</strong>'. $g[$i];
        $secLast1 = $secLast1 + 1;
        $secLast1N = ceil($g[$i]);
    }
}
}

if($sec15!=0)
{
$remSec .= "15 Foot/<strong>" .$sec15 . "</strong>, ";  
}

if($sec12!=0)
{
$remSec .= " 12 Foot/<strong>".$sec12."</strong>, ";    
}

if($secLast!=0)
{
$remSec .= $secLastN ." Foot/<strong>".$secLast."</strong>, ";
}
if($secLast1!=0)
{
$remSec .=  $secLast1N." Foot/<strong>".$secLast1."</strong>";
}

Answer 1

我可以建议一个特定的 SW 技术，它包括使用 generators，这使得更容易将停止搜索的条件推到解决方案空间探索循环的深处：

function sum_to_range(array $numbers, float $higherThan, float $lowerOrEqualThan, float $summed): iterable {
  while (!empty($numbers)) {
    $first = array_shift($numbers);
    $updated = $summed + $first;
    if ($updated > $higherThan && $updated <= $lowerOrEqualThan) {
      yield [$updated, $numbers];
    }
    if ($updated > $lowerOrEqualThan)
      break;
    yield from sum_to_range($numbers, $higherThan, $lowerOrEqualThan, $updated);
    /* 'yield from' seems worth to use...
    foreach(sum_to_range($numbers, $higherThan, $lowerOrEqualThan, $updated) as list($sub, $rest))
      if ($sub > $higherThan && $sub <= $lowerOrEqualThan) {
        yield [$sub, $rest];
      }
    */
  }
}

很抱歉，它没有强制执行任何 optimbility 标准，还因为您没有明确说明您感兴趣的标准（值最大值，使用的序列最小值......）。 但它可以给你一个起点：它在相对较短的时间内找到每一个可能的总和，这里我只是计算它们：

  $c = 0;
  $g = array(4.66,4.66,4.54,4.54,2.33,2.33,3.83,3.83,3.91,3.91);
  $g = array(4.66,4.66,4.54,4.54,2.33,2.33,3.83,3.83,3.91,3.91,2.36,5.33,4.59,1.69,4.77,2.10,6.0,3.23,3.98,4.22,1.44,2.78,3.88,3.69,5.55,3.69,2.56,3.55,4.63,1.5,2.8,);   // Code will hang for this input
  sort($g);
  foreach(sum_to_range($g, 14, 15, 0) as list($sum_14_15, $rest_14_15)) {
    foreach(sum_to_range($rest_14_15, 11, 12, 0) as list($sum_11_12, $rest_11_12)) {
      $rest = array_sum($rest_11_12);
      ++$c;
      //print_r(compact('sum_14_15','sum_11_12', 'rest'));
    }
  }
  echo "tot: $c\n";

产生

tot: 110136

有关 Generator Syntax 的有趣页面，了解“yield”或“yield from”的介绍。我认为有趣的是，它们可以在几种主流语言中使用，例如 Python、Javascript、C# 等……