DP SOS: Quy hoạch động tổng tập con

Experiments (1)

Tổng các tập con của 26

DP SOS (Sum over Subsets) tính tổng giá trị của mọi tập con cho từng tập hợp. Bài học bắt đầu từ cách duyệt toàn bộ cặp mask, submask, sau đó giảm công việc lặp lại bằng quy hoạch động. Bạn sẽ thấy cùng một đáp án qua ba mức thời gian: $O(4^k)$ , $O(3^k)$ và $O(k2^k)$ .

Bài viết được biên soạn lại từ DP SOS của SPyofgame trên es.ac.vn, với biên tập viên tuandebu và người đóng góp ngpin04. Phần định nghĩa, hai cách cày trâu và các ví dụ đến từ bản gốc; phần duyệt tập con và truy hồi SOS là phần bổ sung của bản này. Xem nguồn và ghi chú biên soạn.

Kiến thức cần có

Mảng, vòng lặp, hàm đệ quy và phép cộng số nguyên trong C++
Biểu diễn nhị phân: bit thứ $p$ có trọng số $2^p$ , đánh số từ $0$
Phép AND &, OR |, XOR ^ và dịch trái <<
Ý tưởng quy hoạch động: lưu và tái sử dụng kết quả của các bài toán con

Nếu cần ôn C++, bắt đầu từ bài học nhập và xuất. Bài này thuộc nhóm quy hoạch động của CP Wiki.

Bài toán tổng tập con

Xét tập nền $U=\{0,1,\ldots,k-1\}$ . Một số nguyên mask trong $[0,2^k)$ biểu diễn một tập con của $U$ : bit $p$ bằng $1$ khi tập đó chứa $p$ . Ví dụ, $26=(11010)_2$ biểu diễn tập $\{1,3,4\}$ .

Cho mảng $a$ có $2^k$ phần tử. Với mỗi mask, cần tính

F[mask]=\sum_{submask\subseteq mask}a[submask].

Ký hiệu $submask\subseteq mask$ so sánh hai tập hợp được biểu diễn bằng bit, tương đương với (submask & mask) == submask. Nó không có nghĩa là submask <= mask: chẳng hạn $3\leq4$ , nhưng $(011)_2$ không phải tập con của $(100)_2$ .

Tập rỗng có mã $0$ , nên $a[0]$ được tính trong mọi tổng. Nếu bài toán không tính tập rỗng, có thể đặt $a[0]=0$ trước khi chạy. Nếu mảng ban đầu chỉ có $n<2^k$ phần tử, chủ động thêm số $0$ vào các vị trí $n,\ldots,2^k-1$ .

Ví dụ nhỏ

Với $k=2$ và $a=[1,2,3,4]$ :

`mask`	Biểu diễn tập hợp	Các `submask` hợp lệ	Tổng
`00`	$\varnothing$	`00`	$1$
`01`	$\{0\}$	`00`, `01`	$1+2=3$
`10`	$\{1\}$	`00`, `10`	$1+3=4$
`11`	$\{0,1\}$	`00`, `01`, `10`, `11`	$1+2+3+4=10$

Kết quả là $F=[1,3,4,10]$ . Giá trị a[mask] là trọng số gắn với cả tập hợp, không phải tổng trọng số của từng bit trong tập hợp đó.

Ví dụ từ sơ đồ gốc

Với mask = 26, chỉ các bit $1,3,4$ được bật. Tám tập con có mã $0,2,8,10,16,18,24,26$ . Các giá trị trong hình gốc là:

`submask`	0	2	8	10	16	18	24	26
$a[submask]$	8	9	9	10	12	4	6	14

Do đó $F[26]=8+9+9+10+12+4+6+14=72$ .

Tổng các tập con của 26

flowchart TD
    total["F[26] = 72"] --> low["Không có bit 4: 36"]
    total --> high["Có bit 4: 36"]
    low --> l0["a[0] + a[2] = 17"]
    low --> l1["a[8] + a[10] = 19"]
    high --> h0["a[16] + a[18] = 16"]
    high --> h1["a[24] + a[26] = 20"]

Ready when requested

Sơ đồ chia tám tập con thành hai nhóm theo bit $4$ , rồi chia tiếp theo bit $3$ . Bảng và phép cộng phía trên vẫn cung cấp toàn bộ ví dụ khi chưa mở sơ đồ.

Cách cày trâu

