PHP backtracking algorithm example sharing

This article mainly introduces the backtracking algorithm implemented in PHP, and analyzes the implementation steps and usage methods of the PHP backtracking algorithm in the form of specific examples, involving recursion, traversal, operation and other related operation skills of strings and arrays. Friends in need can refer to Next, I hope it can help everyone.

Question:

One big cow camel has 2 bags of rice, one medium cow camel has one bag of rice, and two small cow camels have one bag of rice Bags of rice. How many large cows, how many medium cows, and how many small cows are needed to make 100 bags of rice?

Implementation code:

##

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

The running results are as follows:

Related recommendations:

php backtracking algorithm to solve the n-queens problem_PHP tutorial

##

The above is the detailed content of PHP backtracking algorithm example sharing. For more information, please follow other related articles on the PHP Chinese website!