2018-07-13 08:20

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

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.

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答

#### 2条回答默认 最新

• douyou8047 2018-07-13 11:55
已采纳

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

点赞 打赏 评论
• dougao7801 2018-07-13 09:16

This algorithm will find all pairs that adds up to the \$required value:

\$required = 1.3;
\$array_result = ['0.6', '0.5', '0.8', '0.7'];

foreach (\$array_result as \$value) {

\$remaining = \$required - \$value;
if (in_array((string)\$remaining, \$array_result)) {
\$new_answer = (\$value <= \$remaining ? [\$value, \$remaining] : [\$remaining, \$value]);
}
}

echo '<pre>';
echo '</pre>';

Outputs:

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

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

)

点赞 打赏 评论