Khởi tạo $F[mask]=0$ . Duyệt mọi mask và mọi submask trong $[0,2^k)$ ; nếu submask là tập con của mask, cộng $a[submask]$ vào $F[mask]$ .

Cày trâu bằng vòng lặp

Hàm nhận mảng đã được thêm số $0$ cho đủ $2^k$ phần tử. Các ví dụ C++ trong bài dùng long long; mọi tổng trung gian phải nằm trong miền biểu diễn của kiểu này.

#include <cstddef>
#include <vector>

std::vector<long long> brute_sos(const std::vector<long long>& a) {
    std::vector<long long> result(a.size(), 0);
    for (std::size_t mask = 0; mask < a.size(); ++mask) {
        for (std::size_t submask = 0; submask < a.size(); ++submask) {
            if ((mask & submask) == submask) {
                result[mask] += a[submask];
            }
        }
    }
    return result;
}

Có $2^k\cdot2^k=4^k$ cặp cần kiểm tra. Phép AND kiểm tra tập con trong thời gian hằng số khi mask nằm trong một từ máy. Nếu thay phép AND bằng vòng lặp kiểm tra từng bit, thời gian có thể tăng thành $O(k4^k)$ .

Cày trâu bằng đệ quy

Với mỗi vị trí bit, xét bốn cặp giá trị (bit của mask, bit của submask): (0,0), (0,1), (1,0), (1,1). Khi đã chọn xong $k$ bit, kiểm tra quan hệ tập con rồi cộng vào kết quả.

#include <cstddef>
#include <vector>

void brute_recursive(int bit, std::size_t mask, std::size_t submask,
                     const std::vector<long long>& a,
                     std::vector<long long>& result) {
    if (bit < 0) {
        if ((mask & submask) == submask) {
            result[mask] += a[submask];
        }
        return;
    }
    const std::size_t flag = std::size_t{1} << bit;
    brute_recursive(bit - 1, mask,        submask,        a, result);
    brute_recursive(bit - 1, mask,        submask | flag, a, result);
    brute_recursive(bit - 1, mask | flag, submask,        a, result);
    brute_recursive(bit - 1, mask | flag, submask | flag, a, result);
}

Trước khi gọi, tạo result gồm $2^k$ số $0$ , rồi gọi brute_recursive(k - 1, 0, 0, a, result). Điều kiện bit < 0 phải được xét trước phép dịch bit. Với $k=0$ , lời gọi đi thẳng vào trường hợp cơ sở và cho $F[0]=a[0]$ .

Cây đệ quy có $4^k$ lá. Tổng số nút là $1+4+\cdots+4^k$ , nên thời gian là $O(4^k)$ ; ngăn xếp có độ sâu $O(k)$ , ngoài mảng kết quả $O(2^k)$ .

Chỉ duyệt các tập con hợp lệ

Phần bổ sung này loại các cặp không hợp lệ ngay từ khi duyệt. Bắt đầu ở submask = mask, rồi lặp submask = (submask - 1) & mask để sinh tập con kế tiếp theo thứ tự giảm dần.

#include <cstddef>
#include <vector>

std::vector<long long> submask_sos(const std::vector<long long>& a) {
    std::vector<long long> result(a.size(), 0);
    for (std::size_t mask = 0; mask < a.size(); ++mask) {
        std::size_t submask = mask;
        while (true) {
            result[mask] += a[submask];
            if (submask == 0) break;
            submask = (submask - 1) & mask;
        }
    }
    return result;
}

Phép trừ $1$ tắt bit $1$ thấp nhất và bật các bit thấp hơn; phép AND loại những bit không thuộc mask. Ví dụ, với mask = 10 (1010), thứ tự là 1010, 1000, 0010, 0000. Dừng sau khi xử lý $0$ để vừa tính tập rỗng vừa tránh quay lại mask.

Trong một cặp hợp lệ, mỗi bit có ba khả năng: không thuộc cả hai tập, chỉ thuộc mask, hoặc thuộc cả hai. Vì thế tổng số cặp trên mọi mask là $3^k$ . Có thể đạt cùng giới hạn bằng cách bỏ nhánh (0,1) khỏi hàm đệ quy.

Quy hoạch động theo từng bit

Phần bổ sung này giải thích cách tái sử dụng các tổng. Gọi $D_i[mask]$ là tổng của những $a[submask]$ thỏa:

submask là tập con của mask
Các bit từ $i$ trở lên của submask giống mask
Chỉ các bit $0,\ldots,i-1$ được phép thay đổi từ $1$ thành $0$

