PHP貪婪算法解決0-1背包問題實例分析
更新時間:2015年03月23日 11:19:47 作者:瘋狂一夏
這篇文章主要介紹了PHP貪婪算法解決0-1背包問題,實例分析了貪婪算法的原理與背包問題的實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了PHP貪婪算法解決0-1背包問題的方法。分享給大家供大家參考。具體分析如下:
貪心算法解決0-1背包問題,全局最優(yōu)解通過局部最優(yōu)解來獲得!比動態(tài)規(guī)劃解決背包問題更靈活!
//0-1背包貪心算法問題 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } } //生成數(shù)據(jù) $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背包最優(yōu)解為:'; echo tanxin($x);
希望本文所述對大家的php程序設計有所幫助。
相關文章
PHP實現(xiàn)的通過參數(shù)生成MYSQL語句類完整實例
這篇文章主要介紹了PHP實現(xiàn)的通過參數(shù)生成MYSQL語句類,結合完整實例形式分析了生成MYSQL語句類的實現(xiàn)與使用技巧,需要的朋友可以參考下2016-04-04PHP屏蔽蜘蛛訪問代碼及常用搜索引擎的HTTP_USER_AGENT
屏蔽蜘蛛相信每一位站長都不希望這樣做吧,因為蜘蛛的訪問就沒有用戶的瀏覽,直接會給我們帶來一定損失,不過也有例外,某些網(wǎng)站就不希望被蜘蛛爬行,接下來為你介紹屏蔽蜘蛛的php代碼2013-03-03php foreach 使用&(與運算符)引用賦值要注意的問題
foreach 通過在 $value 之前加上 & 很容易就能修改數(shù)組的單元,在 foreach 使用引用時要注意了。也可以在處理完后立即斷開引用關系,后面就不會有上述情況了。2010-02-02詳談symfony window下的安裝 安裝時候出現(xiàn)的問題以及解決方法
下面小編就為大家?guī)硪黄斦剆ymfony window下的安裝 安裝時候出現(xiàn)的問題以及解決方法。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-09-09PHP+Ajax實時自動檢測是否聯(lián)網(wǎng)的方法
這篇文章主要介紹了PHP+Ajax實時自動檢測是否聯(lián)網(wǎng)的方法,通過Ajax調用連接百度效果實現(xiàn)檢測網(wǎng)站是否聯(lián)網(wǎng)的功能,需要的朋友可以參考下2015-07-07