欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

程序员文章站 2024-02-11 11:06:40
...

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

$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

{

for($j=1;$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

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

else{

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

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

}

}

if($iprice*($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背包问题,实例分析了贪婪算法的原理与背包问题的实现技巧,需...
PHP贪婪算法解决0-1背包问题实例分析_PHP教程

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频


网友评论

文明上网理性发言,请遵守 新闻评论服务协议

我要评论
  • PHP贪婪算法解决0-1背包问题实例分析_PHP教程
  • 专题推荐