java - 如何找到与特定值最接近的数组元素之和？

Question

在 Java 中，我应该如何找到与特定值 K 最接近(或相等)的数组元素之和？

例如，对于数组 {19,23,41,5,40,36} 和 K=44，最接近的可能和是 23+19=42。我已经为此苦苦挣扎了几个小时；我对动态规划几乎一无所知。顺便说一句，该数组只包含正数。

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);
}