Sum over Subsets (SOS) Dynamic Programming ใน C++

บทนำ

โจทย์: กำหนดอาร์เรย์ A ขนาด 2ⁿ คำนวณ F(x) = Σ A[i] สำหรับทุก i ที่เป็น subset ของ x (i & x == i) สำหรับทุก x = 0..2ⁿ-1

ตัวอย่าง

A = [5, 7, 1, 9], n = 2 x=0 (00): subset={00} → F=5 x=1 (01): subset={00,01} → F=5+7=12 x=2 (10): subset={00,10} → F=5+1=6 x=3 (11): subset={00,01,10,11} → F=5+7+1+9=22

SOS DP Recurrence

DP[mask][i] = ผลรวมของ subset ของ mask ที่พิจารณาเฉพาะบิต 0..i - ถ้าบิต i ของ mask = 1: DP[mask][i] = DP[mask][i-1] + DP[mask^(1<

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

const int N = 1000;

void SumOverSubsets(int a[], int n) {
    int sum[1 << n] = {0};
    int DP[N][N];
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                if (j == 0) DP[i][j] = a[i] + a[i ^ (1 << j)];
                else DP[i][j] = DP[i][j - 1] + DP[i ^ (1 << j)][j - 1];
            } else {
                if (j == 0) DP[i][j] = a[i];
                else DP[i][j] = DP[i][j - 1];
            }
        }
        sum[i] = DP[i][n - 1];
    }
    for (int i = 0; i < (1 << n); i++) cout << sum[i] << "\t";
}

int main() {
    int A[] = {5, 7, 1, 9};
    int n = 2;
    cout << "The sum over subsets is \t";
    SumOverSubsets(A, n);
    return 0;
}

ผลลัพธ์

The sum over subsets is 5 12 6 22

ความซับซ้อน

เวลา: O(n × 2ⁿ), พื้นที่: O(n × 2ⁿ) เร็วกว่า Brute Force O(3ⁿ) หรือ O(4ⁿ) มาก

สรุป

SOS DP เป็นเทคนิคขั้นสูงสำหรับปัญหา Subset Sum / Bitmask DP ใช้ใน Competitive Programming บ่อยมาก