Walrus Weights/Abrufen einer Kombination in einem Array, dessen Summe am nächsten liegt

Question

Ich habe an diesem Problem gearbeitet https://open.kattis.com/problems/walrusweights. Ich habe gesehen, dass jemand anders hier danach gefragt hat, aber meine Herangehensweise an dieses Problem ist völlig anders.

In dem Problem müssen Sie eine Kombination in einem Array finden, die Summe ist am nächsten an 1000. Hier ist meine Lösung, es funktioniert gut unter dem Zeitlimit (0,26s, Limit ist 2s), jedoch nach 31 Testfällen, Es gibt mir eine falsche Antwort.

In meinem Programm, las ich zunächst alle Zahlen und es auf ein Array Größe n + 1 machen (mit einer Null als erste Zahl, werde ich erklären kurz), und dann rufe ich diese Methode:

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); 
    } 
} 

mit:

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

In der Kombinationsmethode sind die Parameter der Index Sie sind momentan in dem Array, ob Sie auf die Summe den aktuellen Eintrag hinzugefügt werden, die aktuelle Summe, und die höchste Kombination, die bisher bei 1000 liegt.

Ich habe eine Methode erstellt, die, sobald alle Kombinationen fertig sind, die 1000 am ehesten erhält, aber ich bin mir sicher, dass das funktioniert, und es ist ziemlich einfach, so dass es sich nicht lohnt, angezeigt zu werden.

Kann mir jemand sagen, was ich falsch mache? Ist die Logik der Kombinationsmethode falsch oder gibt es eine zusätzliche Überprüfung oder etwas von der Art, die mir fehlt?

Answer 1

Ein bisschen spät, aber ich habe das beantwortet und werde es hier für andere, um zu sehen, ob sie müssen.

http://hastebin.com/etapohavud.cpp

I eine rekursive Methode gemacht, dass die Anordnung von Zahlen durchläuft (die zuvor sortiert wurden) nur Summen überprüft, die auf die nächstgelegene führen könnten alle möglichen, zu einer Arraylist hinzuzufügen. Es ist so sortiert, dass ich mir keine Sorgen machen muss, dass ich eine kleinere Zahl vor mir finde, was die gesamte aktuelle Summe, die ich überprüfe, ändern könnte.

Kurz gesagt, ich berechnete alle lebensfähigen Kombinationen, die am Ende der 1000 am nächsten sein könnte und dann die nächste am nächsten gefunden.