www.adminn.cn
站长正能量分享网!

PHP实现的回溯算法示例

AD:阿里云服务器企业会员更优惠 腾讯云香港,韩国免备案服务器1.8折优惠

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

模板优惠价: (点击购买)
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《PHP实现的回溯算法示例》
文章链接:https://www.adminn.cn/news/7554.html
本站资源模板仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。2021.5月起,网站调整,暂不再分享免费模板。谢谢理解

Adminn.Cn 站长分享圈

帝国CMS精品模板腾讯云优惠券,代金券

2次开发,学习研究使用!扫码支付后联系QQ677123发货!

支付宝扫一扫打赏