Khi chưa xử lý bit nào, chỉ có chính mask, nên $D_0[mask]=a[mask]$ . Khi đã xử lý cả $k$ bit, mọi tập con đều được tính, nên $D_k[mask]=F[mask]$ .

Công thức truy hồi và tính đúng đắn

Nếu bit $i$ của mask bằng $0$ , mọi tập con cũng có bit này bằng $0$ , nên không có nhóm mới. Nếu bit đó bằng $1$ , chia các tập con thành hai nhóm rời nhau: giữ bit $i$ và bỏ bit $i$ .

D_{i+1}[mask]= \begin{cases} D_i[mask], & (mask\mathbin{\&}2^i)=0,\\ D_i[mask]+D_i[mask\mathbin{\oplus}2^i], & (mask\mathbin{\&}2^i)\ne0. \end{cases}

Hai nhóm bao phủ toàn bộ các tập con được phép sau bước $i$ và không giao nhau. Từ trường hợp cơ sở, quy nạp theo $i$ cho thấy mỗi giá trị được cộng đúng một lần vào tổng cần thiết.

Có thể ghi đè trên một mảng: tại bước $i$ , chỉ các mask có bit $i=1$ bị cập nhật. Mọi ô được đọc thêm đều có bit $i=0$ , nên chưa bị thay đổi trong bước đó. Vì vậy thứ tự duyệt mask trong cùng một bước bit không ảnh hưởng kết quả.

Theo dõi một ví dụ

Vẫn dùng $a=[1,2,3,4]$ :

Bước	`00`	`01`	`10`	`11`
Khởi tạo $D_0=a$	1	2	3	4
Xử lý bit 0	1	$2+1=3$	3	$4+3=7$
Xử lý bit 1	1	3	$3+1=4$	$7+3=10$

Phải đặt vòng lặp bit ở ngoài khi ghi đè theo cách này. Nếu đổi sang mask ở ngoài, với ví dụ trên có thể thu được $11$ thay vì $10$ ở mask 11, vì $a[0]$ bị cộng lặp.

Chương trình C++17

Chương trình đọc $k$ , tiếp theo là đúng $2^k$ số nguyên. Giới hạn $0\leq k\leq20$ và $|a[i]|\leq10^9$ là lựa chọn cho ví dụ này: tổng trị tuyệt đối không vượt $2^{20}\cdot10^9$ , nằm trong long long. Đây không phải giới hạn toán học của SOS DP.

#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

std::vector<long long> sos_dp(std::vector<long long> values, int k) {
    for (int bit = 0; bit < k; ++bit) {
        const std::size_t flag = std::size_t{1} << bit;
        for (std::size_t mask = 0; mask < values.size(); ++mask) {
            if ((mask & flag) != 0) {
                values[mask] += values[mask ^ flag];
            }
        }
    }
    return values;
}

int main() {
    int k;
    if (!(std::cin >> k) || k < 0 || k > 20) {
        std::cerr << "Expected integer k in [0, 20]\n";
        return 1;
    }
    const std::size_t count = std::size_t{1} << k;
    std::vector<long long> a(count);
    for (long long& value : a) {
        if (!(std::cin >> value) || value < -1000000000LL || value > 1000000000LL) {
            std::cerr << "Expected 2^k integers in [-10^9, 10^9]\n";
            return 1;
        }
    }
    std::string extra;
    if (std::cin >> extra) {
        std::cerr << "Unexpected extra input\n";
        return 1;
    }
    for (long long value : sos_dp(a, k)) {
        std::cout << value << '\n';
    }
}

Các hàm ở trên giả sử độ dài mảng bằng $2^k$ . Hàm main bảo đảm điều kiện này; khi dùng riêng hàm sos_dp, người gọi phải bảo đảm $k$ hợp lệ, đúng kích thước mảng và không tràn tổng.

Đối chiếu các ví dụ đầu vào

Ví dụ đầu tiên của bản gốc:

2
27 2 2004 0

Kết quả, theo thứ tự mask từ $0$ đến $3$ :

Các ví dụ còn lại giúp phân biệt quy ước mảng và dữ liệu nhập không hợp lệ. Chương trình mới báo lỗi với dữ liệu thiếu hoặc thừa; muốn thêm số $0$ thì phải làm rõ điều đó trước khi tính.

