當前位置:首頁 > 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: 示例 算法

分享到:

广西快3最大遗漏值统计表