Teilen von Beispielen für den PHP-Backtracking-Algorithmus

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 können sich an Next wenden, ich hoffe, es kann allen helfen.

Frage:

Eine große Kamelkuh hat 2 Beutel Reis, eine mittelgroße Kamelkuh hat einen Beutel Reis und Zwei kleine Kuhkamele haben einen Sack Reis. Wie viele große Kühe, wie viele mittelgroße Kühe und wie viele kleine Kühe werden benötigt, um 100 Säcke Reis herzustellen?

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);
?>

Das laufende Ergebnis ist wie folgt folgt:

Verwandte Empfehlungen:

PHP-Backtracking-Algorithmus zur Lösung des N-Queens-Problems_PHP-Tutorial

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