UVA 562 Dividing Coins：0/1 背包問題經典應用解析

問題背景

UVA 562 "Dividing Coins" 是一道經典的 0/1 背包問題變體。題目要求將一組金幣分成兩堆，使得兩堆價值差異最小。這本質上是尋找一個子集，其總價值最接近所有金幣總價值的一半。

核心思路：轉化為背包問題

設所有金幣總價值為 sum，我們只需在容量為 sum/2 的背包中，裝入價值最大的金幣組合。設該最大價值為 maxValue，則兩堆差異為 sum - 2 * maxValue。這正是標準的 0/1 背包動態規劃模型。

動態規劃狀態定義

• dp[j]：容量為 j 的背包所能裝入的最大金幣價值。
• 狀態轉移方程：dp[j] = max(dp[j], dp[j - value[i]] + value[i])，其中 value[i] 為第 i 個金幣的價值。
• 為避免重複使用同一金幣，內層循環需從大到小遍歷（j = mid_cost down to value[i]）。

關鍵代碼解析 (C++)

const int N = 1e5 + 10;
int dp[N];
int value[N];

int main() {
    int Ncase;
    scanf("%d", &Ncase);
    while (Ncase--) {
        memset(dp, 0, sizeof(dp));
        int sum_cost = 0, n_bags;
        scanf("%d", &n_bags);
        for (int i = 0; i < n_bags; ++i) {
            scanf("%d", &value[i]);
            sum_cost += value[i];
        }
        int mid_cost = sum_cost / 2;
        for (int i = 0; i < n_bags; ++i) {
            for (int j = mid_cost; j >= value[i]; --j) {
                dp[j] = max(dp[j], dp[j - value[i]] + value[i]);
            }
        }
        printf("%d\n", sum_cost - 2 * dp[mid_cost]);
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(T * n * sum/2)，其中 T 為測試案例數，n 為金幣數量，sum 為總價值。題目限制 sum ≤ 10^5，故可通過。
• 空間複雜度：O(sum)，使用一維陣列優化空間。

常見陷阱與優化

• 數組大小：dp 陣列需開到總價值一半以上（1e5/2 + 10）。
• 初始化：每個測試案例必須將 dp 歸零。
• 輸出格式：直接輸出差值，無需額外文字。

總結

本題展示了 0/1 背包在「平衡分割」場景的典型應用。掌握「總和一半做容量、求最大價值、用差值作答案」的轉化技巧，對解決類似分割問題（如 POJ 1017、HDU 1022）極有幫助。