Podzielić optymalnie tablicę na dwie subarrays tak że suma elementów w obu są takie same

Question

mam podane równanie jak ten:

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

Jak mogę optymalnie zastąpić operatorów, tak że suma równania jest równe zero lub drukuje -1. Myślę o jednym algorytmie, ale nie jest on optymalny. Mam pomysł na brutalne skompletowanie wszystkich przypadków ze złożonością O(n*2^n), ale (n < 300).

Oto link do problemu: http://codeforces.com/gym/100989/problem/M.

Answer 1

Próbujesz rozwiązać Partition Problem; tj. podziel twoje liczby całkowite na dwa podzbiory, których sumy są takie same, i przypisz znak dodatni do liczb całkowitych w jednym podzbiorze i znaki ujemne do tych w innym podzbiorze.

W twoim konkretnym problemie masz niski limit zarówno liczby całkowitej, jak i wartości tych liczb całkowitych. Możesz zastosować standardowe podejście dynamicznego algorytmu z podejściem włączającym/wykluczającym; tj. znalezienie podzbioru pierwszych liczb całkowitych n, które sumują się do i, biorąc pod uwagę przypadek, w którym ostatnia z tych liczb całkowitych nie jest używana (więc potrzebujesz podzbioru pierwszych liczb całkowitych n-1 zsumowanych do i) i gdzie jest on używany (podzbiór z pierwszych liczb całkowitych n-1 zsumowanych do i - val(n)).

Answer 2

Oto pomysł:

1. Sortuj 2nd do N-te elementy malejące (problem pozostaje taka sama).
2. Utwórz sumę skumulowaną w odwrotnej kolejności. [1 4 3 2] => [10 9 5 2], aby uzyskać górną granicę dla najwyższego numeru, który wciąż możesz osiągnąć z pozostałymi liczbami całkowitymi.
3. Użyj granic z sumy skumulowanych zwrotów do przycinania.

W Javie:

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