11

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

例如，对于数组 {19,23,41,5,40,36} 和 K=44，最接近的可能和是 23+19=42。我已经为此苦苦挣扎了几个小时；我对动态编程几乎一无所知。顺便说一句，数组只包含正数。

4

4 回答 4

16

对于此类问题，您通常会使用动态编程。但是，这基本上归结为保留一组可能的总和并逐个添加输入值，如下面的代码所示，并且具有相同的渐近运行时间O(n K)：.nK

然而，下面版本中的常量可能更大，但我认为代码比动态编程版本更容易理解。

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);
}
于 2013-04-15T19:14:52.510 回答
2

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

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

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

于 2013-04-15T19:15:26.777 回答
0

我会说首先对数组进行排序。那么您的示例将是：arr = {5, 19, 23, 36, 40, 41}。然后： 1) 取 arr[0] 和 arr[i]，其中 i = arr.Size。求和并记录总和与 K 的差，如果总和小于 K。 2) 如果 sum > K，执行步骤 1，但不要使用 arr[i]，而是使用 arr[i-1]，因为我们想要降低我们的总和。如果 sum < K，则执行第 1 步，但不要使用 arr[0]，而是使用 arr[1]，因为我们想要增加总和。不断重复第 2 步，增加或减少索引，直到两个元素的索引相等。然后，我们知道导致总和和 K 之间差异最小的元素对。

----------------针对解决方案中任意数量的元素进行了编辑----------------

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

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

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

3) 如果总和小于 K，我们再次分支，为集合中的所有元素创建子节点。如果总和大于 K，我们停止，保持总和与 K 之间的差（如果总和 < K）。如果我们找到一个总和更好的分支，那么我们保留那个分支。重复此过程，直到所有分支都完成分支。

使用不同的顶部节点执行步骤 1-3。

于 2013-04-15T18:38:14.263 回答
0 
private int closestSum(int[] a, int num){
    int k=a.length-1;
    int sum=0;
    Arrays.sort(a);

    while(a[k]>num){
        k--;
    }
    for(int i=0;i<k;i++){
        for(int j=i+1;j<=k;j++){
            if(a[i]+a[j]<=num && a[i]+a[j]>sum)
                sum = a[i]+a[j];
        }
    }
    return sum;
}
于 2020-05-19T20:27:30.593 回答