本文实例讲述了PHP实现的回溯算法。分享给大家供大家参考,具体如下:
问题:
一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少/
/头中牛,多少头小牛?
实现代码:
<?php
/*
$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);
?>
运行结果如下图:
希望本文所述对大家PHP程序设计有所帮助。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。