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

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

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

算法缺陷：正如做人不能太貪婪一樣，貪婪算法本身有著致命的缺陷，這使得其應用背景收到了很多限制。因為算法是取的局部最優(yōu)解，沒有考慮以后的問題。這就像一個自私自利的人一樣，雖然短時間內(nèi)可以獲得一些利益，但長期以往，很難會有大的成就。當然，社會很復雜，也許會有人一直自私下去而生活的還不錯。這體現(xiàn)在算法上就是在一些情況下（具體下面會提到），貪婪算法是可以得到最優(yōu)解的，這對于算法設(shè)計來說當然是好事。

/*
* 貪婪算法
* $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;
}

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《PHP基本語法入門教程》、《php面向?qū)ο蟪绦蛟O(shè)計入門教程》、《php字符串(string)用法總結(jié)》及《php程序設(shè)計算法總結(jié)》

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