最佳分割數組分成兩個子陣等等元素都在那筆相同

Question

我給出的等式，像這樣的：

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

我怎麼能代替最佳運營商，從而使等式的總和等於零，或打印-1。 我想到了一種算法，但它不是最優的。我有一個想法強制所有案件的複雜性O(n*2^n)，但(n < 300)。

這是問題的鏈接：http://codeforces.com/gym/100989/problem/M。

Answer 1

您正在嘗試解決Partition Problem;即將整數分成兩個子集，其總和相同，並將正號分配給一個子集中的整數，將負號分配給另一個子集中的整數。

在您的特定問題中，您對整數數量和整數值都有一個下限。您可以使用包含/排除方法應用標準動態算法方法;即通過考慮這些整數中的最後一個未被使用（因此需要第一個總和爲i的整數的子集）以及它被使用的位置（一個子集）的情況來找到總計爲i的第一個整數的子集第一個n-1整數總和爲i - val(n)）。

Answer 2

這裏有一個想法：

1. 排序第2至第N個元素降（問題保持不變）。
2. 反向構建累計和。 [1 4 3 2] => [10 9 5 2]獲得最高數字的上限，您仍然可以通過其餘整數達到上限。
3. 使用反向累積和的界限進行修剪。

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