dongxinm279890 2018-07-13 00:20
浏览 40
已采纳

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

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 03: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
    

    展开全部

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)
编辑
预览

报告相同问题?

手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部