如何找到一个数组的元素尽可能接近之和为特定值? [英] 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屋!