Example sharing of backtracking algorithm in php

One big cow camel has two bags of rice, one medium cow camel has one bag of rice, and two small cow camels have one bag of rice. How many big cows, how many medium cows, and how many calves are needed for 100 bags of rice?

<?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 above is the detailed content of Example sharing of backtracking algorithm in php. For more information, please follow other related articles on the PHP Chinese website!