Partage d'exemples d'algorithme de backtracking PHP

Cet article présente principalement l'algorithme de backtracking implémenté en PHP et 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 de chaînes et de tableaux. Les amis dans le besoin peuvent se référer à Next, j'espère que cela pourra aider tout le monde.

Question :

Une grosse chamelle a 2 sacs de riz, une chamelle de taille moyenne a un sac de riz, et deux petites vaches chameaux ont un sac de riz Sacs de riz Combien de grosses vaches, combien de vaches moyennes et combien de petites vaches sont nécessaires pour fabriquer 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);
?>

Le résultat en cours d'exécution est le suivant suit :

Recommandations associées :

algorithme de backtracking php pour résoudre le problème des n-queens_Tutoriel 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!