PHP backtracking algorithm

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 You can refer to

for details as follows:

Question:

A big cow camel 2 bags Rice, one medium-sized cow camel and one bag of rice, two small cow camels and one bag of rice. How many big 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 result is as follows ：

PHPBacktracking algorithmExample sharing

##Backtracking algorithmExample sharing in php

phpBacktracking algorithmSolve n Queen Problem_PHP Tutorial

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