Веса Моржей / Получение комбинации в массиве, сумма которой ближе всего к 1000

Question

Я работал над этой проблемой 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, но я уверен, что это работает, и это довольно просто, поэтому показывать его не стоит, если в этом нет необходимости.

Может кто-нибудь сказать мне, что я делаю не так? Неправильна ли логика метода комбинирования, или я провожу дополнительную проверку или что-то в этом роде?

Answer 1

Немного поздно, но я ответил на это и оставлю это здесь для других, чтобы посмотреть, если они должны.

http://hastebin.com/etapohavud.cpp

Я сделал рекурсивный метод, который обходит массив чисел (который был ранее отсортирован), проверяя только суммы, которые могут привести к ближайшему, добавляя все возможные в ArrayList. Это отсортировано, так что мне не нужно было бы беспокоиться о поиске меньшего числа впереди, которое могло бы изменить всю текущую сумму, которую я проверяю.

Короче говоря, я вычислил все жизнеспособные комбинации, которые могли оказаться ближе к 1000, а затем нашел самую близкую к ней.