如何找到arrays元素与特定值的最接近可能总和？

在Java中，我应该如何找到arrays元素与特定值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 inputs = Arrays.asList(19,23,41,5,40,36); int opt = 0; // optimal solution so far Set sums = new HashSet<>(); sums.add(opt); // loop over all input values for (Integer input : inputs) { Set 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的上限，因此所有和的值都在[0, K]范围内。 由于sums是一个集合，它最多包含K+1元素。

内循环内的所有计算都需要恒定的时间，因此总循环需要O(K) 。 由于同样的原因，set newSums也包含K+1元素，因此最后的addAll需要O(K) 。

结束：外循环执行n次。 循环体取O(K) 。 因此，算法在O(n K) 。

编辑2

根据请求如何找到导致最佳总和的元素：

而不是跟踪单个整数 – 子列表的总和 – 您还应该跟踪子列表本身。 如果您创建一个新类型（没有getter / setters来保持示例简洁），这是相对简单的：

 public class SubList { public int size; public List subList; public SubList() { this(0, new ArrayList<>()); } public SubList(int size, List subList) { this.size = size; this.subList = subList; } } 

现在初始化变为：

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

sums的内循环也需要一些小的调整：

 for (Integer input : inputs) { Set newSums = new HashSet<>(); // loop over all sums so far for (SubList sum : sums) { List 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); } 

Answer 2

您可以将其视为所有可能k的n-choose-k问题，因此复杂性是指数级的 。

1. 找到一组总和最多为K 。 对于i=1; i<=N; i++ ，该集应包括i个数i=1; i<=N; i++ i=1; i<=N; i++ i=1; i<=N; i++ 。 为了实现这一点，对于每个i只需要采用数组中所有数字的n-choose-i 组合 。
2. 保留一个finalResult变量，其中包含到目前为止找到的最佳数字集及其总和。
3. 将步骤1的每个子结果与finalResult ，并在必要时进行更新。

它让我想起了背包问题 ，所以你可能想看看它。

Answer 3

我会说首先排序数组。 然后你的例子是：arr = {5,19,23,36,40,41}。 然后：1）取arr [0]和arr [i]，其中i = arr.Size。 如果总和低于K，则将它求和并记录总和与K之间的差值.2）如果总和> K，执行步骤1，但使用arr [i-1]代替arr [i-1]，因为我们想要降低我们的总和。 如果sum

—————-编辑解决方案中的任意数量的元素—————-

我相信你可能需要一棵树。 这就是我的想法：

1）选择一个数字作为您的顶级节点。

2）对于集合中的每个数字，创建一个子节点，对于创建的每个分支，计算该分支的总和。

3）如果总和小于K，我们再次分支，为集合中的所有元素创建子节点。 如果总和大于K，我们停止，保持总和与K之间的差值（如果总和

使用不同的topnodes执行步骤1-3。