元字的最佳組合

我們如何找到元字的最佳組合呢？最簡單的方法就是窮舉，但這樣的方式要求計算機計算的次數非常巨大，而且時間複雜度高達O(n^4)。本文將在代碼實現中給出更為高效的方法。

一、順序窮舉法

首先介紹一種基本的窮舉方法——順序窮舉法。從左向右，從上向下枚舉每個元素，暴力枚舉每一種組合方式，最後求解出最優解。

<?php
 
function optimalCombination($array) {
    $len = count($array);
    $max_sum = 0;
    $pos = [0, 0, 0, 0]; // 用一個數組來記錄下標
    for ($i = 0; $i < $len; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            for ($k = $j + 1; $k < $len; $k++) {
                for ($l = $k + 1; $l < $len; $l++) {
                    $sum = $array[$i] + $array[$j] + $array[$k] + $array[$l];
                    if ($sum > $max_sum) {
                        $max_sum = $sum;
                        $pos = [$i, $j, $k, $l];
                    }
                }
            }
        }
    }
    return [$max_sum, $pos];
}
 
$array = [12, 16, 20, 32, 58, 89, 99];
list($max_sum, $pos) = optimalCombination($array);
echo "最大值為：$max_sum，其下標為(" . implode(',', $pos) . ")";
 
?>

上面的代碼是PHP語言的實現代碼，其核心思想就是嵌套四層循環依次枚舉每個元素，最後將所有組合的和求出來，從而得到最大值以及最大值對應的下標。

雖然此方法非常簡便易行，但是當元素數量較大時計算量極大，效率不高，所以我們需要優化。

二、排序+優化窮舉法

我們可以先對所有元素排序，此時處於數組左側的元素一定比處於右側的元素都小，那麼這樣子循環次數就能大大減少，只需要枚舉排序後的前四個元素即可。

在此基礎上，進一步優化的方法是，當四個數的和不大於當前找到的最大和時，可以直接跳出內層循環，尋找下一組元素的組合。

<?php
 
function optimalCombination($array) {
    sort($array);  // 先排序
    $len = count($array);
    $max_sum = 0;
    $pos = [0, 0, 0, 0];
    for ($i = $len - 1; $i >= 3; $i--) {
        if ($array[$i] + $array[$i-1] + $array[$i-2] + $array[$i-3] <= $max_sum) {
            break;  // 如果當前四數之和小於等於已找到的最大和，直接跳出循環
        }
        for ($j = $i - 1; $j >= 2; $j--) {
            if ($array[$i] + $array[$j-1] + $array[$j-2] + $array[$j] <= $max_sum) {
                break;
            }
            for ($k = $j - 1; $k >= 1; $k--) {
                if ($array[$i] + $array[$j] + $array[$k-1] + $array[$k] <= $max_sum) {
                    break;
                }
                for ($l = $k - 1; $l >= 0; $l--) {
                    $sum = $array[$i] + $array[$j] + $array[$k] + $array[$l];
                    if ($sum > $max_sum) {
                        $max_sum = $sum;
                        $pos = [$l, $k, $j, $i];
                    }
                }
            }
        }
    }
    return [$max_sum, $pos];
}
 
$array = [12, 16, 20, 32, 58, 89, 99];
list($max_sum, $pos) = optimalCombination($array);
echo "最大值為：$max_sum，其下標為(" . implode(',', $pos) . ")";
 
?>

上面的代碼是使用PHP語言實現的排序+優化版的窮舉算法。注意，在使用sort()函數進行排序時，默認是按升序排序。

三、動態規劃法

動態規劃是一種算法思想，其思想是將複雜問題簡化為若干個子問題，通過求解子問題的最優解，組合各個子問題的最優解得到原問題的解。在本文中，我們同樣可以使用動態規劃思想去解決元字的最佳組合問題。（此處省略掉狀態轉移方程的推導）

<?php
 
function optimalCombination($array) {
    $len = count($array);
    if ($len < 4) {
        return false;
    }
    sort($array);  // 先排序
    $dp = [];
    for ($i = 0; $i < $len; $i++) {
        for ($k = $len - 1; $k > $i + 2; $k--) {
            $dp[$i][$k] = $array[$i] + $array[$i+1] + $array[$k-1] + $array[$k];
            if ($i > 0 && $k < $len - 1) {
                $dp[$i][$k] = max($dp[$i][$k], $dp[$i-1][$k-1] + $array[$i] - $array[$i-1] - $array[$k] + $array[$k-1]);
            }
        }
    }
    $max_sum = 0;
    $pos = [0, 1, $len-2, $len-1];
    for ($i = 0; $i < $len - 3; $i++) {
        for ($k = $len - 1; $k > $i + 2; $k--) {
            if ($dp[$i][$k] > $max_sum) {
                $max_sum = $dp[$i][$k];
                $pos = [$i, $i+1, $k-1, $k];
            }
        }
    }
    return [$max_sum, $pos];
}
 
$array = [12, 16, 20, 32, 58, 89, 99];
list($max_sum, $pos) = optimalCombination($array);
echo "最大值為：$max_sum，其下標為(" . implode(',', $pos) . ")";
 
?>

上面的代碼是使用PHP語言實現的動態規划算法，由於本文篇幅有限，省略了狀態轉移方程的推導過程。需要注意的是，前兩個元素與後兩個元素構成的子序列是單調性區間，並且一定是子問題的最優解，因此需要將其預處理到dp數組中，避免重複計算。

四、總結

本文主要講述了元字的最佳組合問題，並介紹了三種解決方案，分別是順序窮舉法、排序+優化窮舉法以及動態規劃法。其中，順序窮舉法算法簡單易實現，但是在元素數量較多時計算量大；排序+優化窮舉法方法可以通過先排序以及判斷和的大小來縮減計算量；動態規劃方法則是應用了動態規劃思想來解決問題，適用於需要求解最優解的情況下，同時還可提供狀態轉移方程。