php获取数组中相加和最接近或等于(<=),要小等于给定值的算法
程序员文章站
2022-03-26 17:25:29
...
需要一个php算法,选出一串数组中的数字组合相加和要最接近(
例如 :上限值:38 给定数组值 15,20,10, 6
正确结果选定:20 10 6
这个要如何实现?求具体实现方式
之前是按从大到小排序,再相加,发现选出 20 15 10,但是其实最优的是20 10 6,求帮助。。。
回复内容:
需要一个php算法,选出一串数组中的数字组合相加和要最接近(
例如 :上限值:38 给定数组值 15,20,10, 6
正确结果选定:20 10 6
这个要如何实现?求具体实现方式
之前是按从大到小排序,再相加,发现选出 20 15 10,但是其实最优的是20 10 6,求帮助。。。
$a = 38;
$arr = array(15,20,10,6);
function ss($a,$arr){
$count = count($arr);
$array = array();
for($i=0;$i
}
$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
)
)
)
最先想到的肯定是暴力for循环算法,这个时间复杂度有点高,在n^2,少量数据可以实现的。
结果是 20 15 10 和明显小于38了啊,if判断就可以筛选掉,不可能一次性就给你选出最优,除非刚好。
算法的话可以划分到动态规划里面去,核心也是for循环,很类似。
这是经典背包问题,推荐阅读 背包问题九讲
利用了动态规划求解01背包问题的方法
$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];
}
}
求助,求助~update