PHP-Backtracking-Algorithmus

墨辰丷
Freigeben: 2023-03-26 16:28:01
Original
1691 Leute haben es durchsucht

In diesem Artikel wird hauptsächlich der in PHP implementierte Backtracking-Algorithmus vorgestellt und anhand spezifischer Beispiele die Implementierungsschritte und Verwendungsmethoden des PHP-Backtracking-Algorithmus analysiert, einschließlich Rekursion, Durchquerung, Operation und anderer verwandter Operationsfähigkeiten von Zeichenfolgen und Arrays. Freunde in Not Sie können die

Details wie folgt abrufen:

Frage:

2 Tüten für eine große Kamelkuh Reis, eine mittelgroße Kamelkuh und eine Tüte Reis, zwei kleine Kamelkuh und eine Tüte Reis Wie viele große Kühe, wie viele mittelgroße Kühe und wie viele kleine Kühe werden für die Herstellung benötigt? 100 Säcke Reis?

Implementierungscode:

<?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);
?>
Nach dem Login kopieren

Das laufende Ergebnis ist wie unten gezeigt:

Verwandte Empfehlungen:

PHPBacktracking-AlgorithmusBeispielfreigabe

Beispielfreigabe des Backtracking-Algorithmus in PHP

phpBacktracking-Algorithmus Solve n Queen Problem_PHP-Tutorial

Das obige ist der detaillierte Inhalt vonPHP-Backtracking-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage