Heim > Backend-Entwicklung > PHP-Tutorial > php获取数组中相加和最接近或等于(<=),要小等于给定值的算法

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

WBOY
Freigeben: 2016-06-06 20:20:49
Original
2562 Leute haben es durchsucht

需要一个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

Verwandte Etiketten:
php
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage