Min Abs Sum

April 01, 2017

分類標籤:algorithm dynamic programming

給定A = [a0, a1, …, an-1],如何找到一組S = [s0, s1, … sn-1], sj ∈ {-1, 1}, 使得abs(sum(ai * si))有最小值?關鍵在於對於 A 中的每個元素 a 能夠產生的 sum 作動態規劃。

目錄

思路

先將A的值全部轉正,問題就轉化成如何將A分成兩組,其sum分別為P和Q,使得P - Q有最小值。

dp[j]表示能否加總出sum = j,dp[j] >= 0 表示可以,<0 則否。我們將對每個A的值a迭代更新dp[j]dp[j]的值填入目前還有多少a可供使用。因為a可能會重複,先算count[a]備用。

例如:

A = [1, 3, 3], 迭代到a = 3 (count = 2)的情況下,因為已知可以達成sum = 1且有兩個3,所以將sum = 4 和 sum = 7也更新成可以達成的狀態。結果會是dp[1] = 2, dp[4] = 1, dp[7] = 0

動態規劃

如果dp[j] >= 0的話,表示靠先前出現過的a0, a1, …a-1已經可以計算出sum = j,dp[j]填入count[a]備用。

否則如果是dp[j-a] > 0的情況,表示可以算出sum = j-a,再加上a即可算出sum = j。 如上一步所言,dp[j-a]為可用a的數量,因此更新dp[j] = dp[j-a] - 1

最後找到最大的P使得P < S / 2 + 1

=> 答案 = Q - P = (S - P) - P = S - 2 * P

int solution(vector<int> &A) {
    int N = A.size();
    int M = 0;
    int S = 0;
    for (int i = 0; i < N; ++i) {
        A[i] = abs(A[i]);
        M = max(M, A[i]);
        S += A[i];
    }

    int count[M+1] = {0};
    for (int i = 0; i < N; ++i) {
        count[A[i]] += 1;
    }

    int dp[S+1] = {0};
    for (int i = 1; i < S+1; ++i) {
        dp[i] = -1;
    }

    for (int a = 1; a < M+1; ++a) {
        if (count[a] > 0) {
            for (int j = 0; j < S; ++j) {
                if (dp[j] >= 0) {
                    dp[j] = count[a];
                } else if (j-a >= 0 && dp[j-a] > 0) {
                    dp[j] = dp[j-a] - 1;
                }
            }
        }
    }

    int res = S;
    for (int i = 0; i < S/2 + 1; ++i) {
        if (dp[i] >= 0) {
            res = min(res, S - 2*i);
        }
    }

    return res;
}

觀察:A的值介於-100~100之間,所以重複的數量應該會很多,對於每個可能的值去迭代更新dp[j],相對於對A的每個元素迭代更有效率。

參考

題目

解答


Profile picture

Shubo Chao 軟體工程師,目前大多專注於前端開發