Sơ lược về bài toán Subset sum và ứng dụng

[NhanSu]

Chào các bạn. Hôm nay, mình xin giới thiệu với các bạn sơ lược về bài toán Subset sum. Để giới thiệu đầy đủ sẽ rất dài và vượt quá khả năng của mình, chắc phải nhờ các bạn chuyên ngành khoa học máy tính, do vậy mình chỉ giới thiệu sơ lược và nêu ứng dụng để giải bài toán trong thực tế. Bài toán như sau: cho mảng n số nguyên dương a(1 to n) và số k, hãy xác định tồn tại hay không một tập con của a có tổng bằng k, tìm 1 bộ số nếu có? Một ứng dụng thường gặp đối với các bạn làm sổ sách số liệu (hình như các bác kế toán gọi là "bốc thuốc"): sếp chi một khoản tiền k đồng mà lý do không thể đưa vào sổ sách được, các bác kế toán sẽ tách ra thành các nội dung chi hợp lý có tổng = k (các nội dung này nằm trong danh mục có sẵn được chi của công ty và có chi phí cụ thể, đây chính là mảng a(1 to n)).
Ví dụ a=[2, 5, 9, 20, 30] , k =35, tồn tại bộ số [5, 30] có tổng bằng k.
(Còn tiếp...)

 

[NhanSu]

Bài toán Subset sum có nhiều cách giải nhưng khi n và k là các số lớn thì thời gian giải sẽ rất lớn. Trước tiên, ta tìm xem có tồn tại bộ số có tổng bằng k không. Lời giải dễ thấy nhất là dùng đệ quy, ta phát biểu bài toán như sau: cho mảng a(1 to n), xây dựng hàm SS(p, q) trả về TRUE nếu tồn tại tập con của p phần tử đầu tiên của mảng a có tổng bằng q
- Trường hợp p = 1: nếu a(1) = k, SS = TRUE, ngược lại trả về FALSE
- Nếu 1<p<=n: có 2 khả năng:
+ Nếu SS(p-1, q-a(p)) = TRUE tức là có tập con của a(1 to p-1) có tổng bằng q-a(p) khi đó tập con này thêm a(p) sẽ có tổng = q
+ Nếu SS(p-1,q)=TRUE thì tồn tại tập con của a(1 to p-1) có tổng bằng q, đây cũng là tập con của a(1 to p), do đó SS(p, q)=TRUE
Kết hợp 2 khả năng trên ta được SS(p, q) = SS(p-1, q - a(p)) Or SS(p-1, q) đây chính là lệnh gọi đệ quy.
Từ phân tích trên, ta có thể code bằng đệ quy, chú ý đệ quy chỉ áp dụng với n nhỏ, nếu n lớn sẽ tràn stack.

Option Explicit
Private a()
Function DQ(p As Long, q As Long) As Boolean
    If p = 1 Then
        DQ = (a(1) = q)
    Else
        DQ = DQ(p - 1, q - a(p)) Or DQ(p - 1, q)
    End If
End Function

Sub SS_DQ()
    Dim tmp(), n&, k&, i&
    tmp = Range("A2", Range("A2").End(xlDown)).Value
    n = UBound(tmp)
    k = Range("A1").Value
    ReDim a(1 To n)
    For i = 1 To n
        a(i) = tmp(i, 1)
    Next
    MsgBox DQ(n, k)
End Sub

Bạn cần đăng nhập để thấy hình ảnh

Trong file, A1=50 =k, mảng các số A2:A19

Bạn cần đăng nhập để thấy link

 

[NhanSu]

Cách giải đệ quy ngắn gọn nhưng thời gian chạy rất lâu với n lớn và dễ lỗi stack overflow. Sau đây mình sẽ giải bằng quy hoạch động. Mục đích của quy hoạch động là xây dựng mảng DP(0 to n, 0 to k) trong đó mỗi phần tử DP(p, q) chứa giá trị Boolean là sự tồn tại bộ số là tập con của {0, a(1 to p)} có tổng bằng q (DP(p, q) cũng chính bằng SS(p, q) ở trên nhưng ta tìm bằng phuơng pháp khác). Tương tự bài trên, ta cũng thấy
DP(p, q) = DP(p-1, q-a(p)) Or DP(p-1, q) nhưng khác với bài 2 dùng đệ quy, phương pháp quy hoạch động sẽ lưu tất cả giá trị trung gian vào mảng nên tốc độ sẽ nhanh hơn và không bị tràn stack.
Dưới đây là code áp dụng DP để tìm xem có đáp án không và xuất ra 1 đáp án nếu có:

Option Explicit
Private InputArr() As Long
Private SubSet() As Boolean

Sub FillArray(Goal As Long, n As Long)
    Dim i As Long, j As Long
    
    SubSet(InputArr(0), 0) = False
    For j = 1 To n
        SubSet(InputArr(0), j) = True
    Next
       
    For i = InputArr(0) + 1 To Goal
        SubSet(i, 0) = False
        For j = 1 To n
            If i = InputArr(j - 1) Then
                SubSet(i, j) = True
            ElseIf i >= InputArr(j - 1) + InputArr(0) Then
                SubSet(i, j) = SubSet(i, j - 1) Or SubSet(i - InputArr(j - 1), j - 1)
            Else
                SubSet(i, j) = SubSet(i, j - 1)
            End If
        Next
    Next
