PHP算法之过河问题

方法一：动态规划

<?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