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

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/setters来保持示例简洁),这是相对简单的:

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