PHP實(shí)現(xiàn)的貪婪算法實(shí)例

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

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

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

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

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

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