java - 对导致元素乘积最大的数组进行排序

Question

我正在研究一个问题，该问题涉及将整数数组作为用户的输入。该程序计算数组元素的乘积。计算过程如下:例如，让输入为 56、61、2。然后程序首先执行 56 * 61 = 3416，然后 modulo 3416 with 199 = 33。现在取数组中的下一个元素，即 2，并将它与 33 = 66 相乘。结果将是 3416 + 33 = 3482。这是同位素原子的计算。现在，如果我们可以重新排列数组的元素，即 61、2、56；我们可以实现最大乘积如下:

61 * 2 = 122
122 * 56 = 6832
6832 + 122 = 6954

我写了一个程序，可以简单地计算输入数组的乘积，但现在我想按上面提到的那样对数组进行排序。我的程序如下:

import java.util.*;
public class codevita1 {
    public static void main (String []args) {
        int num = 0;
        try {
            num = Integer.parseInt (args[0]);
        } catch (Exception e) {
            System.err.println ("Arguments not enough");
        }
        int arr[] = new int[num];
        for (int i = 1; i <= num; i++) {
            arr[i-1] = Integer.parseInt(args[i]);
        }
        new codevita1().calcEnery (arr);
    }

    private int calcEnergy (int elements[]) {
    int energy = 0;
    int t = 1;
    for (int i = 0; i < elements.length; i++) {
        if (i == 0) {
            energy = (elements[i] * elements[++i]);
        } else {
            energy += (t * elements[i]);
        }
        t = energy % 199;
    }
    return energy;
}
}

我已经搜索过动态规划和分而治之算法，但我不明白哪种算法可以帮助我完成任务。请帮助我了解应该使用哪种算法以及如何使用？

Answer 1

天真的方法是检查每个排列，这需要 O(n!) 时间。

您可能还会注意到 (a%199 * b)%199 = (a * b) %199它允许我们检查将一组数字分成两个几乎相等的子集的所有方法。当我们检查 split 方式时，我们可以计算出 t ，它在计算第一个子集的能量后剩余，作为第一个子集 % 199 中所有数字的乘积，无论子集中元素的顺序如何，它都将保持不变。然后我们可以递归地计算两个子集的最优顺序。

如果子集的顺序很重要，则有 C(n,n/2) 种方法可以将 n 个数字分成两个子集。 C(n,n/2) < 2^n 所以操作总数小于 2^n * 2 * 2^(n/2) * 4 * 2^(n/4) * 8 * 2^(n/8) *... * 2 ^ (log(n)/2) * 2^(2) * 2 ^ (log(n)) * 2 ^ 1 即 ~ 2^(2*n + 2*log (n)) 这是 O(2^n) 所以仍然很慢但比 n 好!

我怀疑拆分成更多的子集(更准确地说是 sqrt(n) 个子集 sqrt(n) 个元素在每个子集中)可能会好得多，但尚未计算这种情况的复杂性。