在 Java 中,我应该如何找到与特定值 K 最接近(或相等)的数组元素之和?
例如,对于数组 {19,23,41,5,40,36} 和 K=44,最接近的可能和是 23+19=42。 我已经为此苦苦挣扎了几个小时;我对动态规划几乎一无所知。顺便说一句,该数组只包含正数。
最佳答案
您通常会使用动态规划来解决此类问题。然而,这基本上归结为保留一组可能的总和并将输入值一个一个地相加,如以下代码所示,并且具有相同的渐近运行时间: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);
}
关于java - 如何找到与特定值最接近的数组元素之和?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16022205/