如何找到一个数组的元素尽可能接近之和为特定值？ [英] How do I find the closest possible sum of an Array's elements to a particular value?

问题描述

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

In Java, how should I find the closest (or equal) possible sum of an Array's elements to a particular value K?

例如，对于数组{19,23,41,5,40,36}和K = 44，最接近的可能之和为23 + 19 = 42。 我一直挣扎在这几个小时;我几乎一无所知动态规划。顺便说一下，该阵列仅包含正数。

For example, for the array {19,23,41,5,40,36} and K=44, the closest possible sum is 23+19=42. I've been struggling on this for hours; I know almost nothing about dynamic programming. By the way, the array contains only positive numbers.

推荐答案

您通常会使用动态编程这样的问题。然而，基本上可以归结为保持一组可能的款项，并加输入值一个接一个，如下面的code，并且具有相同的渐近运行时间： 0（N K） ，其中 N 是输入数组的大小和 K 的目标值。

You would typically use dynamic programming for such a problem. However, that essentially boils down to keeping a set of possible sums and adding the input values one by one, as in the following code, and has the same asymptotic running time: O(n K), where n is the size of your input array and K is the target value.

在版本以下常量可能更大，不过，但我认为code是更容易跟踪，比动态编程的版本将是。

The constants in the version below are probably bigger, however, but I think the code is much easier to follow, than the dynamic programming version would be.

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

修改

一个短信上运行的时间可能是有用的，因为我只是声称 0（N K）没有道理。

A short note on running time might be useful, since I just claimed O(n K) without justification.

显然，初始化和打印结果只是需要一定的时间，所以我们应该分析双环。

Clearly, initialization and printing the result just takes constant time, so we should analyse the double loop.

外环运行在所有的输入，所以它的机身被执行 N 倍。

The outer loop runs over all inputs, so it's body is executed n times.

内环运行在所有款项，到目前为止，这可能是在理论上一个指数。 然而的，我们使用了一个上限 K ，所以在总和所有值在范围 [0，K] 。由于金额是一个集合，它包含至多 K + 1 元素。

The inner loop runs over all sums so far, which could be an exponential number in theory. However, we use an upper bound of K, so all values in sums are in the range [0, K]. Since sums is a set, it contains at most K+1 elements.

内环内所有的计算需要一定的时间，所以总的回路采用 O（K）。该集 newSums 还包含至多 K + 1 元素，出于同样的原因，所以的addAll 到底需要 O（K）和

All computations inside the inner loop take constant time, so the total loop takes O(K). The set newSums also contains at most K+1 elements, for the same reason, so the addAll in the end takes O(K) as well.

结束语：外循环执行 N 次。该循环体采用 O（K）。因此，该算法在运行为O（n K）。

Wrapping up: the outer loop is executed n times. The loop body takes O(K). Therefore, the algorithm runs in O(n K).

编辑2

后，关于如何还发现，导致最优总和的元素请求：

Upon request on how to also find the elements that lead to the optimal sum:

。这是相对简单的，如果你创建一个新的类型（无getter / setter方法​​，以保持示例简洁）：

Instead of keeping track of a single integer - the sum of the sublist - you should also keep track of the sublist itself. This is relatively straightforward if you create a new type (no getters/setters to keep the example concise):

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

初​​始化现在变成了：

The initialization now becomes:

SubList opt = new SubList();

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

在金额内环需要一些小的调整，以及：

The inner loop over the sums needs some small adaptations as well:

for (SubList sum : sums) {
    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);
}

这篇关于如何找到一个数组的元素尽可能接近之和为特定值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！