ZeroJudge 解題筆記：o628.天秤 (Libra)

作者：王一哲
日期：2026年10月18日


ZeroJudge 題目連結：o628.天秤 (Libra)

題目 pdf 檔連結：天秤 (Libra)

解題想法

這題是TOI練習賽202409潛力組第3題，這組題目當中最簡單的一題。題目是多組測資。每組測資第1列為1個整數 $n (2 \leq n \leq 100)$，代表有 $n$ 個砝碼，第2列有 $n$ 個正整數 $w_1, w_2, w_3, \dots, w_n ~(w_i \leq 10^3)$，代表這 $n$ 個砝碼的重量。題目要檢測，是否能將 $n$ 個砝碼分為總重量相同的兩組。

先計算砝碼總重量 $wsum$，如果 $wsum$ 是奇數，不可能平分，直接輸出 $0$。接下來要湊出 $target = wsum // 2$，因為每個砝碼只有選或不選兩種可能性，是 0/1 背包問題，可以用一維陣列 $dp$ 記錄狀態，$dp[j]$ 是否可以湊出總重量 $j$，也可以用 bitset 取代陣列。 。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 9.9 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        weights = list(map(int, data[ptr:ptr+n]))
        ptr += n
        wsum = sum(weights)
        if wsum%2 == 1:  # 不可能平分，輸出 0
            result.append("0\n")
            continue
        target = wsum//2  # 目標
        dp = [False]*(target+1)  # 0/1 背包問題，是否能湊出 target
        dp[0] = True
        for w in weights:
            for j in range(target, w-1, -1):
                dp[j] |= dp[j-w]
        result.append("1\n" if dp[target] else "0\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 14 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        weights = list(map(int, data[ptr:ptr+n]))
        ptr += n
        wsum = sum(weights)
        if wsum%2 == 1:  # 不可能平分，輸出 0
            result.append("0\n")
            continue
        target = wsum//2  # 目標
        dp = 1  # 0/1 背包問題，是否能湊出 target
        for w in weights:
            dp |= (dp << w)
        result.append("1\n" if (dp >> target) & 1 else "0\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 9 ms，記憶體約為 3.6 MB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // n 個砝碼
    while(cin >> n) {
        int w, wsum = 0;  // 重量，重量加總
        vector<int> weights (n);  // n 個砝碼的重量
        for(int i = 0; i < n; i++) {
            cin >> w;
            weights[i] = w;
            wsum += w;
        }

        // 特例，如果 wsum 是奇數，無法平分
        if (wsum % 2 == 1) {
            cout << "0\n";
            continue;
        }

        // 0/1 背包問題
        int target = wsum / 2;
        vector<bool> dp (target + 1, false);
        dp[0] = true;  // 一定可以湊出總重量 0
        for(int w : weights) {
            for(int j = target; j >= w; j--) {
                if (dp[j - w]) dp[j] = true;
            }
        }

        // 如果 dp[target] == true，有解
        cout << dp[target] << "\n";
    }
    return 0;
}

使用時間約為 2 ms，記憶體約為 3.6 MB，通過測試。

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // n 個砝碼
    while(cin >> n) {
        int w, wsum = 0;  // 重量，重量加總
        vector<int> weights (n);  // n 個砝碼的重量
        for(int i = 0; i < n; i++) {
            cin >> w;
            weights[i] = w;
            wsum += w;
        }

        // 特例，如果 wsum 是奇數，無法平分
        if (wsum % 2 == 1) {
            cout << "0\n";
            continue;
        }

        // 0/1 背包問題
        int target = wsum / 2;
        bitset<50001> dp;  // 題目總重量上限 100 * 1000 = 100000，目標上限 50000
        dp.set(0);  // 一定可以湊出總重量 0
        for(int w : weights) {
            dp |= (dp << w);
        }

        // 如果 dp[target] == true，有解
        cout << dp[target] << "\n";
    }
    return 0;
}

C 語言程式碼

使用時間約為 5 ms，記憶體約為 1.9 MB，通過測試。

#include <stdio.h>

int main() {
    int n;  // n 個砝碼
    while(scanf("%d", &n) != EOF) {
        int w, wsum = 0;  // 重量，重量加總
        int weights[100] = {0};  // n 個砝碼的重量，題目上限 100 個
        for(int i = 0; i < n; i++) {
            scanf("%d", &w);
            weights[i] = w;
            wsum += w;
        }

        // 特例，如果 wsum 是奇數，無法平分
        if (wsum % 2 == 1) {
            puts("0");
            continue;
        }

        // 0/1 背包問題
        int target = wsum / 2;
        int dp[50001] = {0};  // 題目總重量上限 100 * 1000 = 100000，目標上限 50000
        dp[0] = 1;  // 一定可以湊出總重量 0
        for(int i = 0; i < n; i++) {
            for(int j = target; j >= weights[i]; j--) {
                if (dp[j - weights[i]]) dp[j] = 1;
            }
        }

        // 如果 dp[target] == 1，有解
        printf("%d\n", dp[target]);
    }
    return 0;
}