当前位置:首页 > PHP教程 > php应用 > 列表

PHP实现的回溯算法示例

发布:smiling 来源: PHP粉丝网  添加日期:2018-08-31 10:18:25 浏览: 评论:0 

问题: 一头大牛驼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. ?>

Tags: 示例 算法

分享到: