Maison > développement back-end > tutoriel php > Algorithme de backtracking PHP

Algorithme de backtracking PHP

墨辰丷
Libérer: 2023-03-26 16:28:01
original
1695 Les gens l'ont consulté

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);
?>
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal