PHP实现的回溯算法示例
发布:smiling 来源: PHP粉丝网 添加日期:2018-08-31 10:18:25 浏览: 评论:0
问题: 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛?
实现代码:
- <?php
- /*
- * k = 2x + y + 1/2z
- 取值范围
- * 0 <= x <= 1/2k
- * 0 <= y <= k
- * 0 <= z < = 2k
- * x,y,z最大值 2k
- */
- $daMi= 100;
- $result=array();
- functionisOk($t,$daMi,$result)
- {/*{{{*/
- $total= 0;
- $hash=array();
- $hash[1] = 2;
- $hash[2] = 1;
- $hash[3] = 0.5;
- for($i=1;$i<=$t;$i++)
- {
- $total+=$result[$i] *$hash[$i];
- }
- if($total<=$daMi)
- {
- returntrue;
- }
- returnfalse;
- }/*}}}*/
- functionbacktrack($t,$daMi,$result)
- {/*{{{*/
- //递归出口
- if($t> 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);
- ?>
Tags: 示例 算法
- 上一篇:php简单中奖算法(实例)
- 下一篇:PHP实现无限极分类生成分类树的方法
相关文章
- ·php使用ajax示例(2013-12-09)
- ·PHP自动捕捉页面500错误示例(2014-01-19)
- ·PHP验证码实现代码简单示例(2014-08-22)
- ·php验证码程序代码(2014-08-22)
- ·一个完整php验证码实例程序(2014-08-25)
- ·PHP计算身份证校验码示例(2018-05-31)
- ·php利用云片网实现短信验证码功能的示例代码(2018-06-06)
- ·PHP基于双向链表与排序操作实现的会员排名功能示例(2018-06-06)
- ·原生JS实现Ajax通过GET方式与PHP进行交互操作示例(2018-06-11)
- ·php获取客户端IP及URL的方法示例(2018-07-26)
- ·php基于dom实现的图书xml格式数据示例(2018-07-26)
- ·PHP实现多级分类生成树的方法示例(2018-07-31)
- ·PHP基于DOM创建xml文档的方法示例(2018-07-31)
- ·PHP使用DOM和simplexml读取xml文档的方法示例(2018-07-31)
- ·php制作基于xml的RSS订阅源功能示例(2018-07-31)
- ·php实现文件与16进制相互转换的方法示例(2018-08-02)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)