如何找到数组元素的最接近特定值的可能总和？

Question

在Java中，我应该如何找到数组元素最接近（或等于）特定值K的可能总和？

例如，对于数组{19,23,41,5,40,36}和K=44，最接近的可能总和是23+19=42。 我已经苦苦思考了几个小时；我对动态规划知之甚少。此外，数组仅包含正数。

- Karim El Sheikh

---

5 + 40是最接近的可能和吗？ - splungebob

我的意思是总和将小于或等于K。 - Karim El Sheikh

你能够相加的数字有限制吗？例如，每个总和只能使用两个元素还是也可以使用所有元素的总和？ - G. Bach

任意数量元素的总和 - Karim El Sheikh

好的，请提供需要翻译的内容。 - arynaq

Answer 1

通常在这种问题中，您会使用动态规划。但是，这基本上归结为保持可能的总和集，并逐个添加输入值，如下所示的代码，并具有相同的渐近运行时间：O(n K)，其中n是您的输入数组的大小，K是目标值。

下面版本中的常量可能更大，但我认为该代码比动态规划版本更容易理解。

public class Test {
    public static void main(String[] args) {
        int K = 44;
        List<Integer> inputs = Arrays.asList(19,23,41,5,40,36);

        int opt = 0;                // optimal solution so far          

        Set<Integer> sums = new HashSet<>();
        sums.add(opt);

        // loop over all input values
        for (Integer input : inputs) {
            Set<Integer> newSums = new HashSet<>();

            // loop over all sums so far                        
            for (Integer sum : sums) {
                int newSum = sum + input;

                // ignore too big sums
                if (newSum <= K) {
                    newSums.add(newSum);

                    // update optimum                       
                    if (newSum > opt) {
                        opt = newSum;
                    }
                }
            }

            sums.addAll(newSums);
        }

        System.out.println(opt);
    }
}

编辑

关于运行时间，简短说明一下可能会有所帮助，因为我刚才声称了O(n K)，但没有解释。

显然，初始化和打印结果只需要常量时间，因此我们应该分析双重循环。

外部循环遍历所有输入，因此它的主体被执行n次。

内部循环遍历到目前为止的所有总和，理论上可以是指数级的。 然而，我们使用上限K，因此sums中的所有值都在范围[0，K]内。 由于sums是一个集合，因此它最多包含K + 1个元素。

内部循环中的所有计算都需要常量时间，因此总循环需要O(K)。由于同样的原因，集合newSums也包含最多K + 1个元素，因此结尾的addAll也需要O(K)。

总结一下：外部循环执行n次。 循环体需要O(K)的时间。 因此，该算法的时间复杂度为O(n K)。

编辑2

如要查找导致最优总和的元素：

您应该跟踪子列表的总和和子列表本身。 如果您创建一个新类型（没有getter / setter以保持示例简洁），这相对简单：

public class SubList {
    public int size;
    public List<Integer> subList;

    public SubList() {
        this(0, new ArrayList<>());
    }

    public SubList(int size, List<Integer> subList) {
        this.size = size;
        this.subList = subList;
    }
}

现在初始化变为：

SubList opt = new SubList();

Set<SubList> sums = new HashSet<>();
sums.add(opt);  

内部循环对sums也需要做出一些小的改动：

for (Integer input : inputs) {
    Set<SubList> newSums = new HashSet<>();

    // loop over all sums so far                        
    for (SubList sum : sums) {
        List<Integer> newSubList = new ArrayList<>(sum.subList);
        newSubList.add(input);
        SubList newSum = new SubList(sum.size + input, newSubList);         

        // ignore too big sums
        if (newSum.size <= K) {
            newSums.add(newSum);

            // update optimum                       
            if (newSum.size > opt) {
                opt = newSum;
            }
        }
    }

    sums.addAll(newSums);
}

- Vincent van der Weele

---

@Heuster 谢谢，我现在明白了，好的解决方案！但是我不理解的是最坏情况下的复杂度。在你评论中的例子（以及大多数元素都包含在结果中的任何例子中），我看到结果集每次都会翻倍，导致指数级复杂度，对吗？如果我错了，请告诉我。更新：由于您保留了每个子结果，因此空间复杂度也是指数级的，对吗？ - zafeiris.m

@zafeiris.m 我已经添加了一个有关运行时间的注释。关键在于 upperBound，它使得 sums 的大小保持在 K 的线性范围内。 - Vincent van der Weele

这不就是暴力算法或者动态规划吗？抱歉，我不懂Java。 - Aseem Goyal

@Heuster：另一个问题：所需的序列无法生成。我是对的吗？如果不是，请解释一下该方法。 - Aseem Goyal

@anon 我更新了答案，采用了一种见证方法：每当您更新最优解时，还要跟踪导致该最优解的子列表。 - Vincent van der Weele

Answer 2

您可以将其视为一个 n-choose-k 问题，对于所有可能的 k，复杂度是指数级别的。

1. 找到一组数字，它们的总和最多为 K。这个集合应该包含 i 个数字，其中 i=1; i<=N; i++。为了实现这一点，对于每个 i，只需取数组中所有数字的 n-choose-i 组合。
2. 保持一个 finalResult 变量，记录到目前为止找到的最佳数字集合及其总和。
3. 将步骤 1 的每个子结果与 finalResult 进行比较，如果有必要则更新它。

它让我想起了背包问题，您可能想看一下。

- zafeiris.m

Answer 3

private int closestSum(int[] a, int num){
    int k=a.length-1;
    int sum=0;
    Arrays.sort(a);

    while(a[k]>num){
        k--;
    }
    for(int i=0;i<k;i++){
        for(int j=i+1;j<=k;j++){
            if(a[i]+a[j]<=num && a[i]+a[j]>sum)
                sum = a[i]+a[j];
        }
    }
    return sum;
}

- Nilamber Singh

Answer 4

我会先对数组进行排序。然后你的例子就是：arr = {5, 19, 23, 36, 40, 41}。 然后： 1) 取arr [0]和arr [i]，其中i = arr.Size。将它们相加并记录总和与K之间的差值（如果总和小于K）。 2) 如果总和> K，请执行步骤1，但使用arr [i-1]代替arr [i]，因为我们希望降低总和。 如果总和< K，请执行步骤1，但使用arr [1]代替arr [0]，因为我们希望增加总和。 通过增加或减少索引重复步骤2，直到两个元素的索引相等。 然后，我们就知道了产生总和与K之间差值最小的一对元素。

----------------适用于任意数量元素的解决方案的编辑----------------

我认为你可能需要一棵树。这是我的想法：

1）选择一个数字作为顶部节点。

2）对于集合中的每个数字，创建一个子节点，并为每个创建的分支计算该分支的总和。

3) 如果总和小于K，我们再次分支，为集合中的所有元素创建子节点。如果总和大于K，我们停止，并保留总和与K之间的差值（如果总和小于K）。如果我们找到一个具有更好总和的分支，则保留该分支。重复此过程，直到所有分支都完成分支。

使用不同的顶级节点执行步骤1-3。

- masotann

---

如果我理解正确的话，这并不能正确地解决他的问题；例如搜索13时，[1, 2, 10]就是一个例子。 - G. Bach

@Calpis，如果参与结果的数字超过两个呢？ - zafeiris.m

抱歉，我没有意识到这是解决方案的任意数字。让我重新考虑一下。 - masotann