Bài toán dãy con cân bằng

Học lập trình

Bài toán dãy con cân bằng

Bài toán dãy con cân bằng (Balanced Subsequence Problem) là một bài toán trong lĩnh vực khoa học máy tính. Đây là một bài toán NP-hard, có nghĩa là không có giải thuật đa thức thời gian để giải quyết bài toán này cho tất cả các trường hợp.

Đề bài: Cho một dãy số nguyên S gồm n phần tử. Tìm một dãy con của S sao cho tổng các phần tử trong dãy con này bằng 0. Nếu có nhiều hơn một dãy con cân bằng, hãy chỉ ra một trong số chúng.

Ví dụ: Cho dãy S = {3, 4, -7, 3, 1, 3, 1, -4, -2, -2}. Một dãy con cân bằng của S là {4, -7, 3}, vì tổng các phần tử trong dãy này là 0. Một dãy con cân bằng khác của S là {3, 1, -4}, vì tổng các phần tử trong dãy này cũng bằng 0.

Để giải quyết bài toán này, chúng ta sử dụng thuật toán quy hoạch động.

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

Thuật toán quy hoạch động giải bài toán dãy con cân bằng có thể được mô tả như sau:

– Khởi tạo một mảng 2 chiều sums có kích thước (n+1) x (n+1) và gán tất cả các phần tử bằng False.

– Gán True cho các phần tử trên đường chéo chính của sums, vì một dãy con chỉ chứa một phần tử có thể được coi là cân bằng.

– Sử dụng hai vòng lặp for để tính giá trị của phần tử sums[i][j]. Phần tử này được tính bằng cách sử dụng các giá trị của sums[i][j-1]sums[i-1][j-1]. Nếu sums[i][j-1] là True hoặc sums[i-1][j-1] là True và tổng của dãy con từ S[i-1] đến S[j-2] cộng với S[j-1] bằng 0, thì sums[i][j] được gán là True.

– Duyệt qua các dãy con của dãy S từ phải sang trái. Nếu tìm thấy dãy con cân bằng đầu tiên, trả về dãy con này. Nếu không tìm thấy, trả về một dãy con rỗng.

Thuật toán này có độ phức tạp thời gian là $O(n^3)$ vì có 3 vòng lặp for lồng nhau.

Cài đặt bài toán dãy con cân bằng với Python

def balanced_subsequence_dp(S):
    n = len(S)
    sums = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        sums[i][i] = True
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            sums[i][j] = sums[i][j - 1] or (sums[i - 1][j - 1] and S[j - 1] + sum(S[i - 1:j - 1]) == 0)
    for i in range(n, 0, -1):
        for j in range(i, n + 1):
            if sums[i][j]:
                return S[i - 1:j]
    return []

S = [3, 4, -7, 3, 1, 3, 1, -4, -2, -2]
res = balanced_subsequence_dp(S)
print(res)

Đầu tiên, ta khởi tạo một bảng hai chiều sums với n+1 hàng và n+1 cột, và gán tất cả các phần tử của bảng bằng False.

Tiếp theo, ta gán True cho các phần tử trên đường chéo chính (sums[i][i]), vì các dãy con chỉ chứa một phần tử có thể được coi là cân bằng.

Sau đó, ta sử dụng hai vòng lặp for để tính toán giá trị của phần tử sums[i][j]. Phần tử này được tính bằng cách sử dụng các giá trị của sums[i][j-1]sums[i-1][j-1]. Nếu sums[i][j-1] là True hoặc sums[i-1][j-1] là True và tổng của dãy con từ S[i-1] đến S[j-2] cộng với S[j-1] bằng 0, thì sums[i][j] được gán là True.

Cuối cùng, ta sử dụng hai vòng lặp for khác để duyệt qua tất cả các dãy con của S và kiểm tra xem dãy con đó có cân bằng hay không. Nếu có, ta trả về dãy con đó.

Cài đặt bài toán dãy con cân bằng với C++

#include <iostream>
#include <vector>

using namespace std;

vector<int> balanced_subsequence_dp(vector<int> S) {
    int n = S.size();
    vector<vector<bool>> sums(n + 1, vector<bool>(n + 1, false));
    for (int i = 0; i <= n; i++) {
        sums[i][i] = true;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            sums[i][j] = sums[i][j - 1] || (sums[i - 1][j - 1] && S[j - 1] + accumulate(S.begin() + i - 1, S.begin() + j - 1, 0) == 0);
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i; j <= n; j++) {
            if (sums[i][j]) {
                return vector<int>(S.begin() + i - 1, S.begin() + j);
            }
        }
    }
    return vector<int>();
}

int main() {
    vector<int> S = {3, 4, -7, 3, 1, 3, 1, -4, -2, -2};
    vector<int> res = balanced_subsequence_dp(S);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    return 0;
}

