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

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