确定数组中值的最大部分以匹配给定值

Question

I have an array with values:

$values = array(
    2,
    4,
    7.5,
    9
);

And i have a separate value:

$total = 12;

What's the correct mathematical approach to pick out values from $values, with the greater values coming first and the lesser values coming last, until the value of $total is reached or closely approached, but never exceeded?

I am aware that this is a basic mathematical problem, but i am pretty incapable of maths, and i have no idea how to accomplish this.

Answer 1

Ironically, i ended up with a fairly compact piece of code, which beautifully solves the problem - and proves that this is not the knapsack problem per sé.

$total = 7.9;
$values = array(2, 2.5, 5, 8);
$computed = 0;

rsort($values);

foreach($values as $val) {
    if($val + $computed > $total)
        continue;
    $computed += $val;
}

That's it.