Implementation example of PHP greedy algorithm

This article mainly introduces the greedy algorithm implemented in PHP, briefly explains the concept and principle of the greedy algorithm, and analyzes the relevant operating skills of the greedy algorithm implemented in PHP in the form of examples. Friends who need it can refer to it

The example in this article describes the greedy algorithm implemented in PHP. Share it with everyone for your reference. The details are as follows:

Background introduction: Greedy algorithm and data structure knowledge base algorithm can be said to be an algorithm closest to our lives. People are always greedy. Well, so the design of this algorithm is very consistent with human nature. The reason why I say this is because people will use greedy algorithms to solve problems intentionally or unintentionally in their lives. The most common thing is to make change. Everyone has never learned how to make change, but when there is enough money in all denominations, everyone will find the same combination to get the money they need. In fact, the greedy algorithm is at work here.

Design idea: The design idea of ​​the greedy method can be understood from two aspects, namely intuitively and mathematically. Intuitively understanding the greedy algorithm is to use the fastest method to solve the problem. Here "fast" is the main goal. For example, in the above example of changing money, if the change you want to change is 6.6 yuan. Then first get a 5 yuan ticket, because this can make the money you collect grow the fastest. If the RMB has a denomination of 6 yuan, you will definitely choose the 6 yuan instead of using two other pieces to make up 6 yuan; mathematically understanding the greedy algorithm is to target the current optimal solution when making judgments, which is similar to optimization Steepest descent method in . The advantage of this method is that the problem solving speed is extremely fast, and it can basically be completed in one pass.

Algorithm defects: Just as a person cannot be too greedy, the greedy algorithm itself has fatal flaws, which places many restrictions on its application background. Because the algorithm takes the local optimal solution, it does not consider future problems. This is like a selfish person. Although he can get some benefits in a short time, it is difficult for him to achieve great achievements in the long run. Of course, society is very complex, and there may be people who continue to be selfish and live a pretty good life. This is reflected in the algorithm that in some cases (mentioned below), the greedy algorithm can obtain the optimal solution, which is of course a good thing for algorithm design.

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

The above is the detailed content of Implementation example of PHP greedy algorithm. For more information, please follow other related articles on the PHP Chinese website!