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 '<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程序設計有所幫助。