PHP实现的回溯算法示例

作者:袖梨 2022-06-24

问题:

 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛?

实现代码:

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

运行结果如下图:

相关文章

精彩推荐