Exemple d'implémentation d'un algorithme gourmand PHP

Cet article présente principalement l'algorithme glouton implémenté en PHP, explique brièvement le concept et le principe de l'algorithme glouton et analyse les compétences opérationnelles pertinentes de l'algorithme glouton implémenté en PHP sous forme d'exemples auxquels les amis dans le besoin peuvent se référer. it

Les exemples de cet article décrivent l'algorithme glouton implémenté en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Introduction au contexte : L'algorithme gourmand et l'algorithme de base de connaissances sur la structure des données peuvent être considérés comme l'algorithme le plus proche de nos vies. sont toujours gourmands. Eh bien, la conception de cet algorithme est très cohérente avec la nature humaine. La raison pour laquelle je dis cela est que les gens utiliseront des algorithmes gourmands pour résoudre des problèmes, intentionnellement ou non, dans leur vie. La chose la plus courante est de faire du changement. Tout le monde n’a jamais appris à faire du changement, mais lorsqu’il y a suffisamment d’argent dans toutes les confessions, tout le monde trouvera la même combinaison pour obtenir l’argent dont il a besoin. En fait, l’algorithme glouton est à l’œuvre ici.

Idée de conception : L'idée de conception de la méthode gloutonne peut être comprise sous deux aspects, à savoir intuitivement et mathématiquement. Comprendre intuitivement l’algorithme glouton consiste à utiliser la méthode la plus rapide pour résoudre le problème. Ici, "rapidement" est l'objectif principal. Par exemple, dans l'exemple ci-dessus de changement d'argent, si la monnaie que vous souhaitez changer est de 6,6 yuans. Alors procurez-vous d'abord un billet de 5 yuans, car cela peut faire croître l'argent que vous collectez le plus rapidement. Si le RMB a une valeur nominale de 6 yuans, vous choisirez certainement les 6 yuans au lieu d'en utiliser deux autres pour composer 6 yuans ; comprendre mathématiquement que l'algorithme glouton consiste à cibler la solution optimale actuelle lors de la prise de jugement, similaire à l'optimisation de la méthode de descente la plus raide. dans . L’avantage de cette méthode est qu’elle est extrêmement rapide pour résoudre le problème et qu’elle peut être réalisée en une seule passe.

Défauts de l'algorithme : Tout comme une personne ne peut pas être trop gourmande, l'algorithme gourmand lui-même présente des défauts fatals, ce qui impose de nombreuses restrictions sur son fond d'application. Parce que l’algorithme prend la solution optimale locale, il ne prend pas en compte les problèmes futurs. C'est comme une personne égoïste. Bien qu'il puisse obtenir certains avantages en peu de temps, il lui est difficile d'obtenir de grandes réalisations à long terme. Bien sûr, la société est très complexe et il peut y avoir des gens qui continuent à être égoïstes et à mener une vie plutôt agréable. Cela se reflète dans l'algorithme qui, dans certains cas (mentionnés ci-dessous), l'algorithme glouton peut obtenir la solution optimale, ce qui est bien sûr une bonne chose pour la conception d'algorithmes.

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!