java - 比较并计算数组中的数字以接近目标

Question

我有一个包含 3 的数组

我想将它们组合起来，以便尽可能接近 1000，但如果其中一个数字是 1000，那么我当然只想取该数字。

如果程序找到一个同样接近 1000 的组合，也许是 999 和 1001，它应该取最大的数字。

我的代码有两个问题:

1) 如果一个数字是 1000，则不会回答 1000。它会回答 1000 和另一个最小的数字。

2) 它根据我给出输入数字的顺序找到最佳匹配。无论如何它都应该找到它。

示例:我的输入是 900、500、498 和 4。这给出了 904，这是错误的。

我的输入是2、498、900和500。输出为 1002，这是正确的。相同的数字但顺序不同:

Example: my input is 4, 5, 6, 1000. It gives me 1004, but it should give me 1000.

这是我的代码

记住:数组中至少有 3 个Integer!

        int target = 1000;
        int optimum = 0;
        int optimum_distance = target;
        List<Integer> sums = new ArrayList<Integer>(0);
        sums.add(0,weights[0]);

try {
    for(int i=1; i < weights.length; i++) {
        int weight = weights[i];
        List<Integer> newSums = new ArrayList<Integer>();
        for(int j=0; j < sums.size(); j++) {

            int sum = sums.get(j);
                newSums.add(sum);
                int newSum = sum + weight;
                int distance = Math.abs(target - newSum);
                if (newSum <= target) {
                    newSums.add(newSum);
                    if (distance < optimum_distance) {
                        optimum = newSum;
                        optimum_distance = distance;
                    }
                }
                else if (distance < optimum_distance || (distance == optimum_distance && newSum > optimum))
                {
                    optimum = newSum;
                    optimum_distance = distance;
                    newSums.add(newSum);
                }
            }
        sums = newSums;
    }
} catch (Exception e){
  System.err.println("Error");
  System.exit(1);
}
System.out.print(optimum);  

Answer 1

可能不完全是您正在寻找的内容，但解决了要求。该方法是构建一个幂集并计算它们的总和。 {1, 2, 3} 的幂集为:

{{},{1}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}}

public class CloseTo1000 { 
static Set<List<Integer>> powerSet = new HashSet<>();

public static void main(String[] args) {        

    List<Integer> mainList = new ArrayList<Integer>();
    mainList.add(900);
    mainList.add(500);
    mainList.add(498);
    mainList.add(4);
    powerSet = buildPowerSet(mainList,mainList.size());
    System.out.println(powerSet);

    Set<List<Integer>> toremove = new HashSet<List<Integer>>(); //remove the empty set
    for(List<Integer> li : powerSet){
        if(li.isEmpty()){
        toremove.add(li);
        }
    }
    powerSet.removeAll(toremove);

    findOptimum(powerSet);        
}

private static Set<List<Integer>> buildPowerSet(List<Integer> list, int count){

    powerSet.add(list);

    for(int i=0; i<list.size(); i++)
    {
        List<Integer> temp = new ArrayList<Integer>(list);
        temp.remove(i);
        buildPowerSet(temp, temp.size());
    }
    return powerSet;
}


private static int findOptimum(Set<List<Integer>> powerSet){
    int opt = 10000 ;
    List<Integer> optList = new ArrayList<Integer>();

    for (List<Integer> li : powerSet){
        int k = Math.abs(li.stream().mapToInt(Integer :: intValue).sum()-1000);// find absolute difference to 1000
        System.out.println(k);   
        if(k<opt){
        opt=k;
        optList=li;
        }
        if(k==opt && li.stream().mapToInt(Integer :: intValue).sum()>1000){// 999 and 1001, it should take the highest number
        opt=k;
        optList=li;
        }
    } 
    opt = opt +1000;
     System.out.println("optList: "+optList);
     System.out.println("opt: " +opt);
    return opt;     
}
}