PHP: найдите два или больше числа из списка чисел, которые складывают к данной сумме

Следующий метод даст вам ответ ... почти всегда. Увеличьте переменную итераций на свой вкус.

<?php

// Inputs
$n[1]=8.99;
$n[2]=1.45;
$n[3]=4.83;
$n[4]=8.16;
$n[5]=2.53;
$n[6]=0.28;
$n[7]=9.37;
$n[8]=0.34;
$n[9]=5.82;
$n[10]=8.24;
$n[11]=4.35;
$n[12]=9.67;
$n[13]=1.69;
$n[14]=5.64;
$n[15]=0.27;
$n[16]=2.73;
$n[17]=1.63;
$n[18]=4.07;
$n[19]=9.04;
$n[20]=6.32;

// Output
$t=57.96;

// Let's try to do this a million times randomly
// Relax, thats less than a blink
$iterations=1000000;
while($iterations-->0){
    $z=array_rand($n, mt_rand(2,20));
    $total=0;
    foreach($z as $x) $total+=$n[$x];
    if($total==$t)break;
}

// If we did less than a million times we have an answer
if($iterations>0){
    $total=0;
    foreach($z as $x){
        $total+=$n[$x];
        print("[$x] + ". $n[$x] . " = $total<br/>");
    }
}

?>

Одно решение:

[1] + 8.99 = 8.99
[4] + 8.16 = 17.15
[5] + 2.53 = 19.68
[6] + 0.28 = 19.96
[8] + 0.34 = 20.3
[10] + 8.24 = 28.54
[11] + 4.35 = 32.89
[13] + 1.69 = 34.58
[14] + 5.64 = 40.22
[15] + 0.27 = 40.49
[16] + 2.73 = 43.22
[17] + 1.63 = 44.85
[18] + 4.07 = 48.92
[19] + 9.04 = 57.96

Я не думаю, что ответ не так прост, как сказал Ник. пусть у вас есть следующие числа:

1 2 3 6 8

при поиске решения на сумму 10

никс сделает это (если я правильно понимаю):

1*8 = 9 = too low
adding next lowest (2) = 11 = too high

теперь он удалит большое число и снова начнет принимать новое высшее

1*6 = 7 = too low
adding next lowest (2) = 9 = too low
adding next lowest (3) = 12 = too high

... и так далее, где идеальным ответом будет просто 8 + 2 = 10 ... я думаю, что единственное решение - попробовать все возможные комбинации числа и остановитесь, если искомая задача найдена (или действительно вычислите все, если есть разные решения, и сохраните, какое из них использовало наименьшее количество чисел).

РЕДАКТИРОВАТЬ: на самом деле вычисление всех возможных комбинаций из 21 числа приведет к действительно, очень, очень многим вычислениям - поэтому должно быть какое-то «умное» решение для сложения чисел в особом порядке (например, тот, что в посте в никс - с некоторые улучшения, возможно, это приведет нас к надежному решению)

извините за добавление нового ответа, но это совершенно новое решение для решения всех проблем жизни, вселенной и всего остального ...:

function array_sum_parts($n,$t,$all=false){
    $count_n = count($n); // how much fields are in that array?
    $count = pow(2,$count_n); // we need to do 2^fields calculations to test all possibilities

    # now i want to look at every number from 1 to $count, where the number is representing
    # the array and add up all array-elements which are at positions where my actual number
    # has a 1-bit
    # EXAMPLE:
    # $i = 1  in binary mode 1 = 01  i'll use ony the first array-element
    # $i = 10  in binary mode 10 = 1010  ill use the secont and the fourth array-element
    # and so on... the number of 1-bits is the amount of numbers used in that try

    for($i=1;$i<=$count;$i++){ // start calculating all possibilities
        $total=0; // sum of this try
        $anzahl=0; // counter for 1-bits in this try
        $k = $i; // store $i to another variable which can be changed during the loop
        for($j=0;$j<$count_n;$j++){ // loop trough array-elemnts
            $total+=($k%2)*$n[$j]; // add up if the corresponding bit of $i is 1
            $anzahl+=($k%2); // add up the number of 1-bits
            $k=$k>>1; //bit-shift to the left for looking at the next bit in the next loop
        }
        if($total==$t){
            $loesung[$i] = $anzahl; // if sum of this try is the sum we are looking for, save this to an array (whith the number of 1-bits for sorting)
            if(!$all){
                break; // if we're not looking for all solutions, make a break because the first one was found
            }
        }
    }

    asort($loesung); // sort all solutions by the amount of numbers used


    // formating the solutions to getting back the original array-keys (which shoud be the return-value)
    foreach($loesung as $val=>$anzahl){
        $bit = strrev(decbin($val));
        $total=0;
        $ret_this = array();
        for($j=0;$j<=strlen($bit);$j++){
            if($bit[$j]=='1'){
                $ret_this[] = $j;
            }   
        }
        $ret[]=$ret_this;
    }

    return $ret;
}

