当前位置:Gxlcms > PHP教程 > PHP贪婪算法解决0-1背包问题实例分析_PHP教程

PHP贪婪算法解决0-1背包问题实例分析_PHP教程

时间:2021-07-01 10:21:17 帮助过:8人阅读

PHP贪婪算法解决0-1背包问题实例分析


这篇文章主要介绍了PHP贪婪算法解决0-1背包问题,实例分析了贪婪算法的原理与背包问题的实现技巧,需要的朋友可以参考下

本文实例讲述了PHP贪婪算法解决0-1背包问题的方法。分享给大家供大家参考。具体分析如下:

贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活!

?

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

//0-1背包贪心算法问题

class tanxin{

public $weight;

public $price;

public function __construct($weight=0,$price=0)

{

$this->weight=$weight;

$this->price=$price;

}

}

//生成数据

$n=10;

for($i=1;$i<=$n;$i++){

$weight=rand(1,20);

$price=rand(1,10);

$x[$i]=new tanxin($weight,$price);

}

//输出结果

function display($x)

{

$len=count($x);

foreach($x as $val){

echo $val->weight,' ',$val->price;

echo '
';

}

}

//按照价格和重量比排序

function tsort(&$x)

{

$len=count($x);

for($i=1;$i<=$len;$i++)

{

for($j=1;$j<=$len-$i;$j++)

{

$temp=$x[$j];

$res=$x[$j+1]->price/$x[$j+1]->weight;

$temres=$temp->price/$temp->weight;

if($res>$temres){

$x[$j]=$x[$j+1];

$x[$j+1]=$temp;

}

}

}

}

//贪心算法

function tanxin($x,$totalweight=50)

{

$len=count($x);

$allprice=0;

for($i=1;$i<=$len;$i++){

if($x[$i]->weight>$totalweight) break;

else{

$allprice+=$x[$i]->price;

$totalweight=$totalweight-$x[$i]->weight;

}

}

if($i<$len) $allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);

return $allprice;

}

tsort($x);//按非递增次序排序

display($x);//显示

echo '0-1背包最优解为:';

echo tanxin($x);

希望本文所述对大家的php程序设计有所帮助。

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/973134.htmlTechArticlePHP贪婪算法解决0-1背包问题实例分析 这篇文章主要介绍了PHP贪婪算法解决0-1背包问题,实例分析了贪婪算法的原理与背包问题的实现技巧,需...

人气教程排行