PHP编程如何求取边端点值的最大可能总和

这类问题通常对应图/树结构的计算场景：给定若干顶点，每个顶点绑定一个数值，顶点间通过边连接，要求选出符合约束的边集合，计算所有选中边的两端点数值之和的总和，求该总和的最大可能值。

场景1：边无共享顶点（最大权匹配场景） #

约束要求选中的任意两条边没有公共顶点，属于典型的最大权匹配问题：

• 问题转化逻辑：将每条边的权重设置为两个端点的数值之和，求图的最大权匹配即可得到目标最大值
• 顶点规模≤20时，可以用状态压缩动态规划实现，代码示例如下：

<?php
// 配置：顶点数值数组，下标为顶点ID
$vertexValues = [3, 5, 2, 7, 1];
// 配置：图的所有边，每个元素为两个顶点ID的数组
$edges = [[0,1], [1,2], [2,3], [3,4], [0,4], [1,3]];
$vertexCount = count($vertexValues);
// dp[mask]表示mask二进制位标记的顶点集合可获得的最大总和
$dp = array_fill(0, 1 << $vertexCount, 0);

for ($mask = 0; $mask < (1 << $vertexCount); $mask++) {
    // 找到第一个未被使用的顶点
    $firstUnused = -1;
    for ($i = 0; $i < $vertexCount; $i++) {
        if (!($mask & (1 << $i))) {
            $firstUnused = $i;
            break;
        }
    }
    if ($firstUnused === -1) continue;
    
    // 情况1：不选该顶点关联的任何边，直接标记为已用继承当前值
    $newMask = $mask | (1 << $firstUnused);
    if ($dp[$newMask] < $dp[$mask]) {
        $dp[$newMask] = $dp[$mask];
    }
    
    // 情况2：选该顶点和相邻未使用顶点的边，更新总和
    foreach ($edges as $edge) {
        $another = -1;
        if ($edge[0] === $firstUnused && !($mask & (1 << $edge[1]))) {
            $another = $edge[1];
        } elseif ($edge[1] === $firstUnused && !($mask & (1 << $edge[0]))) {
            $another = $edge[0];
        }
        if ($another !== -1) {
            $newMask2 = $mask | (1 << $firstUnused) | (1 << $another);
            $currentSum = $dp[$mask] + $vertexValues[$firstUnused] + $vertexValues[$another];
            if ($dp[$newMask2] < $currentSum) {
                $dp[$newMask2] = $currentSum;
            }
        }
    }
}
// 输出最大总和
echo "最大可能总和：" . max($dp);
?>

场景2：树结构单条路径最大和 #

约束要求选中的边构成一条简单路径（无重复顶点的连通路径），此时总和等于路径所有顶点数值之和的2倍减去路径首尾顶点的数值，可用树形动态规划实现：

<?php
$vertexValues = [3, 5, 2, 7];
// 树的邻接表
$adj = [
    0 => [1],
    1 => [0, 2, 3],
    2 => [1],
    3 => [1]
];
$maxSum = 0;

function dfs($node, $parent) {
    global $adj, $vertexValues, $maxSum;
    // 存储以当前节点为端点的最大路径和
    $currentMax = $vertexValues[$node];
    foreach ($adj[$node] as $neighbor) {
        if ($neighbor === $parent) continue;
        $neighborMax = dfs($neighbor, $node);
        // 更新全局最大值：当前节点拼接左右两个子路径
        $maxSum = max($maxSum, $currentMax + $neighborMax);
        // 更新当前节点作为端点的最大路径和
        $currentMax = max($currentMax, $vertexValues[$node] + $neighborMax);
    }
    $maxSum = max($maxSum, $currentMax);
    return $currentMax;
}

dfs(0, -1);
// 边端点总和等于路径顶点和 * 2 - 首尾顶点和，这里计算得到的$maxSum是最大路径顶点和，可根据实际约束调整转换逻辑
echo "路径最大边端点总和：" . ($maxSum * 2 - min($vertexValues));
?>

因Codility有限公司提出的DMCA下架请求，原问题对应的专属约束、测试用例等特定内容已被移除，以上为通用场景下的标准实现方案，可根据实际业务约束调整逻辑。

内容的提问来源于stack exchange，提问作者Nikunj Dhimar