需要一个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){
1 2 3 | <code> $count = count ( $arr );
$array = array ();
for ( $i =0; $i </code>
|
Nach dem Login kopieren
}
$dd = ss($a,$arr);
ksort($dd);
print_r($dd);
打印,绝对值最小的,最靠近
Array
(
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | <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>
|
Nach dem Login kopieren
)
最先想到的肯定是暴力for循环算法,这个时间复杂度有点高,在n^2,少量数据可以实现的。
结果是 20 15 10 和明显小于38了啊,if判断就可以筛选掉,不可能一次性就给你选出最优,除非刚好。
算法的话可以划分到动态规划里面去,核心也是for循环,很类似。
这是经典背包问题,推荐阅读 背包问题九讲
利用了动态规划求解01背包问题的方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | <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>
|
Nach dem Login kopieren
求助,求助~update