POJ 1004 Dividing：多重背包二進制優化判斷能否平分

POJ 1004 Dividing：多重背包判斷集合能否等分

題目大意：輸入 6 個整數 a1..a6，表示價值為 i 的物品有 ai 個。問能否將所有物品分成兩堆價值相等。多組數據，全 0 結束。

解題思路：01 背包轉多重背包 + 二進制優化

總價值 sum = Σ i·ai。若 sum 為奇數直接 "Can't be divided."。否則目標容量 V = sum/2。每種物品數量有限，屬多重背包。用二進制拆分數量：將 ai 拆為 1, 2, 4, ..., 2^k, 剩餘，轉化為若干 01 物品，再做 01 背包 DP。
DP 狀態：dp[j] 表示能否湊出價值 j。初始 dp[0] = true。最終檢查 dp[V]。

核心代碼

int a[7], dp[120005];
int main() {
    int cas = 0;
    while (scanf("%d%d%d%d%d%d", &a[1],&a[2],&a[3],&a[4],&a[5],&a[6]) == 6) {
        if (!a[1] && !a[2] && !a[3] && !a[4] && !a[5] && !a[6]) break;
        int sum = 0;
        for (int i = 1; i <= 6; i++) sum += a[i] * i;
        printf("Collection #%d:\n", ++cas);
        if (sum % 2) {
            puts("Can't be divided.\n");
            continue;
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        int V = sum / 2;
        for (int i = 1; i <= 6; i++) {
            int cnt = a[i];
            for (int k = 1; k <= cnt; k <<= 1) {
                int w = k * i;
                for (int j = V; j >= w; j--)
                    dp[j] |= dp[j - w];
                cnt -= k;
            }
            if (cnt) {
                int w = cnt * i;
                for (int j = V; j >= w; j--)
                    dp[j] |= dp[j - w];
            }
        }
        if (dp[V]) puts("Can be divided.\n");
        else puts("Can't be divided.\n");
    }
    return 0;
}

關鍵點

• 二進制拆分將多重背包轉為 01 背包，時間複雜度 O(V log ai)。
• dp[0] = 1 必須初始化，否則轉移無法啟動。
• 輸出格式需嚴格匹配樣例（空行、大小寫、標點）。