UVA 562 Dividing Coins：0/1 背包求兩堆硬幣最小差值

UVA 562 Dividing Coins：0/1 背包求兩堆硬幣最小差值

給定 N 枚硬幣（面值 ≤ 500），分成兩堆，求兩堆總價值差的最小值。N ≤ 100，總和 ≤ 50000。

問題轉化

設總和 S，選一堆和為 x，另一堆 S-x，差值 |S-2x|。
目標：找 x ≤ S/2 使 S-2x 最小，即找 ≤ S/2 的最大可達成和 x。

0/1 背包可行性 DP

dp[j]：是否能湊出和 j。
初始 dp[0] = true。
對每枚硬幣 v，逆序更新：

for (int i=0; i=v[i]; j--)
        if (dp[j-v[i]]) dp[j] = true;

注意：dp[j] = dp[j] || dp[j-v[i]] 錯誤（會丟失「僅用前 i-1 個硬幣湊出 j」的情況），必須用 if 判斷。

完整代碼

#include 
#include 
const int MAXN = 105;
const int MAXSUM = 50000;
int v[MAXN];
bool dp[MAXSUM+1];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        int sum = 0;
        for (int i=0; i=v[i]; j--)
                if (dp[j-v[i]]) dp[j] = true;
        int ans = sum;
        for (int i=sum/2; i>=0; i--)
            if (dp[i]) { ans = sum - 2*i; break; }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• 逆序循環保證 0/1 性質（每枚硬幣用一次）。
• if (dp[j-v[i]]) dp[j]=true 而非 dp[j] |= dp[j-v[i]]，雖然邏輯等價但後者掩蓋了狀態轉移語義。
• 從 sum/2 向下找第一個 true，差值最小。
• 多測試用例，每次重置 dp 數組。

複雜度

時間 O(N * sum) ≤ 5e6，空間 O(sum) ≤ 5e4，極快。

此題是「子集和問題 → 0/1 背包可行性 DP → 平衡分割」的教科書級範例，代碼簡潔高效。