Как сложить элементы массива в разных вариациях?

Question

[Александр Вербицкий]

Например есть массив
$array = [1, 2, 3, 4, 5]

И нужно сложить эти числа в разных вариациях
1+2
1+3
1+4
1+2+4
3+2+5
и т.д.

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

Т.е. если сумма этих элементов, например, равна 20, останавливаем поиск, и показываем что входит в эту сумму.

Последнее условие я уже сам додумаю, а вот само перечисление вариаций для сложения чисел что-то не для моего ума...

Comments

[poniyur]

Типичная задача о рюкзаке.
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...
Не понял про "рекурсивно сложить числа", не понимаю, где тут рекурсия вообще нужна.

[BoShurik]

poniyur, немного не она. Там два параметры: ценность и объем, а тут обычный перебор по одному параметру

Answer 1

[wisgest]

Тупой просмотр всех возможных подмножеств множества индексов (подмножество задаётся двоичным числом: 1 — есть элемент, 0 — нет элемента). Без рекурсии. Без оптимизации.

<?php
$array = [1, 2, 3, 4, 5];
$SUM = 7;

$LIMIT = 1 << count($array);
for ($set = 0; $set < $LIMIT; $set++) {
	$s = 0;
	for ($i = 0; $i < count($array); $i++)
		if ((1 << $i) & $set) $s += $array[$i];
	if ($s == $SUM) {
		echo 'Индексы элементов массива, составляющих сумму: ';
		for ($i = 0; $i < count($array); $i++)
			if ((1 << $i) & $set) echo $i, ' ';
		break;
	}
}

Comments

[Александр Вербицкий]

Подскажите, а что значит <<?
Что-то ни когда не использовал такой оператор

[wisgest]

Побитовые операторы

[Vitsliputsli]

Александр Вербицкий, это операции с битами, это:
$LIMIT = 1 << count($array);
сдвиг влево всех битов 1 на count($array) позиций, по-сути это можно записать как:
$LIMIT = 2 ** count($array);
Но как указал wisgest, здесь смысл именно в операциях с битами.

Answer 2

[BoShurik]

Вариант с рекурсией (все-таки отмеченное решение уже на 50 элементах заметно тормозит)

$array = array_fill(0, 50, 1);
$sum = 20;

function elements($array, $sum, &$result = [], $iteration = [])
{
    // Если нужны все перестановки, то нужно закомментировать условие
    if (!empty($result)) {
        return;
    }
    if ($sum === 0) {
        $result[] = $iteration;

        return;
    }

    foreach ($array as $index => $value) {
        if ($sum - $value < 0) {
            continue;
        }

        $next = $array;
        unset($next[$index]);

        elements($next, $sum - $value, $result, array_merge($iteration, [$index]));
    }

    return;
}

elements($array, $sum, $result);

// Если вытащены все возможные перестановки, то разкомментировать
// Отсортируем, чтоб убрать повторяющиеся элементы
//foreach ($result as &$item) {
//    sort($item);
//}
//unset($item);
//$result = array_unique($result, SORT_REGULAR);

foreach ($result as $item) {
    echo 'Индексы элементов массива, составляющих сумму: ' . implode(' ', $item) . \PHP_EOL;
}

Answer 3

[Дмитрий]

https://www.php.net/manual/ru/function.array-sum.php
Ещё вариант

$stop = 42;

$items = range(1, 100);

$sum = 0;

$i = 0;

while($sum <= $stop) {
    $sum += $items[$i];
    $i++;
}
echo $sum;

Comments

[Александр Вербицкий]

Так это просто сумма всех элементов массива
Мне нужны разные варианты сложения чисел

[Дмитрий]

Александр Вербицкий, ну это тогда сложнее, вариантов с каждым новым элементом массива будут только расти. Уточните тогда в вопросе
Как минимум один результат так можно посчитать)