PHP实现的回溯算法示例

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

问题：

一头大牛驼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();
function isOk($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)
 {
 return true;
 }
 return false;
}/*}}}*/
function backtrack($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);
?>

运行结果如下图：

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

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

赞 (0)

相关推荐

  • php实现猴子选大王问题算法实例

    本文实例讲述了php实现猴子选大王问题算法.分享给大家供大家参考.具体分析如下: 一.问题: n只猴子围坐成一个圈,按顺时针方向从1到n编号. 然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数, 如此重复,直至剩下一个猴子,它就是大王. 设计并编写程序,实现如下功能: (1)   要求由用户输入开始时的猴子数$n.报数的最后一个数$m. (2)   给出当选猴王的初始编号. 二.解决方法: /** * @param int $n 开始时的猴子数

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • PHP使用栈解决约瑟夫环问题算法示例

    本文实例讲述了PHP使用栈解决约瑟夫环问题算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php cla

  • php约瑟夫问题解决关于处死犯人的算法

    本文实例讲述了php约瑟夫问题解决关于处死犯人的算法.分享给大家供大家参考.具体分析如下: 古代某法官要判决IV个犯人的死刑,他有一条荒唐的法律将犯人站成一个圆圈,从第s个人开始数起,每到第D个人就拉出来处死,然后再数D个,再拉出来处决-- 直到剩下最后一个可以赦免. function getNum($n,$m){ //用于把所有的数存到数组初始化 $a = array(); //遍历,存入数组 for($i=1;$i<=$n;$i++){ $a[$i] = $i; } //指针归0 reset

  • PHP回溯法解决0-1背包问题实例分析

    本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna

  • PHP 正则表达式效率 贪婪、非贪婪与回溯分析(推荐)

    先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪 看起来,好像没什么问题,其实则不然.若 $str = '<script<script>alert(document.cookie)</script&

  • PHP贪婪算法解决0-1背包问题实例分析

    本文实例讲述了PHP贪婪算法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活! //0-1背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } }

  • PHP正则表达式的效率 回溯与固化分组

    先来看下问题. 字符串 复制代码 代码如下: $str = '<script>123456</script>'; 正则表达式为 复制代码 代码如下: $strRegex1 = '%<script>.+<\/script>%'; $strRegex2 = '%<script>.+?<\/script>%'; $strRegex3 = '%<script>(?:(?!<\/script>).)+<\/scri

  • PHP实现基于回溯法求解迷宫问题的方法详解

    本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.

  • java 实现迷宫回溯算法示例详解

    用一个7 x 7的矩形表示迷宫,0和1分别表示的是通路和障碍.通过设计编写程序找到蓝色小球达到蓝色旗子的路线 思路: 构建一个迷宫(用二维数组)实现找通路的方法findRoad() 构建二维数组不难,我们主要是要实现findRoad()这个方法,在实现这个方法前,我们需要约定好一下几个点:小球的位置当作入口(1,1),小旗的位置当作出口(5,5)数组里数的含义分别为(0没有走过).(1障碍).(2走过且为正确的路线).(3走过且为错误的路线)将我们每一步的走法称为策略:下 -> 右 -> 上

  • PHP实现的回溯算法示例

    PHP实现的回溯算法示例

    本文实例讲述了PHP实现的回溯算法.分享给大家供大家参考,具体如下: 问题: 一头大牛驼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();

  • 教你怎么用Java回溯算法解数独

    教你怎么用Java回溯算法解数独

    一.题干 输入一个9*9二维数组表示数独,已经填入的数字用1-9表示,待填入的数字用0表示,试写一个算法解出数独并输出. 二.思路 容易想到回溯法,即以人的思维的解数独,遍历数组,如果是空白就从1-9依次选一个数判断本行.列.3*3宫格内是否有重复,如果有就进行下一个数字的选择:如果该数暂时满足条件,那么进行下一个格子的选择,递归的终止条件是遍历完所有格子. 三.代码分段演示 输入数组 Scanner sc = new Scanner(System.in); int[][] board = ne

  • python回溯算法实现全排列小练习分享

    python回溯算法实现全排列小练习分享

    问题:输入列表L(不含重复元素),输出L的全排列. 如输入:L=[1,2,3] 则输出:[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 全排列问题,可以用回溯法解决,详细分析请参考东哥公众号:labuladong,看了之后醍醐灌顶. 先帖一个正确解法: ''' 回溯算法模板: from: labuladong公众号 result = [] def backtrack(选择列表,路径):     if 满足结束条

  • C++回溯算法深度优先搜索举例分析

    C++回溯算法深度优先搜索举例分析

    目录 扑克牌全排列 员工的重要性 图像渲染 被围绕的区域 岛屿数量 电话号码的字母组合 组合总数 活字印书 N皇后 扑克牌全排列 假如有编号为1~ 3的3张扑克牌和编号为1~3的3个盒子,现在需要将3张牌分别放到3个盒子中去,且每个盒子只能放一张牌,一共有多少种不同的放法. 解题思路:假定按照牌面值从小到大依次尝试,即将1号牌放入第一个盒子中.按此顺序继续向后走,放完第三个盒子时,手中的牌也已经用完,再继续往后则到了盒子的尽头.此时一种放法已经完成了,即这条路走到了尽头,需要折返,重新回到上一个

  • C++回溯算法广度优先搜索举例分析

    C++回溯算法广度优先搜索举例分析

    目录 迷宫问题 N叉树的层序遍历 腐烂的橘子 单词接龙 打开转盘锁 迷宫问题 假设有一个迷宫,里面有障碍物,迷宫用二维矩阵表示,标记为0的地方表示可以通过,标记为1的地方表示障碍物,不能通过.现在给一个迷宫出口,让你判断是否可以从入口进来之后,走出迷宫,每次可以向任意方向走. 代码实现: namespace BFS { struct pair { int _x; int _y; pair(int x, int y) :_x(x) , _y(y) {} }; bool mapBFS(vector<

  • VC实现五子棋游戏的一个算法示例

    VC实现五子棋游戏的一个算法示例

    本文讲述了VC实现五子棋游戏的一个算法示例,该算法采用极大极小剪枝博弈算法,感兴趣的读者可以对程序中不完善的部分进行修改与完善. 该设计主要包括:数据结构.估值函数.胜负判断.搜索算法 程序运行界面如下: 具体实现步骤如下: 1.数据结构 //记录每步棋,可以建立链表用来进行悔棋.后退(本程序没有实现) struct Step { int x,y; //棋子坐标 int ball; //表示下子方{BLACK,WHITE} }; //记录棋盘情况,用于搜索过程 class CBoardSitua

  • Java实现的RSA加密解密算法示例

    本文实例讲述了Java实现的RSA加密解密算法.分享给大家供大家参考,具体如下: import java.awt.AlphaComposite; import java.awt.Color; import java.awt.Font; import java.awt.Graphics2D; import java.awt.Image; import java.awt.RenderingHints; import java.awt.image.BufferedImage; import java.

  • Python编程实现的简单神经网络算法示例

    Python编程实现的简单神经网络算法示例

    本文实例讲述了Python编程实现的简单神经网络算法.分享给大家供大家参考,具体如下: python实现二层神经网络 包括输入层和输出层 # -*- coding:utf-8 -*- #! python2 import numpy as np #sigmoid function def nonlin(x, deriv = False): if(deriv == True): return x*(1-x) return 1/(1+np.exp(-x)) #input dataset x = np.

随机推荐