如何找到数组元素与特定值最接近的总和？

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

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

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

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

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

我会说首先排序数组。那么你的例子就是: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]，因为我们想降低我们的和。If sum <K，做第一步，但不是arr[0]，而是arr[1]，因为我们想增加和。通过增加或减少索引，继续重复步骤2，直到两个元素的索引相等。然后，我们知道使和与k之间的差最小的元素对>

---------------- 编辑任意数目的元素的解决方案 ----------------

我相信你可能需要一棵树。我是这么想的:

1)选择一个数字作为顶节点。

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

3)如果总和小于K，我们再次分支，为集合中的所有元素创建子节点。如果和大于K，则停止，保留和与K的差值(If sum <重复此过程，直到所有分支都完成分支。>

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

相关内容

最新更新

热门标签：