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

Question

需要一个php算法，选出一串数组中的数字组合相加和要最接近(<=)给定值的算法。

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

Answer 1

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

$count = count($arr);
$array = array();
for($i=0;$i<$count;$i++){
    $r = $arr[$i];
    unset($arr[$i]);
    $sum = abs(array_sum($arr) - $a);
    $array[$sum][] = $arr;
    $arr[] = $r;
}
return $array;

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

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

Array
(

[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
            )

    )

)

Answer 2

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

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

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

Answer 3

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

Answer 4

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

$maxSize = 38;
$arr = array(15, 20, 10, 6);
$result = array();
$answers = array();
$currSize = 36;
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
    $result[] = array();
    for ($j = 0; $j <= $maxSize; $j++) {
        $result[$i][$j] = 0;
    }
}
for ($i = 0; $i <= $maxSize; $i++) {
    for ($j = 0; $j < $len; $j++) {
        if ($arr[$j] > $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];
    }
}

Answer 5

今天一个朋友问了我这个问题，研究了一下，代码如下，应该能符合题主的要求，虽然时间已经过去很久了。

// 目标数组
$arr = [15, 20, 10, 6];
// 限定最大值
$max = 38;
// 执行
$re = digui($arr, $max);
// 执行结果
print_r('当限定结果最大值为 ' . $max . ' 时，最优解为' . implode('+', $re[1]) . '=' . $re[0]);

// 程序主体
function digui($arr, $max = null, $re = [], $i = 0, $bak = []) {
    empty($bak) && $bak = $arr;
    if (count($arr) == 0) {
        // 递归结束,返回解析结果集
        if (empty($re)) {
            return [0, []];
        }
        krsort($re);
        foreach ($re as $k1 => $v1) {
            // 将序列转换为数字
            foreach ($v1 as $k2 => $v2) {
                $v1[$k2] = $bak[$v2];
            }
            // 最终返回结果
            return [$k1, $v1];
        }
    }

    // 取出当前第一个数
    $x = array_shift($arr);

    // 单元素
    if (!isset($re[$x])) {
        if ($x > $max) {
            $i++;
            return digui($arr, $max, $re, $i, $bak);
        }
        if ($x == $max) {
            $re = [$x => [$x]];
            return digui([], $max, $re, $i, $bak);
        }
        $re[$x] = [$i];
    }

    // 双元素相加
    for ($b = 0; $b < count($arr); $b++) {
        $result = $x + $arr[$b];
        if (!isset($re[$result])) {
            if ($result < $max) {
                $re[$result] = [$i, $i + $b + 1];
            }
            if ($result == $max) {
                $re = [$result => [$i, $i + $b + 1]];
                return digui([], $max, $re, $i, $bak);
            }
        }
    }

    // 多元素相加
    foreach ($re as $k => $v) {
        if (count($v) > 1 && !in_array($i, $v)) {
            $result = $k + $x;
            if (!isset($re[$result])) {
                array_push($v, $i);
                if ($result < $max) {
                    $re[$result] = $v;
                }
                if ($result == $max) {
                    $re = [$result => $v];
                    return digui([], $max, $re, $i, $bak);
                }
            }
        }
    }

    $i++;
    return digui($arr, $max, $re, $i, $bak);
}

Answer 6

求助，求助~update

Answer 7

楼主，弄出来了吗？