ZeroJudge 解題筆記：t163.挑選紀念品

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


ZeroJudge 題目連結：t163.挑選紀念品

解題想法

每組測資第一列為兩個整數 $n ~(1 \leq n \leq 40), w ~(0 \leq w \leq 10^9)$，代表有 $n$ 件紀念品，背包最多可以裝到總重量 $w$；第二列有 $n$ 個正整數 $a_i ~(1 \leq a_i \leq 10^9)$，分別代表第 $i$ 個紀念品的重量。每件紀念品最多只能選一次，在不超重的條件下共有幾種挑選方式。

這題看起來是標準的 0/1 背包問題，但是 $w$ 的範圍太大，如果用一個長度為 $w+1$ 的一維陣列 $dp$ 記錄挑選方法數，這樣會超出記憶體上限而且速度很慢，需要用折半枚舉才能 AC。不過這題的記憶體上限為 64 MB，Python 就算用折半枚舉還是無法 AC，依然會超出記憶體上限。

Python 程式碼

只能通過 60% 的測資。

def solve():
    import sys
    from bisect import bisect_right
    
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        w = int(data[ptr + 1])
        ptr += 2
        # 讀取物品重量
        items = [int(x) for x in data[ptr : ptr + n]]
        ptr += n

        # 折半切分
        mid = n // 2
        left_items = items[: mid]
        right_items = items[mid :]
        
        # 自訂函式，窮舉左、右兩半所有的重量組合
        def get_subset_sum(arr):
            sums = [0]
            for x in arr:
                sums += [s + x for s in sums]
            return sums

        # 呼叫 get_subset_sum，窮舉左、右兩半子集合
        left_sums = get_subset_sum(left_items)
        right_sums = get_subset_sum(right_items)
        
        # 右半部排序，用於二分搜
        right_sums.sort()
            
        # 走訪左半部，用二分搜找右半部合法的數量
        ans = 0
        for isum in left_sums:
            if isum > w: continue  # 左半部就超重，略過
            # 從右半部找大於 (w - isum) 的第一個位置
            ans += bisect_right(right_sums, w - isum)
        
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;

// 自訂函式，計算所有子集合總重量，代入範圍內各物體重量 arr，正在檢查的索引值 idx，目前的加總 curr，儲存計算結果的 result
void get_subset_sum(const vector<LL>& arr, int idx, LL curr, vector<LL>& result) {
    // 遞迴出口，檢查到最後一項
    if (idx == (int)arr.size()) {
        result.push_back(curr);
        return;
    }
    
    // 選擇1，不拿 arr[idx]，遞迴
    get_subset_sum(arr, idx + 1, curr, result);
    // 選擇2，拿 arr[idx]，遞迴
    get_subset_sum(arr, idx + 1, curr + arr[idx], result);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    LL w;
    while(cin >> n >> w) {
        // 讀取物品重量
        vector<LL> items (n);
        for(int i = 0; i < n; i++) {
            cin >> items[i];
        }
    
        // 折半切分
        int mid = n / 2;
        vector<LL> left_items (items.begin(), items.begin() + mid);
        vector<LL> right_items (items.begin() + mid, items.end());
        vector<LL> left_sums, right_sums;
        left_sums.reserve(1 << left_items.size());
        right_sums.reserve(1 << right_items.size());
        
        // 呼叫 get_subset_sum，窮舉左、右兩半子集合
        get_subset_sum(left_items, 0, 0, left_sums);
        get_subset_sum(right_items, 0, 0, right_sums);
        
        // 右半部排序，用於二分搜
        sort(right_sums.begin(), right_sums.end());
        
        // 走訪左半部，用二分搜找右半部合法的數量
        LL ans = 0;
        for(LL isum : left_sums) {
            if (isum > w) continue;  // 左半部就超重，略過
            // 從右半部找大於 (w - isum) 的第一個位置
            auto idx = upper_bound(right_sums.begin(), right_sums.end(), w - isum) - right_sums.begin();
            // 更新 ans
            ans += idx;
        }
        cout << ans << "\n";
    }
    return 0;
}