方法一：动态规划
<?php
echo "过桥问题--动态规划\n";
fwrite(STDOUT,'请输入每个过桥人（人数>=2）的时间，用空格隔开：');
$a=fgets(STDIN);
$speed=array_map(function ($v){ return intval($v);}, array_filter(explode(' ',$a)));
$status=['left'=>array_keys($speed),'right'=>[],'candle'=>'left','sumTime'=>0,'path'=>'0','comment'=>'开始'];
$end=[];
$i=0;
$result=[];
gep_bridge($status);
$path=explode(',',$end['path']);
foreach ($path as $v){
echo "{$result[$v]['comment']}\n";
}
function gep_bridge($status){
global $i;
global $result;
global $speed;
if(!judge($status)){#判断是否已全部过河
return;
}
$result[$i]=$status;
if($status['candle']=='left'){//灯在左边
$c=C($status['left']);//列出左边所有的两人组合
foreach ($c as $v){
$time=max($speed[$v[0]],$speed[$v[1]]);//本次过河需要的时间
$newStatus['left']=array_diff($status['left'],$v);//左边剩余的人
$newStatus['right']=array_merge($status['right'],$v);//右边已过河的人
$newStatus['sumTime']=$status['sumTime']+$time;//当前策略用时
$newStatus['candle']='right';//灯在河右边
$i++;
$newStatus['path']=$status['path'].','.$i;//记录策略
$newStatus['comment']="第".($v[0]+1)."个人和第".($v[1]+1)."个人过河，用时{$time},总用时{$newStatus['sumTime']}";//这里只是为了结果更直白
gep_bridge($newStatus);//把这个策略节点当做新的节点，递归处理
}
}else{//灯在右边，这里还可以优化，在当前问题中，每次返回送灯的人肯定是速度最快的人，没必要列举所有情况。
foreach ($status['right'] as $v){
$time=$speed[$v];
$newStatus['left']=array_merge($status['left'],[$v]);
$newStatus['right']=array_diff($status['right'],[$v]);
$newStatus['sumTime']=$status['sumTime']+$time;
$newStatus['candle']='left';
$i++;
$newStatus['path']=$status['path'].','.$i;
$newStatus['comment']="第".($v+1)."个人返回，用时{$time},总用时{$newStatus['sumTime']}";
gep_bridge($newStatus);
}
}
}
//排列组合，返回所有两人组合
function C($arr){
$count=count($arr);
$result=[];
for ($i=0;$i<$count-1;$i++){
for ($j=$i+1;$j<$count;$j++){
$result[]=[$arr[$i],$arr[$j]];
}
}
return $result;
}
//判断是否结束
function judge($status){
global $result;
global $end;
global $i;
if(count($status['left'])==0){//如果左边没有人了，表示已经全部过河
if(!$end || $status['sumTime']<$end['sumTime']){
//如果还没有策略成功或者策略过河的时间比当前策略时间长，则保留当前策略为最优策略
$end['sumTime']=$status['sumTime'];
$end['path']=$status['path'];
}
$result[$i]=$status;
return false;
}
foreach ($result as $v){
if($v['left']==$status['left'] && $v['right']==$status['right'] && $v['candle']==$status['candle'] && $status['sumTime']>=$v['sumTime']){
//判断当前状况有没有出现过，在本例中不会出现
return false;
}
}
return true;
}
运行结果
过桥问题--动态规划
请输入每个过桥人（人数>=2）的时间，用空格隔开：1 8 9 10
开始
第1个人和第2个人过河，用时8,总用时8
第1个人返回，用时1,总用时9
第3个人和第1个人过河，用时9,总用时18
第1个人返回，用时1,总用时19
第4个人和第1个人过河，用时10,总用时29
方法二：数学归纳
<?php
echo "过桥问题--归纳为数学问题，要么是最快者将最慢的2个送过桥，要么是最快的2个将最慢的2个送过桥\n";
fwrite(STDOUT, '请输入每个过桥人（人数>=2）的时间，用空格隔开：');
$a = fgets(STDIN);
$speed = array_map(function ($v) {
return intval($v);
}, array_filter(explode(' ', $a)));
$result = [];
$sumTime = 0;
$num = count($speed);//未过桥人数
asort($speed);//对时间进行排序
$keys = array_keys($speed);
echo "开始\n";
while ($num > 0) {
if ($num == 1) {//一个人
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."个人过河，用时{$speed[$keys[0]]},总用时{$sumTime}";
} elseif ($num == 2) {//两个人
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[0]+1)."个人和第".($keys[1]+1)."个人过河，用时{$speed[$keys[1]]},总用时{$sumTime}";
} elseif ($num == 3) {//三个人
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[0]+1)."个人和第".($keys[1]+1)."个人过河，用时{$speed[$keys[0]]},总用时{$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."个人返回，用时{$speed[$keys[0]]},总用时{$sumTime}";
$sumTime += $speed[$keys[2]];
$result[] = "第".($keys[0]+1)."个人和第".($keys[0]+2)."个人过河，用时{$speed[$keys[0]]},总用时{$sumTime}";
} else {//四个人 分两种情况
//1最快的将最慢两人送过河
$time1 = $speed[$keys[$num - 1]] + $speed[$keys[0]] * 2 + $speed[$keys[$num - 2]];
//2最快的两人将最慢两人送过河
$time2 = $speed[$keys[1]] * 2 + $speed[$keys[0]] + $speed[$keys[$num - 1]];
if ($time1 < $time2) {
$sumTime += $speed[$keys[$num - 1]];
$result[] = "第".($keys[0]+1)."个人和第".($keys[$num-1]+1)."个人过河，用时{$speed[$keys[$num-1]]},总用时{$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."个人返回，用时{$speed[$keys[0]]},总用时{$sumTime}";
$sumTime += $speed[$keys[$num - 2]];
$result[] = "第".($keys[0]+1)."个人和第".($keys[$num-2]+1)."个人过河，用时{$speed[$keys[$num-2]]},总用时{$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."个人返回，用时{$speed[$keys[0]]},总用时{$sumTime}";
} else {
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[0]+1)."个人和第".($keys[1]+1)."个人过河，用时{$speed[$keys[1]]},总用时{$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."个人返回，用时{$speed[$keys[0]]},总用时{$sumTime}";
$sumTime += $speed[$keys[$num - 1]];
$result[] = "第{$keys[$num-1]}个人和第".($keys[$num-2]+1)."个人过河，用时{$speed[$keys[$num-1]]},总用时{$sumTime}";
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[1]+1)."个人返回，用时{$speed[$keys[1]]},总用时{$sumTime}";
}
}
$num = ($num >= 3 ? $num - 2 : 0);
}
foreach ($result as $v){
echo $v."\n";
}
运行结果
过桥问题--归纳为数学问题，要么是最快者将最慢的2个送过桥，要么是最快的2个将最慢的2个送过桥
请输入每个过桥人（人数>=2）的时间，用空格隔开：1 8 9 10
开始
第1个人和第4个人过河，用时10,总用时10
第1个人返回，用时1,总用时11
第1个人和第3个人过河，用时9,总用时20
第1个人返回，用时1,总用时21
第1个人和第2个人过河，用时8,总用时29
