PHP 經典算法題：百錢百雞問題與窮舉法優化演示

PHP 經典算法題：百錢百雞問題與窮舉法優化演示

《孫子算經》中的「百錢百雞」是窮舉法的經典入門題。本文從最直觀的三層迴圈開始，逐步優化至單層迴圈，並統計各版本迴圈執行次數，直觀展示算法優化的威力。

題目重述

公雞 5 元/隻，母雞 3 元/隻，小雞 1 元/3 隻。用 100 元買 100 隻雞，問公、母、小雞各幾隻？

版本演進與效能比較

原始版：三層迴圈（1,030,301 次）

for ($g = 0; $g <= 100; ++$g) {
    for ($m = 0; $m <= 100; ++$m) {
        for ($x = 0; $x <= 100; ++$x) {
            if ($g*5 + $m*3 + $x/3 == 100 && $g + $m + $x == 100) { ... }
            $count++;
        }
    }
}

優化一：利用總數約束消去小雞迴圈（10,201 次）

$x = 100 - $g - $m;
if ($g*5 + $m*3 + $x/3 == 100) { ... }

優化二：依價格限制公/母雞上限（714 次）

for ($g = 0; $g <= 100/5; ++$g) {      // 公雞最多 20 隻
    for ($m = 0; $m <= 100/3; ++$m) {  // 母雞最多 33 隻
        $x = 100 - $g - $m;
        if ($g*5 + $m*3 + $x/3 == 100) { ... }
    }
}

優化三：動態計算母雞上限（364 次）

for ($g = 0; $g <= 20; ++$g) {
    for ($m = 0; $m <= (100 - $g*5)/3; ++$m) { // 扣除公雞花費後的剩餘錢
        $x = 100 - $g - $m;
        if ($g*5 + $m*3 + $x/3 == 100) { ... }
    }
}

優化四：利用小雞數量必為 3 的倍數（121 次）

if ($x % 3 != 0) continue; // 提前跳過不可能的組合

最終解答（四組解）

優化心得

1. 約束傳播：利用已知條件（總數、總價）減少搜尋空間。
2. 整數特性：小雞價格導致數量必為 3 的倍數，可直接跳過 2/3 的無效迴圈。
3. 邊界收緊：根據單價計算各變數最大可能值，避免無效迭代。

同樣的窮舉思想，透過數學洞察即可將效能提升 8500 倍（1,030,301 → 121）。