PHP实现的回溯算法示例

问题： 一头大牛驼2袋大米，一头中牛驼一袋大米，两头小牛驼一袋大米，请问100袋大米需要多少头大牛，多少头中牛，多少头小牛？

实现代码：

1. <?php 
2. /* 
3.  * k = 2x + y + 1/2z 
4.  取值范围 
5.  * 0 <= x <= 1/2k 
6.  * 0 <= y <= k 
7.  * 0 <= z < = 2k 
8.  * x,y,z最大值 2k 
9.  */ 
10. $daMi= 100; 
11. $result=array(); 
12. functionisOk($t,$daMi,$result) 
13. {/*{{{*/ 
14.  $total= 0; 
15.  $hash=array(); 
16.  $hash[1] = 2; 
17.  $hash[2] = 1; 
18.  $hash[3] = 0.5; 
19.  for($i=1;$i<=$t;$i++) 
20.  { 
21.  $total+=$result[$i] *$hash[$i]; 
22.  } 
23.  if($total<=$daMi) 
24.  { 
25.  returntrue; 
26.  } 
27.  returnfalse; 
28. }/*}}}*/ 
29. functionbacktrack($t,$daMi,$result) 
30. {/*{{{*/ 
31.  //递归出口 
32.  if($t> 3) 
33.  { 
34.  //输出最优解 
35.  if($daMi== (2 *$result[1] +$result[2] + 0.5 *$result[3])) 
36.  { 
37.   echo"最优解，大米:${daMi},大牛：$result[1],中牛： $result[2]，小牛：$result[3]/n"; 
38.  } 
39.  return; 
40.  } 
41.  for($i= 0;$i<= 2 *$daMi;$i++) 
42.  { 
43.  $result[$t] =$i; 
44.  //剪枝 
45.  if(isOk($t,$daMi,$result)) 
46.  { 
47.   backtrack($t+1,$daMi,$result); 
48.  } 
49.  $result[$t] = 0; 
50.  } 
51. }/*}}}*/ 
52. backtrack(1,$daMi,$result); 
53. ?>