Thuật toán này cũng sử dụng một bảng 2 chiều sums để lưu trữ các dãy con của dãy số S. Các phần tử trong bảng này được tính toán bằng cách sử dụng hai vòng lặp for để duyệt qua tất cả các dãy con của S.

Sau khi tính toán giá trị của sums, ta sử dụng hai vòng lặp for khác để duyệt qua tất cả các dãy con của S và kiểm tra xem dãy con đó có cân bằng hay không. Nếu có, ta trả về dãy con đó.

Cài đặt bài toán dãy con cân bằng với Pascal

program balanced_subsequence_dp;

type
  T2DBoolArray = array of array of Boolean;

function balanced_subsequence_dp(S: array of Integer): array of Integer;
var
  n, i, j, k: Integer;
  sums: T2DBoolArray;
begin
  n := Length(S);
  SetLength(sums, n+1, n+1);
  
  for i := 0 to n do
  begin
    sums[i][i] := True;
  end;
  
  for i := 1 to n do
  begin
    for j := i to n do
    begin
      sums[i][j] := sums[i][j-1] or (sums[i-1][j-1] and (S[j-1] + Sum(Copy(S, i-1, j-i)) = 0));
    end;
  end;
  
  for i := n downto 1 do
  begin
    for j := i to n do
    begin
      if sums[i][j] then
      begin
        SetLength(Result, j-i+1);
        for k := i to j do
        begin
          Result[k-i+1] := S[k-1];
        end;
        Exit;
      end;
    end;
  end;
  
  SetLength(Result, 0);
end;

var
  S, res: array of Integer;
begin
  S := [3, 4, -7, 3, 1, 3, 1, -4, -2, -2];
  res := balanced_subsequence_dp(S);
  WriteLn('Balanced subsequence: ', res);
end.

Ta khai báo một type mới T2DBoolArray là một mảng 2 chiều các giá trị Boolean.

Trong hàm balanced_subsequence_dp, ta khởi tạo một mảng sums có kích thước (n+1) x (n+1) và gán tất cả các phần tử bằng False.

Sau đó, ta duyệt qua các phần tử trên đường chéo chính và gán chúng bằng True, vì một dãy con chỉ chứa một phần tử có thể được coi là cân bằng.

Tiếp theo, ta sử dụng hai vòng lặp for để tính giá trị của phần tử sums[i][j]. Phần tử này được tính bằng cách sử dụng các giá trị của sums[i][j-1]sums[i-1][j-1]. Nếu sums[i][j-1] là True hoặc sums[i-1][j-1] là True và tổng của dãy con từ S[i-1] đến S[j-2] cộng với S[j-1] bằng 0, thì sums[i][j] được gán là True.

Tham khảo các thuật toán khác

Có nhiều phương pháp để giải quyết bài toán này, bao gồm cách sử dụng thuật toán quy hoạch động (dynamic programming) và thuật toán tham lam (greedy algorithm). Tuy nhiên, với những dãy số lớn, độ phức tạp của các thuật toán này có thể rất cao, do đó cần có phương pháp tối ưu hơn để giải quyết bài toán này.

Phương pháp tối ưu hơn để giải quyết bài toán dãy con cân bằng là sử dụng thuật toán đệ quy và kỹ thuật quay lui (backtracking).

Thuật toán đệ quy sẽ liệt kê tất cả các dãy con của dãy số S, sau đó kiểm tra từng dãy con xem có tổng bằng 0 hay không. Nếu có, thuật toán sẽ dừng và trả về dãy con đó. Nếu không, thuật toán sẽ tiếp tục duyệt tất cả các dãy con khác của S.

Tuy nhiên, để tối ưu hơn, ta có thể sử dụng kỹ thuật quay lui để tránh liệt kê các dãy con không cần thiết. Khi duyệt tới một vị trí trong dãy số S, ta có thể quyết định xem liệu ta nên chọn phần tử này vào dãy con hay không. Nếu chọn, ta sẽ tiếp tục duyệt đến vị trí tiếp theo, nếu không chọn, ta sẽ bỏ qua phần tử này và tiếp tục duyệt đến vị trí tiếp theo. Bằng cách này, ta có thể tránh liệt kê các dãy con không cần thiết và tối ưu hóa thuật toán.

Độ phức tạp của thuật toán này là O(2^n), với n là số phần tử trong dãy số S. Tuy nhiên, với các dãy số có kích thước lớn, ta có thể sử dụng các kỹ thuật tối ưu khác như cắt tỉa nhánh (branch and bound) để giảm độ phức tạp của thuật toán.

Các bạn hãy thử cài đặt các gợi ý về các thuật toán đã nêu ở trên nhé. Chúc các bạn thành công!

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *