Как найти комбинацию из любого количества элементов подмассива requests, сумма значений которых будет максимальна близка, либо равна значению max_sum?

Question

[Алексей Владимиров]

Зздравствуйте, господа.
Существует массив вида:

[test] => Array
                (
                    [max_sum] => 15
                    [requests] => Array
                        (
                            [0] => 1
                            [1] => 2
                            [2] => 3
                            [3] => 4
                            [4] => 5
                            [5] => 6
                            [6] => 7
                            [7] => 8
                            [8] => 9
                            [9] => 10
                            [10] => 3
                            [11] => 5
                            [12] => 5
                            [13] => 1
                            [14] => 7
                            [15] => 8
                            [16] => 5
                        )
                )

Необходимо найти комбинацию из любого количества элементов подмассива requests(уникальных, т.е. без повторов), сумма значений которых будет максимальна близка, либо равна значению max_sum.
Количество элементов requests может быть довольно большим, и сама эта операция должна будет выполняться для большого количества таких массивов, при чем обязательно "на лету", т.е. важна скорость.

Буду безмерно благодарен за любые подсказки.

Answer 1

[Александр]

Ваша задача это ни что иное как интерпретация "задачи о ранце"
Полистайте, там есть алгоритмы решения.