Example of greedy algorithm implemented by PHP

This article describes the greedy algorithm implemented by PHP. Share it for your reference, as follows:

Background introduction:Greedy algorithms and data structure knowledge base algorithms can be said to be the closest algorithm to our lives. People are always greedy, so the design of this algorithm is very in line with human nature. The reason for saying this is because people will use greed algorithms intentionally or unintentionally in their lives to solve problems. The most common thing is to find change. Everyone has never learned how to find change, but when all the denominations are sufficient, everyone will find the same combination to make up the money they need. In fact, the greedy algorithm is working.

Design ideas:The design idea of ​​the greedy method can be understood from two aspects, namely intuitively and mathematically. Intuitively understanding the greedy algorithm is to solve the problem with the fastest method. "Fast" is the main goal here. For example, the above example of finding change is 6.6 yuan. First of all, you have to get a 5 yuan bill, because this can increase the money you raise the fastest. If the RMB has a denomination of 6 yuan, you will definitely choose 6 yuan instead of using two other ones to make up 6 yuan; from a mathematical perspective, understanding the greedy algorithm is to target the current optimal solution when making judgments, similar to the fastest descent method in optimization. The advantage of this method is that it solves the problem very quickly and can basically be completed by just one surfing.

Algorithm defects:Just as people cannot be too greedy, the greedy algorithm itself has fatal flaws, which has caused many limitations in its application background. Because the algorithm takes the local optimal solution, no future problems are considered. This is like a selfish person. Although you can gain some benefits in a short period of time, it is difficult to achieve great success in the long run. Of course, society is very complicated, and maybe someone will live a good life all the time. This is reflected in the algorithm. In some cases (mentioned below) greedy algorithms can get the optimal solution, which is of course a good thing for algorithm design.

/*
 * Greedy Algorithm
 * $arr array Processing array
 * $volume int box capacity
 */
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;
}

For more information about PHP related content, please check out the topic of this site:PHP data structure and algorithm tutorial》、《Introduction to PHP basic syntax》、《PHP object-oriented programming tutorial》、《Summary of usage of php strings"and"Summary of PHP Programming Algorithm》

I hope this article will be helpful to everyone's PHP programming.