Algorithme de backtracking PHP

Cet article présente principalement l'algorithme de backtracking implémenté en PHP. Il analyse les étapes de mise en œuvre et les méthodes d'utilisation de l'algorithme de backtracking PHP sous la forme d'exemples spécifiques, impliquant la récursivité, le parcours, l'opération et d'autres compétences opérationnelles connexes des chaînes et des tableaux. Amis qui en ont besoin Vous pouvez vous référer aux

détails comme suit :

Question :

2 sacs pour une grosse vache chamelle de riz, une vache chamelle de taille moyenne et un sac de riz, deux petites vaches chamelles et un sac de riz Combien de grosses vaches, combien de vaches moyennes et combien de petites vaches sont nécessaires. faire 100 sacs de riz ?

Code d'implémentation :

<?php
/*
 * k = 2x + y + 1/2z
 取值范围
 * 0 <= x <= 1/2k
 * 0 <= y <= k
 * 0 <= z < = 2k
 * x,y,z最大值 2k
 */
$daMi = 100;
$result = array();
function isOk($t,$daMi,$result)
{/*{{{*/
 $total = 0;
 $hash = array();
 $hash[1] = 2;
 $hash[2] = 1;
 $hash[3] = 0.5;
 for($i=1;$i<=$t;$i++)
 {
 $total += $result[$i] * $hash[$i];
 }
 if( $total <= $daMi)
 {
 return true;
 }
 return false;
}/*}}}*/
function backtrack($t,$daMi,$result)
{/*{{{*/
 //递归出口
 if($t > 3)
 {
 //输出最优解
 if($daMi == (2 * $result[1] + $result[2] + 0.5 * $result[3]))
 {
  echo "最优解，大米:${daMi},大牛：$result[1],中牛： $result[2]，小牛：$result[3]\n";
 }
 return;
 }
 for($i = 0;$i <= 2 * $daMi;$i++)
 {
 $result[$t] = $i;
 //剪枝
 if(isOk($t,$daMi,$result))
 {
  backtrack($t+1,$daMi,$result);
 }
 $result[$t] = 0;
 }
}/*}}}*/
backtrack(1,$daMi,$result);
?>

Résultats en cours Comme indiqué ci-dessous :

Recommandations associées :

PHPAlgorithme de retour en arrièrePartage d'exemples

Exemple de partage de algorithme de backtracking en php

phpalgorithme de backtracking Tutoriel Solving n Queens Problem_PHP

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!