Tình huống từ bản gốc	Cách dùng trong bản này
$k=2$ , dãy `1 2 3 4 5`	Báo thừa dữ liệu; dãy hợp lệ `1 2 3 4` cho `1 3 4 10`
$k=3$ , chỉ có `27 2 2004`	Báo thiếu dữ liệu; thêm năm số $0$ thì được `27 29 2031 2033 27 29 2031 2033`
$k=0$ , không có phần tử nào	Vẫn cần một phần tử $a[0]$ ; nhập `0` rồi `0` thì kết quả là `0`
$k=-1$	Báo lỗi trước khi dịch bit hoặc cấp phát
$k=31$	Vượt giới hạn $20$ của chương trình, báo lỗi trước khi cấp phát

Không thể suy ra rằng mọi trình biên dịch sẽ phát sinh cùng một ngoại lệ cho phép dịch với $k$ âm hoặc quá lớn. Tránh thực hiện phép dịch không hợp lệ ngay từ đầu.

Độ phức tạp và các lỗi dễ gặp

Cách tính	Thời gian	Bộ nhớ ngoài đầu vào
Hai vòng lặp, kiểm tra bằng AND	$O(4^k)$	$O(2^k)$
Đệ quy bốn nhánh	$O(4^k)$	$O(2^k+k)$
Duyệt trực tiếp từng submask	$O(3^k)$	$O(2^k)$
SOS DP theo bit	$O(k2^k)$	$O(2^k)$ với bản sao kết quả

Với $k\geq1$ , vòng DP kiểm tra $k2^k$ mask và thực hiện đúng $k2^{k-1}$ phép cộng. Với $k=0$ , chỉ có một phần tử và không có bước bit nào. Các giới hạn trên dùng mô hình phép toán số nguyên có kích thước cố định; số nguyên lớn cần tính thêm chi phí từng phép cộng.

Không quên tập rỗng: $F[0]=a[0]$
Cày trâu bắt đầu từ mảng kết quả toàn $0$ ; SOS DP bắt đầu từ bản sao của $a$
Nếu $|a[i]|\leq M$ , thì $|F[mask]|\leq2^{\operatorname{popcount}(mask)}M\leq2^kM$ , không phải $kM$
Cấp phát $2^k$ phần tử tăng rất nhanh: riêng $2^{30}$ số nguyên 64 bit cần $8$ GiB, chưa tính mảng khác
Chỉ kiểm tra giới hạn phép dịch là chưa đủ; cần xét cả bộ nhớ và thời gian
Nếu tính theo modulo, áp dụng modulo khi cộng và chuẩn hóa số âm theo yêu cầu bài toán

Tự kiểm tra

Với $a=[5,-2,7,1]$ , hãy tính $F$ bằng tay
Với mask = 5 (101), liệt kê mọi tập con theo thứ tự giảm dần
Nếu mọi $a[mask]=1$ , $F[mask]$ phụ thuộc vào số bit bật như thế nào?

Đáp án

$F=[5,3,12,11]$
101, 100, 001, 000, tức $5,4,1,0$
$F[mask]=2^{\operatorname{popcount}(mask)}$ , vì mỗi bit bật có hai lựa chọn: giữ hoặc bỏ

Nguồn và ghi chú biên soạn

Bản gốc: es.ac.vn/docs/wiki/dp/dp_sos/dp_sos.md và các tệp được include; frontmatter ghi giấy phép Public domain
Tác giả bản gốc: SPyofgame; biên tập viên: tuandebu; người đóng góp: ngpin04
Tham khảo đối chiếu phần bổ sung: USACO Guide: Sum over Subsets DP, gồm duyệt submask và cập nhật tổng theo bit

Bản này giữ các ví dụ số của nguồn, viết lại sơ đồ thành cây chia nhóm nhỏ, sửa đối số bị thiếu trong lời gọi đệ quy và phân biệt lỗi nhập liệu với việc chủ động thêm số $0$ . Các khối MkDocs, trường NULL và lời khẳng định kiểm thử không kèm bằng chứng của bản gốc được thay bằng nội dung đọc được trong trình đọc hiện tại. Đây là bản biên soạn hỗ trợ bằng AI; chưa ghi nhận phê duyệt chuyên môn độc lập cho bản biên soạn này.

Cell	Full width	Full height	Content width × height	Padding X / Y	Borders X / Y
TOP-LEFT
TOP-CENTER
TOP-RIGHT
NAV-LEFT
NAV-CENTER
NAV-RIGHT
MID-LEFT
MID-CENTER
MID-RIGHT
BOT-LEFT
BOT-CENTER
BOT-RIGHT