Bài Toán Phân Chia Tập Hợp (Partition Problem)

Giới thiệu

Bài toán phân chia tập hợp: Cho một tập các số nguyên, xác định xem có thể chia tập đó thành hai tập con có tổng bằng nhau hay không.

Đầu vào và Đầu ra

Đầu vào: Tập số nguyên {3, 1, 1, 2, 2, 1}
Đầu ra: True nếu có thể phân chia. Ở đây là true. Một cách phân chia: {3, 1, 1} và {2, 2, 1} (cả hai tổng = 5).

Thuật toán Quy hoạch động

Nếu tổng các phần tử là lẻ thì trả về false. Ngược lại, tạo bảng partTable[sum/2+1][n+1] với partTable[i][j] = true nếu tập con của j phần tử đầu có tổng bằng i.

checkPartition(set, n)
Begin
    sum := tổng các phần tử
    if sum lẻ then return false
    định nghĩa partTable[sum/2 + 1][n + 1]
    đặt hàng 0 = true, cột 0 = false
    for i = 1 to sum/2 do
        for j = 1 to n do
            partTable[i][j] := partTable[i][j-1]
            if i >= set[j-1] then
                partTable[i][j] := partTable[i][j] OR partTable[i - set[j-1]][j-1]
            done
        done
    return partTable[sum/2][n]
End

Ví dụ C++

#include <iostream>
using namespace std;

bool checkPartition(int set[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += set[i];
    if (sum % 2 != 0) return false;

    bool partTab[sum/2 + 1][n + 1];
    for (int i = 0; i <= n; i++) partTab[0][i] = true;
    for (int i = 1; i <= sum/2; i++) partTab[i][0] = false;

    for (int i = 1; i <= sum/2; i++) {
        for (int j = 1; j <= n; j++) {
            partTab[i][j] = partTab[i][j-1];
            if (i >= set[j-1])
                partTab[i][j] = partTab[i][j] || partTab[i - set[j-1]][j-1];
        }
    }
    return partTab[sum/2][n];
}

int main() {
    int set[] = {3, 1, 1, 2, 2, 1};
    int n = 6;
    if (checkPartition(set, n))
        cout << "Tập hợp có thể chia thành hai tập con tổng bằng nhau.";
    else
        cout << "Không thể chia.";
    return 0;
}

Kết quả

Tập hợp có thể chia thành hai tập con tổng bằng nhau.