0

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

在这个问题中，您必须在一个数组中找到一个总和最接近 1000 的组合。这是我的解决方案，它在时间限制（0.26 秒，限制为 2 秒）下运行良好，但是，在 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 的组合，但我很肯定它有效，而且它非常简单，所以不值得展示，除非需要。

谁能告诉我我做错了什么？组合方法的逻辑是否不正确，或者是否有额外的检查或我缺少的那种东西？

4

1 回答 1

0

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

http://hastebin.com/etapohavud.cpp

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

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

于 2016-11-27T21:16:14.293 回答