php貪婪演算法的實作實例

這篇文章主要介紹了PHP實現的貪婪演算法,簡單說明了貪婪演算法的概念、原理並結合實例形式分析了php實現貪婪演算法的相關操作技巧,需要的朋友可以參考下

本文實例敘述了PHP實作的貪婪演算法。分享給大家供大家參考，具體如下：

背景介紹：貪婪演算法與資料結構知識庫演算法可以說是離我們生活最近的演算法，人總是貪婪的嘛，所以這種演算法的設計是很符合人性的。之所以這麼說，是因為人們會在生活中有意無意的使用貪婪演算法來解決問題。最常見的就是找零錢了，每個人都沒學過該怎麼找零錢，但在所有面額的錢都充足時，每個人都會找出同樣組合來湊夠需要的錢。其實這裡面就是貪婪演算法在運作。

設計想法：貪婪法的設計想法可以從兩個方面來理解，即直觀和數學。從直覺上理解貪婪演算法就是用最快的方法來解決問題。這裡「快」是主要目標，例如上面找零錢的例子，假如你要找的零錢是6.6元。那首先要拿一張5元的，因為這可以讓你湊的錢成長最快。如果人民幣有6元的面額那你一定會選6元的而不是拿兩張別的來湊6元；從數學上來理解貪婪算法就是在做判斷時以當前最優解為目標，類似於最優化中的最速下降法。這種方法的好處是解題速度極快，基本上就是一次歷遍就可以完成。

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

/*
* 贪婪算法
* $arr   array  处理数组
* $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][&#39;v&#39;] <= $volume) {
          $box[$j][&#39;v&#39;] += $arr[$i];
          $box[$j][&#39;k&#39;][] = $i;
          $boxCode = false;
          break;
        }
      }
      if ($boxCode) {
        $box[$boxNum][&#39;v&#39;] = $arr[$i];
        $box[$boxNum][&#39;k&#39;][] = $i;
        $boxNum++;
      }
    }
    return $box;
}

以上是php貪婪演算法的實作實例的詳細內容。更多資訊請關注PHP中文網其他相關文章！