给定偶数长度数组求最大GCD配对和：现有代码出错，求正确解法

给定一个长度为偶数n的整数数组，需要将元素两两配对，计算每对的GCD，最终使所有配对的GCD之和最大。约束条件：n∈[2,20]，arr[i]∈[1,10^9]。

示例：

• 示例1：arr=[3,4,9,5]，最优配对为(4,5)和(3,9)，GCD和为1+3=4。
• 示例2：arr=[1,2,3,4,5,6]，最优配对为(1,5)、(2,4)、(3,6)，GCD和为1+2+3=6。

现有代码的问题 #

你当前的贪心策略（排序后首尾配对）仅在部分案例中有效，比如示例1，但无法保证全局最优。以示例2为例，你的代码会将(1,6)、(2,5)、(3,4)配对，GCD总和为1+1+1=3，远小于最优解6。这是因为贪心只考虑了局部配对的GCD，没有考虑整体组合的最大总和。

正确解法：状态压缩动态规划 #

由于n的最大值为20，我们可以使用状态压缩动态规划来解决这个问题。用二进制掩码（mask）表示元素的使用状态：掩码的第k位为1表示第k个元素已被配对，0表示未被配对。dp[mask]表示当前状态下能得到的最大GCD总和。

具体步骤：

1. 预处理所有两两元素的GCD值，存储在二维数组中，避免重复计算。
2. 初始化dp数组：dp[0] = 0（没有元素被使用时总和为0），其余初始化为-1表示未访问。
3. 遍历所有可能的掩码状态，对于每个状态，找到第一个未被使用的元素i，然后遍历所有j > i且未被使用的元素j，计算新状态的最大总和：

   dp[new_mask] = max(dp[new_mask], dp[mask] + gcd(arr[i], arr[j]))
   

   其中new_mask = mask | (1 << i) | (1 << j)。
4. 最终答案为dp[(1 << n) - 1]，即所有元素都被配对时的最大总和。

Java代码实现 #

import java.util.Arrays;

public class MaxGcdPairSum {
    public static int solve(int[] arr) {
        int n = arr.length;
        int[][] gcds = new int[n][n];
        // 预处理两两元素的GCD值
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                gcds[i][j] = gcd(arr[i], arr[j]);
            }
        }

        int fullMask = (1 << n) - 1;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int mask = 0; mask <= fullMask; mask++) {
            if (dp[mask] == -1) continue;
            // 找到第一个未被使用的元素
            int firstUnused = -1;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) {
                    firstUnused = i;
                    break;
                }
            }
            if (firstUnused == -1) continue; // 所有元素已配对完成
            // 遍历所有未被使用且下标大于firstUnused的元素
            for (int j = firstUnused + 1; j < n; j++) {
                if ((mask & (1 << j)) == 0) {
                    int newMask = mask | (1 << firstUnused) | (1 << j);
                    dp[newMask] = Math.max(dp[newMask], dp[mask] + gcds[firstUnused][j]);
                }
            }
        }

        return dp[fullMask];
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        int[] arr1 = {3,4,9,5};
        System.out.println(solve(arr1)); // 输出4
        int[] arr2 = {1,2,3,4,5,6};
        System.out.println(solve(arr2)); // 输出6
    }
}

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