如何从此数组中获取所需的总和

Question

This is the code I currently have:

$required = 1.3;
$stacks = 0;
$remaining = $required;
$whichtakes = [];
$array_result = ['0.6', '0.5', '0.8', '0.7'];
for($i = 0; $i < count($array_result); $i++) {
    if($array_result[$i] <= $required  && $stacks + $array_result[$i]  <= $required) {
        $stacks += $array_result[$i];
        echo $remaining -= $array_result[$i];
        $whichtakes[] = $array_result[$i];
    }
}
print_r($whichtakes);

Output is

Array (
    [0] => 0.6
    [1] => 0.5
)

This is fetching just 0.6 and 0.5 (first two values) and gives a remaining value (the sum is 1.1, so 0.2 is remaining). But the input has 2 values whose sum matches with my $required value: 0.8 and 0.7.

How can I improve my code so that it will find those values? If there is no exact match possible, I would like to get a series of values whose sum comes as close as possible, minimising the remaining value.

Answer 1

After more explanation in comments, it turns out you want to find an algorithm for this input/output:

Input:

• a total amount, and
• an array with amounts

Output:

• the "closest subset": a selection of amounts from the input array (not necessarily a pair) that has the largest sum that is not greater than the given total amount.
• the difference between the sum of that subset and the given total amount

You can achieve that as follows:

Generate all combinations, keyed by the sums (or remainders) they generate, but stop adding elements when their sums becomes too large. This can be done with simple iteration over the elements and updating a hash, keyed by the sums (or remainders) that are found by adding the value to previously found sums.

Here is how that looks:

// Input
$required = 1.3;
$array_result = [0.6, 0.5, 0.8, 0.7];

// Algorithm
$remainings = [(string)$required => []]; // Keyed by remaining value; gives array elements that have that remainder

foreach($array_result as $i => $val) {
    foreach($remainings as $remaining => $whichtakes) {
        if ($remaining >= $val) $remainings[(string)($remaining-$val)] = array_merge($whichtakes, [$val]);
    }
}
$remaining = min(array_keys($remainings));
$whichtakes = $remainings[(string)$remaining];

// Output
print_r($whichtakes);   // [0.6, 0.7]
print_r($remaining);    // 0