方法一：動(dòng)態(tài)規(guī)劃
<?php
echo "過(guò)橋問(wèn)題--動(dòng)態(tài)規(guī)劃\n";
fwrite(STDOUT,'請(qǐng)輸入每個(gè)過(guò)橋人（人數(shù)>=2）的時(shí)間，用空格隔開(kāi)：');
$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'=>'開(kāi)始'];
$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)){#判斷是否已全部過(guò)河
return;
}
$result[$i]=$status;
if($status['candle']=='left'){//燈在左邊
$c=C($status['left']);//列出左邊所有的兩人組合
foreach ($c as $v){
$time=max($speed[$v[0]],$speed[$v[1]]);//本次過(guò)河需要的時(shí)間
$newStatus['left']=array_diff($status['left'],$v);//左邊剩余的人
$newStatus['right']=array_merge($status['right'],$v);//右邊已過(guò)河的人
$newStatus['sumTime']=$status['sumTime']+$time;//當(dāng)前策略用時(shí)
$newStatus['candle']='right';//燈在河右邊
$i++;
$newStatus['path']=$status['path'].','.$i;//記錄策略
$newStatus['comment']="第".($v[0]+1)."個(gè)人和第".($v[1]+1)."個(gè)人過(guò)河，用時(shí){$time},總用時(shí){$newStatus['sumTime']}";//這里只是為了結(jié)果更直白
gep_bridge($newStatus);//把這個(gè)策略節(jié)點(diǎn)當(dāng)做新的節(jié)點(diǎn)，遞歸處理
}
}else{//燈在右邊，這里還可以優(yōu)化，在當(dāng)前問(wèn)題中，每次返回送燈的人肯定是速度最快的人，沒(méi)必要列舉所有情況。
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)."個(gè)人返回，用時(shí){$time},總用時(shí){$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;
}
//判斷是否結(jié)束
function judge($status){
global $result;
global $end;
global $i;
if(count($status['left'])==0){//如果左邊沒(méi)有人了，表示已經(jīng)全部過(guò)河
if(!$end || $status['sumTime']<$end['sumTime']){
//如果還沒(méi)有策略成功或者策略過(guò)河的時(shí)間比當(dāng)前策略時(shí)間長(zhǎng)，則保留當(dāng)前策略為最優(yōu)策略
$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']){
//判斷當(dāng)前狀況有沒(méi)有出現(xiàn)過(guò)，在本例中不會(huì)出現(xiàn)
return false;
}
}
return true;
}
運(yùn)行結(jié)果
過(guò)橋問(wèn)題--動(dòng)態(tài)規(guī)劃
請(qǐng)輸入每個(gè)過(guò)橋人（人數(shù)>=2）的時(shí)間，用空格隔開(kāi)：1 8 9 10
開(kāi)始
第1個(gè)人和第2個(gè)人過(guò)河，用時(shí)8,總用時(shí)8
第1個(gè)人返回，用時(shí)1,總用時(shí)9
第3個(gè)人和第1個(gè)人過(guò)河，用時(shí)9,總用時(shí)18
第1個(gè)人返回，用時(shí)1,總用時(shí)19
第4個(gè)人和第1個(gè)人過(guò)河，用時(shí)10,總用時(shí)29
方法二：數(shù)學(xué)歸納
<?php
echo "過(guò)橋問(wèn)題--歸納為數(shù)學(xué)問(wèn)題，要么是最快者將最慢的2個(gè)送過(guò)橋，要么是最快的2個(gè)將最慢的2個(gè)送過(guò)橋\n";
fwrite(STDOUT, '請(qǐng)輸入每個(gè)過(guò)橋人（人數(shù)>=2）的時(shí)間，用空格隔開(kāi)：');
$a = fgets(STDIN);
$speed = array_map(function ($v) {
return intval($v);
}, array_filter(explode(' ', $a)));
$result = [];
$sumTime = 0;
$num = count($speed);//未過(guò)橋人數(shù)
asort($speed);//對(duì)時(shí)間進(jìn)行排序
$keys = array_keys($speed);
echo "開(kāi)始\n";
while ($num > 0) {
if ($num == 1) {//一個(gè)人
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."個(gè)人過(guò)河，用時(shí){$speed[$keys[0]]},總用時(shí){$sumTime}";
} elseif ($num == 2) {//兩個(gè)人
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[0]+1)."個(gè)人和第".($keys[1]+1)."個(gè)人過(guò)河，用時(shí){$speed[$keys[1]]},總用時(shí){$sumTime}";
} elseif ($num == 3) {//三個(gè)人
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[0]+1)."個(gè)人和第".($keys[1]+1)."個(gè)人過(guò)河，用時(shí){$speed[$keys[0]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."個(gè)人返回，用時(shí){$speed[$keys[0]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[2]];
$result[] = "第".($keys[0]+1)."個(gè)人和第".($keys[0]+2)."個(gè)人過(guò)河，用時(shí){$speed[$keys[0]]},總用時(shí){$sumTime}";
} else {//四個(gè)人 分兩種情況
//1最快的將最慢兩人送過(guò)河
$time1 = $speed[$keys[$num - 1]] + $speed[$keys[0]] * 2 + $speed[$keys[$num - 2]];
//2最快的兩人將最慢兩人送過(guò)河
$time2 = $speed[$keys[1]] * 2 + $speed[$keys[0]] + $speed[$keys[$num - 1]];
if ($time1 < $time2) {
$sumTime += $speed[$keys[$num - 1]];
$result[] = "第".($keys[0]+1)."個(gè)人和第".($keys[$num-1]+1)."個(gè)人過(guò)河，用時(shí){$speed[$keys[$num-1]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."個(gè)人返回，用時(shí){$speed[$keys[0]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[$num - 2]];
$result[] = "第".($keys[0]+1)."個(gè)人和第".($keys[$num-2]+1)."個(gè)人過(guò)河，用時(shí){$speed[$keys[$num-2]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."個(gè)人返回，用時(shí){$speed[$keys[0]]},總用時(shí){$sumTime}";
} else {
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[0]+1)."個(gè)人和第".($keys[1]+1)."個(gè)人過(guò)河，用時(shí){$speed[$keys[1]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[0]];
$result[] = "第".($keys[0]+1)."個(gè)人返回，用時(shí){$speed[$keys[0]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[$num - 1]];
$result[] = "第{$keys[$num-1]}個(gè)人和第".($keys[$num-2]+1)."個(gè)人過(guò)河，用時(shí){$speed[$keys[$num-1]]},總用時(shí){$sumTime}";
$sumTime += $speed[$keys[1]];
$result[] = "第".($keys[1]+1)."個(gè)人返回，用時(shí){$speed[$keys[1]]},總用時(shí){$sumTime}";
}
}
$num = ($num >= 3 ? $num - 2 : 0);
}
foreach ($result as $v){
echo $v."\n";
}
運(yùn)行結(jié)果
過(guò)橋問(wèn)題--歸納為數(shù)學(xué)問(wèn)題，要么是最快者將最慢的2個(gè)送過(guò)橋，要么是最快的2個(gè)將最慢的2個(gè)送過(guò)橋
請(qǐng)輸入每個(gè)過(guò)橋人（人數(shù)>=2）的時(shí)間，用空格隔開(kāi)：1 8 9 10
開(kāi)始
第1個(gè)人和第4個(gè)人過(guò)河，用時(shí)10,總用時(shí)10
第1個(gè)人返回，用時(shí)1,總用時(shí)11
第1個(gè)人和第3個(gè)人過(guò)河，用時(shí)9,總用時(shí)20
第1個(gè)人返回，用時(shí)1,總用時(shí)21
第1個(gè)人和第2個(gè)人過(guò)河，用時(shí)8,總用時(shí)29
