PHP贪婪算法解决0-1背包问题实例分析_PHP教程
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程序设计有所帮助。
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
相关文章
相关视频
专题推荐
-
独孤九贱-php全栈开发教程
全栈 170W+
主讲:Peter-Zhu 轻松幽默、简短易学,非常适合PHP学习入门
-
玉女心经-web前端开发教程
入门 80W+
主讲:灭绝师太 由浅入深、明快简洁,非常适合前端学习入门
-
天龙八部-实战开发教程
实战 120W+
主讲:西门大官人 思路清晰、严谨规范,适合有一定web编程基础学习
上一篇: php中curl使用指南
下一篇: 基于二维拓扑数的可达性查询
网友评论
文明上网理性发言,请遵守 新闻评论服务协议
我要评论