// Inputs
$n[0]=6.56;
$n[1]=8.99;
$n[2]=1.45;
$n[3]=4.83;
$n[4]=8.16;
$n[5]=2.53;
$n[6]=0.28;
$n[7]=9.37;
$n[8]=0.34;
$n[9]=5.82;
$n[10]=8.24;
$n[11]=4.35;
$n[12]=9.67;
$n[13]=1.69;
$n[14]=5.64;
$n[15]=0.27;
$n[16]=2.73;
$n[17]=1.63;
$n[18]=4.07;
$n[19]=9.04;
$n[20]=6.32;

// Output
$t=57.96;

var_dump(array_sum_parts($n,$t)); //returns one possible solution (fuc*** fast)

var_dump(array_sum_parts($n,$t,true)); // returns all possible solution (relatively fast when you think of all the needet calculations)

if вы не используете третий параметр, он возвращает лучшее (с наименьшим количеством используемых чисел) решение в виде массива (с ключами входного массива) - если вы установите для третьего параметра значение true , ВСЕ решения возвращаются (для тестирования я использовал те же числа, что и zaf в его сообщении - в этом случае есть 338 решений, найденных за ~ 10 секунд на моей машине).

РЕДАКТИРОВАТЬ: если вы получите все, вы получите результаты, отсортированные по "лучшим" - без этого вы получите только первое найденное решение (которое не обязательно является лучшим).

РЕДАКТИРОВАТЬ2: чтобы удовлетворить желание некоторых пояснений, я прокомментировал существенные части кода. если кому-то нужны дополнительные объяснения, спросите

1. Check and eliminate fields values more than 21st field

2. Check highest of the remaining, Add smallest, 

3. if its greater than 21st eliminate highest (iterate this process)

   4. If lower: Highest + second Lowest, if equal show result.

   5. if higher go to step 7

   6. if lower go to step 4

7. if its lower than add second lowest, go to step 3.

8. if its equal show result

Это эффективно и требует меньше времени на выполнение.

Возможно неэффективное, но простое решение с обратным прослеживанием

function subset_sums($a, $val, $i = 0) {
    $r = array();
    while($i < count($a)) {
        $v = $a[$i];
        if($v == $val)
            $r[] = $v;
        if($v < $val)
            foreach(subset_sums($a, $val - $v, $i + 1) as $s)
                $r[] = "$v $s";
        $i++;
    }
    return $r;
}

пример

$ns = array(1, 2, 6, 7, 11, 5, 8, 9, 3);
print_r(subset_sums($ns, 11));

результат

Array
(
    [0] => 1 2 5 3
    [1] => 1 2 8
    [2] => 1 7 3
    [3] => 2 6 3
    [4] => 2 9
    [5] => 6 5
    [6] => 11
    [7] => 8 3
)

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

Подсказка:

Сравните каждое значение поля со всеми значениями поля и на каждой итерации проверяйте, равна ли их сумма TOTAL_AMOUNT .

Псевдокод:

for i through field  1-20
 for j through field 1-20
   if value of i + value of j == total_amount
        return i and j

Обновление:

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