這篇文章主要介紹了PHP貪婪演算法解決0-1背包問題,實例分析了貪婪演算法的原理與背包問題的實現技巧,需要的朋友可以參考下
本文實例講述了PHP貪婪演算法解決0-1背包問題的方法。分享給大家供大家參考。具體分析如下:
貪婪演算法解決0-1背包問題,全局最優解透過局部最優解來獲得!比動態規劃解決背包問題更有彈性!
//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 '<br>'; } } //按照价格和重量比排序 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貪婪演算法的原理及用法的詳細內容。更多資訊請關注PHP中文網其他相關文章!