php获取数组中相加和最接近或等于(<=)，要小等于给定值的算法-php教程-PHP中文网

php获取数组中相加和最接近或等于(<=)，要小等于给定值的算法

WBOY

发布： 2016-06-06 20:20:49

原创

2556 人浏览过

需要一个php算法，选出一串数组中的数字组合相加和要最接近(

例如：上限值：38 给定数组值 15，20，10， 6
正确结果选定：20 10 6
这个要如何实现？求具体实现方式
之前是按从大到小排序，再相加，发现选出 20 15 10，但是其实最优的是20 10 6，求帮助。。。

回复内容：

需要一个php算法，选出一串数组中的数字组合相加和要最接近(

$a = 38;
$arr = array(15,20,10,6);
function ss($a,$arr){

<code>$count = count($arr);
$array = array();
for($i=0;$i</code>

登录后复制

}
$dd = ss($a,$arr);
ksort($dd);
print_r($dd);

打印，绝对值最小的，最靠近

Array
(

<code>[2] => Array
    (
        [0] => Array
            (
                [1] => 20
                [2] => 10
                [3] => 6
            )

    )

[3] => Array
    (
        [0] => Array
            (
                [3] => 6
                [4] => 15
                [5] => 20
            )

    )

[7] => Array
    (
        [0] => Array
            (
                [2] => 10
                [3] => 6
                [4] => 15
            )

        [1] => Array
            (
                [4] => 15
                [5] => 20
                [6] => 10
            )

    )
</code>

登录后复制

)

最先想到的肯定是暴力for循环算法，这个时间复杂度有点高，在n^2，少量数据可以实现的。

结果是 20 15 10 和明显小于38了啊，if判断就可以筛选掉，不可能一次性就给你选出最优，除非刚好。

算法的话可以划分到动态规划里面去，核心也是for循环，很类似。

这是经典背包问题，推荐阅读背包问题九讲

利用了动态规划求解01背包问题的方法

<code>
$maxSize = 38;
$arr = array(15, 20, 10, 6);
$result = array();
$answers = array();
$currSize = 36;
$len = count($arr);
for ($i = 0; $i  $i) {
            if ($j === 0) $result[$j][$i] = 0;
            else $result[$j][$i] = $result[$j - 1][$i];
        } else {
            if ($j === 0) $result[$j][$i] = $arr[$j];
            else $result[$j][$i] = max($result[$j - 1][$i], $result[$j - 1][$i - $arr[$j]] + $arr[$j]);
        }
    }
}
// 找出答案
for ($i = $len - 1; $i >= 0 && $currSize !== 0; $i--) {
    if ($result[$i][$currSize] - $result[$i - 1][$currSize - $arr[$i]] === $arr[$i]) {
        $answers[] = $arr[$i];
        $currSize -= $arr[$i];
    }
}
</code>

登录后复制

求助，求助~update