Как получить группы чисел из массива PHP сумма которых равна = N?

Question

[sergeyflancer]

Нужно получить комбинацию чисел сумма которых равна заданному значению. Пока остановился на таком, но код очень долго работает.

$array = [
    '0' => 2000,
    '1' => 2000,
    '2' => 2000,
    '3' => 2000,
    '4' => 2000,
    '5' => 2000,
    '6' => 2000,
    '7' => 1000,
    '8' => 200,
    '9' => 200,
    '10' => 200,
    '11' => 200,
    '12' => 200,
    '13' => 200,
    '14' => 200,
    '15' => 200,
    '16' => 100,
    '17' => 100,
    '18' => 100,
    '19' => 100,
    '20' => 100,
    '21' => 100,
    '22' => 100,
    '23' => 100,
    '24' => 100,
    '25' => 100,
    '26' => 100,
    '27' => 100,
    '28' => 100,
    '29' => 100,
    '30' => 100,
    '31' => 100,
    '32' => 100,
    '33' => 100,
    '34' => 50,
    '35' => 50,
    '36' => 50,
    '37' => 50,
    '38' => 50,
    '39' => 50,
    '40' => 50,
    '41' => 50,
    '42' => 50,
    '43' => 50,
    '44' => 50,
    '45' => 50,
    '46' => 50,
    '47' => 50,
    '48' => 50,
    '49' => 50,
    '50' => 50,
    '51' => 50
];

function getCombos($array, $cost){

    if(in_array($cost, $array))  return [$cost];

    $array = array_filter($array, function ($item) use($cost){
        return $item <= $cost;
    });
    $array = array_values($array);

    for ($dec = 1; $dec < pow(2, count($array)); $dec++) {
        $curterm = array();
        foreach (str_split(strrev(decbin($dec))) as $i => $bit) {
            if ($bit) {
                $curterm[] = $array[$i];
            }

            if((array_sum($curterm) > $cost)) continue 2;

            if((array_sum($curterm) == $cost)){
                return $curterm;
            }
        }

        if((array_sum($curterm) == $cost)){
            return $curterm;
        }
    }

    return false;
}


print_r(getCombos($array, 250));

Опишу подробнее задачу.
В базе есть сертификаты с определенным номиналом(могут повторяться). Нужно при заказе выдавать сертификаты на сумму заказа(желательно выдавать сертификаты с большим номиналом в первую очередь, например на сумму 550 выдавать 500+50 или 200+200+100+50).
Средствами mysql решить задачу не удалось поэтому решил попробовать на уровне PHP

Answer 1

[Dmitry Bay]

Не вижу проблемы.

1) Вы знаете, что сертификаты у вас
50 100 200 300 500 2000 рублей к примеру. Лучше, чтобы было меньше вариаций.

2) Клиенту надо дать купонов на 5000

Делаем выборку по кол-ву купонов (group by coupon_value where coupon active) , получаем массив из 5-15 элементов.
Далее идем от большего значения и набираем максимальными купонами скидку.
получаем, что то типа такого массива [2000=>2, 500=>2]
А дальше делаем запросы на погашение купонов на базу.

Итого запросов 2-~10 на базу очень простых.

Comments

[sergeyflancer]

Можно пример кода для моих данных?

Вот к примеру нужно из массива получить комбинацию чисел(могут повторяться) сумма которых равна 2350

[Dmitry Bay]

sergeyflancer,
1) запрос sql
"select count(id) as couponsCount, value from coupons where active=1 group by value"
2) переводим полученный результат к массиву формата и сортируем по ключу в обратную сторону
[
value=>couponsCount,
...
]

3)
Делаем while цикл, где вычитаем с значения по очереди купоны, пока не получим 0 или пока купоны не закончатся. тут уж сами додумайте как сделать.

[sergeyflancer]

Благодарю за помощь. Сделал так. Уверен что можно было бы как то красивее но главное работает

function test($array, $cost)
{
    $group = [];
    foreach ($array as $item){
        $group[$item] = !empty($group[$item]) ? $group[$item] + 1 : 1;
    }

    $tmp_cost = $cost;
    $certs = [];
    foreach ($group as $amount => $count){
        while ($count > 0) {
            if(($tmp_cost - $amount) == 0) {
                $tmp_cost = $tmp_cost - $amount;
                $certs[] = $amount;
                break;
            } elseif($tmp_cost - $amount > 0) {
                $tmp_cost = $tmp_cost - $amount;
                $certs[] = $amount;
            }
            $count--;
        }
    }

    return array_sum($certs) == $cost ? $certs : false;
}

$cost = 3550;
$array = [
    '0' => 2000,
    '1' => 2000,
    '2' => 2000,
    '3' => 2000,
    '4' => 2000,
    '5' => 2000,
    '6' => 2000,
    '7' => 1000,
    '8' => 200,
    '9' => 200,
    '10' => 200,
    '11' => 200,
    '12' => 200,
    '13' => 200,
    '14' => 200,
    '15' => 200,
    '16' => 100,
    '17' => 100,
    '18' => 100,
    '19' => 100,
    '20' => 100,
    '21' => 100,
    '22' => 100,
    '23' => 100,
    '24' => 100,
    '25' => 100,
    '26' => 100,
    '27' => 100,
    '28' => 100,
    '29' => 100,
    '30' => 100,
    '31' => 100,
    '32' => 100,
    '33' => 100,
    '34' => 50,
    '35' => 50,
    '36' => 50,
    '37' => 50,
    '38' => 50,
    '39' => 50,
    '40' => 50,
    '41' => 50,
    '42' => 50,
    '43' => 50,
    '44' => 50,
    '45' => 50,
    '46' => 50,
    '47' => 50,
    '48' => 50,
    '49' => 50,
    '50' => 50,
    '51' => 50
];

print_r(test($array, $cost));

Array
(
    [0] => 2000
    [1] => 1000
    [2] => 200
    [3] => 200
    [4] => 100
    [5] => 50
)

[Vitsliputsli]

sergeyflancer, значения в массиве всегда кратны друг другу? Т.к. работать будет только в этом случае.
Если взять некратные значения, то работать не будет:
$cost = 1100;
$array = [
'7' => 1000,
'8' => 300,
'9' => 300,
'10' => 300,
'11' => 200,
];

[sergeyflancer]

Это понятно. Так и должно быть. Если кратно и удалось выбрать сертификаты на нужную сумму возвращаются их номиналы, если нет - false

[Dmitry Bay]

sergeyflancer, зачем вам список id каждого купона.

Вам достаточно иметь кол-во доступных каждого номинала.