我们如何找到元字的最佳组合呢？最简单的方法就是穷举，但这样的方式要求计算机计算的次数非常巨大，而且时间复杂度高达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数组中，避免重复计算。
四、总结
本文主要讲述了元字的最佳组合问题，并介绍了三种解决方案，分别是顺序穷举法、排序+优化穷举法以及动态规划法。其中，顺序穷举法算法简单易实现，但是在元素数量较多时计算量大；排序+优化穷举法方法可以通过先排序以及判断和的大小来缩减计算量；动态规划方法则是应用了动态规划思想来解决问题，适用于需要求解最优解的情况下，同时还可提供状态转移方程。