HDU 1709 The Balance：母函數法求不可稱重價值完整解析

題目理解

給定 n 個砝碼（各有一個，重量為 a[i]），天平可將砝碼放兩側。求：

1. 無法稱出的重量值有多少個
2. 具體是哪些值

可稱出的值包括：直接放右盤的重量、左右盤差值產生的重量。

母函數核心思想

每個砝碼有三種狀態：不放、放左盤、放右盤。對應生成函數：

(1 + x^a[i] + x^(-a[i]))  // 但負指數難處理

技巧：只考慮右盤放置（正指數），後通過兩兩差值得到左右盤組合。

完整代碼實現

#include <stdio.h>
#include <string.h>

#define MAX 10008

int main() {
    int a[MAX], c1[MAX], c2[MAX], b[MAX];
    int i, j, k, n, sum;
    
    while (scanf("%d", &n) != EOF) {
        sum = 0;
        for (i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        
        // 初始化
        for (i = 1; i <= sum; i++) {
            b[i] = 0;
            c1[i] = c2[i] = 0;
        }
        
        // 第 1 個砝碼：放或不放
        for (i = 0; i <= 1; i++)
            c1[i * a[0]] = 1;
        
        // 母函數疊加：後續砝碼
        for (i = 1; i < n; i++) {
            for (j = 0; j <= sum; j++) {
                for (k = 0; k * a[i] + j <= sum && k <= 1; k++) {
                    c2[j + k * a[i]] += c1[j];
                }
            }
            // 複製並清零
            for (j = 0; j <= sum; j++) {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        
        // 計算所有可稱重量的差值
        for (i = sum; i > 0; i--) {
            if (c1[i]) {
                for (j = 1; j < i; j++) {
                    if (c1[j])
                        b[i - j] = 1;  // 標記差值可得
                }
            }
        }
        
        // 收集不可稱出的值
        k = 0;
        for (i = 1; i <= sum; i++) {
            if (!c1[i] && !b[i])  // 既非直接可稱，也非差值可得
                c2[k++] = i;
        }
        
        printf("%d\n", k);
        if (k) {
            for (i = 0; i < k - 1; i++)
                printf("%d ", c2[i]);
            printf("%d\n", c2[i]);
        }
    }
    return 0;
}

算法流程圖解

1. 輸入處理：讀取 n 和砝碼重量，計算總和 sum
2. 母函數構建：c1 記錄僅用右盤砝碼能組成的重量
3. 差值擴展：雙重循環計算任意兩可稱重量的差值，存入 b
4. 結果篩選：1~sum 中既不在 c1 也不在 b 的即為答案

複雜度分析

• 時間：O(n × sum²) —— 受限於 sum ≤ 10000 可接受
• 空間：O(sum) —— 三個輔助數組

優化方向

實際比賽中常用 01 背包 DP 替代母函數，代碼更簡潔、常數更小。但母函數思路對理解生成函數組合意義極有幫助。