海象权重/在一个和最接近1000的数组中获得一个组合

Question

我一直在处理这个问题https://open.kattis.com/problems/walrusweights.我看到别人在这里问过这个问题，但我对这个问题的处理方式完全不同。

在这个问题中，你必须在一个数组中找到一个和最接近1000的组合。这是我的解决方案，它在时间限制（0.26s，限制为2s）下运行良好，然而，在31个测试用例之后，它给了我错误的答案。

在我的程序中，我首先读取所有的数字，并使其成为一个n+1大小的数组（第一个数字是零，我稍后会解释），然后我调用这个方法：

public static void combination(int index, boolean use, int currentSum, int closest){
    HS.add(currentSum);
    HS.add(closest);
    if(index == size){
        return;
    }
    if(use)
        currentSum += array[index];
    index++;
    if(currentSum == 0){ //would interfere with the if statement below, if it's 0, it will always be closer to 1000 
        combination(index, true, currentSum, closest);
        combination(index, false, currentSum, closest);
    }
    else{
        if(Math.abs(1000 - currentSum) < Math.abs(1000 - closest)){//so, if the currentSum is closer to 1000 than the closest so far
            closest = currentSum; //this is now the closest one
        }
        else //otherwise, there's no point going on with further changes to this combination, it will never be closest
            return;
        combination(index, true, currentSum, closest);
        combination(index, false, currentSum, closest);
    }
}

带有：

combination(0, nums, false, 0, 1000001); //limit of weights is 1000000

在组合方法中，参数是当前所在的索引、数组、是否将当前条目添加到总和、当前总和以及迄今为止最接近1000的最高组合。

我做了一个方法，一旦所有的组合都完成了，它就会得到最接近1000的一个，但我确信这是有效的，而且它非常简单，所以除非需要，否则不值得展示。

有人能告诉我我做错了什么吗？组合方法的逻辑是错误的，还是有一个额外的检查或我缺少的那种东西？

Answer 1

有点晚了，但我已经回答了这个问题，并将把它留在这里，让其他人看看是否需要。

http://hastebin.com/etapohavud.cpp

我做了一个递归方法，遍历数组（之前已经排序），只检查可能导致最接近的和的和，并将所有可能的和添加到ArrayList中。它是经过排序的，所以我不必担心前面会找到一个较小的数字，这可能会改变我正在检查的整个当前总和。

简而言之，我计算了所有可行的组合，这些组合最终可能最接近1000，然后找到了最接近1000的组合。