本文實(shí)例講述了PHP實(shí)現(xiàn)的貪婪算法。分享給大家供大家參考，具體如下：

背景介紹：貪婪算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)庫(kù)算法可以說(shuō)是離我們生活最近的一種算法，人總是貪婪的嘛，所以這種算法的設(shè)計(jì)是很符合人性的。之所以這么說(shuō)，是因?yàn)槿藗儠?huì)在生活中有意無(wú)意的使用貪婪算法來(lái)解決問(wèn)題。最常見(jiàn)的就是找零錢了，每個(gè)人都沒(méi)學(xué)過(guò)該怎么找零錢，但在所有面額的錢都充足時(shí)，每個(gè)人都會(huì)找出同樣組合來(lái)湊夠需要的錢。其實(shí)這里面就是貪婪算法在起作用。

設(shè)計(jì)思路：貪婪法的設(shè)計(jì)思路可以從兩方面來(lái)理解，即直觀上和數(shù)學(xué)上。從直觀上理解貪婪算法就是用最快的方法來(lái)解決問(wèn)題。在這里面“快”是主要目標(biāo)，例如上面找零錢的例子，假如你要找的零錢為6.6元。那首先要拿一張5元的，因?yàn)檫@可以使你湊的錢增長(zhǎng)最快。如果人民幣有6元的面額那你肯定會(huì)選6元的而不是拿兩張別的來(lái)湊6元；從數(shù)學(xué)上來(lái)理解貪婪算法就是在做判斷時(shí)以當(dāng)前最優(yōu)解為目標(biāo)，類似于最優(yōu)化中的最速下降法。這種方法的好處是解題速度極快，基本上是一次歷遍就可以完成。

算法缺陷：正如做人不能太貪婪一樣，貪婪算法本身有著致命的缺陷，這使得其應(yīng)用背景收到了很多限制。因?yàn)樗惴ㄊ侨〉木植孔顑?yōu)解，沒(méi)有考慮以后的問(wèn)題。這就像一個(gè)自私自利的人一樣，雖然短時(shí)間內(nèi)可以獲得一些利益，但長(zhǎng)期以往，很難會(huì)有大的成就。當(dāng)然，社會(huì)很復(fù)雜，也許會(huì)有人一直自私下去而生活的還不錯(cuò)。這體現(xiàn)在算法上就是在一些情況下（具體下面會(huì)提到），貪婪算法是可以得到最優(yōu)解的，這對(duì)于算法設(shè)計(jì)來(lái)說(shuō)當(dāng)然是好事。

/** 貪婪算法* $arr   array  處理數(shù)組* $volume  int   盒子容量*/function greedy($arr, $volume){    $box = array();    $boxNum = 0;    $num = count( $arr );    for ($i = 0; $i < $num; $i++) {      $boxCode = true;      for ($j = 0; $j < $boxNum; $j++) {        if ($arr[$i] + $box[$j]['v'] <= $volume) {          $box[$j]['v'] += $arr[$i];          $box[$j]['k'][] = $i;          $boxCode = false;          break;        }      }      if ($boxCode) {        $box[$boxNum]['v'] = $arr[$i];        $box[$boxNum]['k'][] = $i;        $boxNum++;      }    }    return $box;}

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。