Walrus Weights/Получение комбинации в массиве, чья сумма ближайшая 1000

Question

Я работаю над этой проблемой https://open.kattis.com/problems/walrusweights. Я видел, что кто-то спрашивал об этом здесь, но мой подход к этой проблеме совершенно другой.

В этой проблеме вы должны найти комбинацию в массиве, размер которой близок к 1000. Вот мое решение, оно работает хорошо по времени (0.26 с, ограничение равно 2 с), однако, после 31 тестового примера, это дает мне неправильный ответ.

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