Teile, so dass Summe der Elemente in beiden gleich ist

Question

ich die Gleichung wie diese gegeben habe:

n = 7 
    1 + 1 - 4 - 4 - 4 - 2 - 2 

Wie kann ich Bediener optimal ersetzen, so dass die Summe der Gleichung ist gleich Null oder drucken -1. Ich denke an einen Algorithmus, aber es ist nicht optimal. Ich habe eine Idee, alle Fälle mit Komplexität O(n*2^n), aber (n < 300) bruteforce.

Hier ist der Link des Problems: http://codeforces.com/gym/100989/problem/M.

Answer 1

Sie versuchen, die Partition Problem zu lösen; d. h. Partitionieren Sie Ihre ganzen Zahlen in zwei Teilmengen, deren Summen gleich sind, und weisen Sie ganzen Zahlen in einer Teilmenge ein positives Vorzeichen und negativen Vorzeichen denen in der anderen Teilmenge zu.

In Ihrem speziellen Problem haben Sie eine niedrige Grenze für die Anzahl der ganzen Zahlen und den Wert dieser ganzen Zahlen. Sie können einen standardmäßigen dynamischen Algorithmus mit dem Einschluss/Ausschluss-Ansatz anwenden; dh eine Teilmenge der ersten n ganzen Zahlen zu finden, die zu i summiert, indem man den Fall betrachtet, in dem der letzte dieser Integer nicht verwendet wird (so benötigt man eine Teilmenge der ersten n-1 Integer summing to i) und wo sie verwendet wird (eine Teilmenge der ersten n-1 Integer summing zu i - val(n)). Hier

Answer 2

ist eine Idee:

1. Sortieren der zweiten bis N-ten Elemente absteigend (das Problem bleibt gleich).
2. Erstellen Sie die kumulative Summe in umgekehrter Reihenfolge. [1 4 3 2] => [10 9 5 2], um eine obere Grenze für die höchste Zahl zu erhalten, die Sie mit den restlichen ganzen Zahlen erreichen können.
3. Verwenden Sie die Grenzen der umgekehrten kumulativen Summe zu beschneiden.

In Java:

// assuming the numbers are positive 
// (ignore operator when parsing, line.split("[ +-]+") will do) 
public static int canReach0(int[] numbers) { 
    sort(numbers, 1); // sort(array, offset) doesn't matter what algorithm 
        // for 300 elements and compared to the complexity of the rest 
    int[] revSum = new int[numbers.length]; 
    revSum[numbers.length - 1] = numbers[numbers.length - 1]; 
    for (int i = numbers.length - 2; i >= 0; i--) 
    revSum[i] = revSum[i + 1] + numbers[i]; 
    int sum = numbers[0]; 
    if (sum == revSum[1]) 
    return 0; 
    return solve(numbers, 1, sum, revSum); 
} 

private static int solve(int[] numbers, int index, int sum, int[] revSum) { 
    if (index == numbers.length - 1) 
    return -1; 
    int high = sum + numbers[index]; 
    if (high == revSum[index + 1] || 
     (high < revSum[index + 1] && solve(numbers, index + 1, high, revSum) == 0)) 
    return 0; 
    int low = sum - numbers[index]; 
    if (low == -revSum[index + 1] || 
     (low > -revSum[index + 1] && solve(numbers, index + 1, low, revSum) == 0)) 
    return 0; 
    return -1; 
}