End Sub
Sub test()
    Dim Arr(), i As Long, x As Long, Goal As Long, NUM As Long, Sum As Long, t
    
    Columns(2).Clear
    Goal = CLng([D1])
    NUM = Range("A" & Rows.Count).End(xlUp).Row
    ReDim InputArr(0 To NUM - 1)
    Arr = Range("A1").Resize(NUM).Value
    If Goal < Arr(1, 1) Then Exit Sub
    For i = 0 To NUM - 1
        InputArr(i) = Arr(i + 1, 1)
        Arr(i + 1, 1) = 0
        Sum = Sum + InputArr(i)
    Next
    If Goal > Sum Then Exit Sub
    
    ReDim SubSet(InputArr(0) To Goal, 0 To NUM)
    t = Timer
    FillArray Goal, NUM
    If SubSet(Goal, NUM) Then
        x = Goal
        For i = NUM To 1 Step -1
            If SubSet(x, i - 1) Then
                Arr(i, 1) = 0
            Else
                Arr(i, 1) = 1
                x = x - InputArr(i - 1)
                If x = 0 Then Exit For
            End If
        Next
    
        MsgBox Timer - t
    Else
        MsgBox Timer - t
        Exit Sub
    End If
    Range("B1").Resize(NUM) = Arr
End Sub

Trong file đính kèm, dữ liệu cột A đã sort tăng dần, ô D1 chứa số k, kết quả ở cột B bằng 1 nếu số tương ứng ở cột A nằm trong tập con (nếu có đáp án).

Bạn cần đăng nhập để thấy link

 

[NhanSu]

Ở bài 3 ta thấy, sử dụng quy hoạch động (DP) thì độ phức tạp phụ thuộc vào cả n và k, mảng Subset thường có kích thước (1+n)*(1+k)*2 bytes (2 bytes là sizeof boolean), vì thế nếu k khoảng 10^7, n khoảng 1000 thì kích thước mảng Subset sẽ khoảng 20GB và VBA sẽ không chạy được.
Để khắc phục và tăng tốc độ, mình đã code trên C# và sử dụng BitArray để lưu mảng Subset. BitArray sử dụng 1 bit để lưu trữ giá trị Bool (1 bytes trong C#) nên thu gọn được kích thước 8 lần so với dùng mảng Bool (so với mảng boolean VBA là 16 lần). Một điểm lợi nữa của C# là có thể khởi tạo mảng lớn hơn so với VBA. Với VBA 64 bit, mảng kích cỡ tối đa khoảng 4GB trong khi dùng C#, mình đã thấy chương trình kéo lên hơn 12GB (máy mình 16GB ram).
Mình upload file cài đặt

Bạn cần đăng nhập để thấy link

, giải nén vào 1 thư mục rồi chạy setup, chương trình sử dụng .NET 5 nên khi cài có thể mất vài phút download thư viện. Trong folder có 2 file a.txt và b.txt là các file input và output.

Bạn cần đăng nhập để thấy hình ảnh

Trong file a.txt, dòng đầu chứa tổng mong muốn (số k), các dòng dưới là số trong mảng đã sort tăng dần, nếu copy từ Excel vào thì cần chuyển định dạng các số về general (chọn cột, bấm Ctrl-Shift-~) để loại bỏ các dấu phân cách hàng nghìn.

Bạn cần đăng nhập để thấy hình ảnh

Kết quả khi chạy chương trình (file Subsetsum core.exe) tìm thấy bộ số theo yêu cầu, nếu không thấy thì chương trình báo No subset with given sum.

Bạn cần đăng nhập để thấy hình ảnh

Đây là kết quả trong file b.txt.
Dữ liệu test trong file a.txt nhỏ (n=52, k=1.509.950), chương trình chạy khoảng 1s trong khi dùng VBA ở bài 3 hết 5,5s còn đệ quy ở bài 2 cả 10 phút chưa xong. Tốc độ và bộ nhớ sẽ tăng rất nhanh nếu tăng n và đặc biệt là tăng k. Đối với bài toán "bốc thuốc" thì k là số tiền, tùy quy mô nhưng ít nhất cũng 10m. Mình đã test với dữ liệu k khoảng 100 triệu, n khoảng 300 thì thời gian chạy khoảng 20 phút.

 

[NhanSu]

Kết thúc: loạt bài này mình chủ yếu đưa ra công cụ để các bạn có thể ứng dụng vào công việc, nhất là các bạn làm kế toán hoặc có người yêu làm kế toán (đảm bảo bạn gái phục sát đất, tất nhiên trừ các bạn gái đã là bậc thầy về bốc thuốc rồi). Trong các bài trên có vấn đề gì thắc mắc mời các bạn tham gia thảo luận thêm cho vui. Những vấn đề sâu hơn về thuật toán có lẽ nằm ngoài khuôn khổ của diễn đàn nhưng vẫn hoan nghênh các bạn chia sẻ.