PHP实现的贪婪算法实例

站长资源 2024/11/26 佚名

2 0 1

本文实例讲述了PHP实现的贪婪算法。分享给大家供大家参考，具体如下：

背景介绍：贪婪算法与数据结构知识库算法可以说是离我们生活最近的一种算法，人总是贪婪的嘛，所以这种算法的设计是很符合人性的。之所以这么说，是因为人们会在生活中有意无意的使用贪婪算法来解决问题。最常见的就是找零钱了，每个人都没学过该怎么找零钱，但在所有面额的钱都充足时，每个人都会找出同样组合来凑够需要的钱。其实这里面就是贪婪算法在起作用。

设计思路：贪婪法的设计思路可以从两方面来理解，即直观上和数学上。从直观上理解贪婪算法就是用最快的方法来解决问题。在这里面“快”是主要目标，例如上面找零钱的例子，假如你要找的零钱为6.6元。那首先要拿一张5元的，因为这可以使你凑的钱增长最快。如果人民币有6元的面额那你肯定会选6元的而不是拿两张别的来凑6元；从数学上来理解贪婪算法就是在做判断时以当前最优解为目标，类似于最优化中的最速下降法。这种方法的好处是解题速度极快，基本上是一次历遍就可以完成。

算法缺陷：正如做人不能太贪婪一样，贪婪算法本身有着致命的缺陷，这使得其应用背景收到了很多限制。因为算法是取的局部最优解，没有考虑以后的问题。这就像一个自私自利的人一样，虽然短时间内可以获得一些利益，但长期以往，很难会有大的成就。当然，社会很复杂，也许会有人一直自私下去而生活的还不错。这体现在算法上就是在一些情况下（具体下面会提到），贪婪算法是可以得到最优解的，这对于算法设计来说当然是好事。

/*
* 贪婪算法
* $arr   array  处理数组
* $volume  int   盒子容量
*/
function greedy($arr, $volume){
    $box = array();
    $boxNum = 0;
    $num = count( $arr );
    for ($i = 0; $i < $num; $i++) {
      $boxCode = true;
      for ($j = 0; $j < $boxNum; $j++) {
        if ($arr[$i] + $box[$j]['v'] <= $volume) {
          $box[$j]['v'] += $arr[$i];
          $box[$j]['k'][] = $i;
          $boxCode = false;
          break;
        }
      }
      if ($boxCode) {
        $box[$boxNum]['v'] = $arr[$i];
        $box[$boxNum]['k'][] = $i;
        $boxNum++;
      }
    }
    return $box;
}

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《php程序设计算法总结》

希望本文所述对大家PHP程序设计有所帮助。

PHP,贪婪算法

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

评论“PHP实现的贪婪算法实例”

暂无评论...

www.wwsws.com 伏龙阁资源网

39,976影音资源

44,792技术资源

21,817软件资源

651,128站长资源

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

更新日志

2024年11月26日

PHP实现的贪婪算法实例

php 数据结构之链表队列

PHP 7.1中AES加解密方法mcrypt_module_open()的替换方案

评论“PHP实现的贪婪算法实例”

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

更新日志

友情链接