Backtrack – duyệt – quay lui cho người mới bắt đầu (Phần 2): Bài tập áp dụng

Đỗ Thị Hồng Ngát 12/12/2023
12
Th12

Backtrack – duyệt – quay lui cho người mới bắt đầu (Phần 2): Bài tập áp dụng

Ở bài viết trước Backtrack – duyệt – quay lui cho người mới bắt đầu (Phần 1) – Sinh nhị phân, sinh hoán vị chúng ta đề cập đến hai thuật toán backtrack để sinh nhị phân và sinh hoán vị – hai thuật toán cốt lõi của mọi bài toán backtrack. Bài viết này sẽ trình bày về cách áp dụng hai thuật toán đó vào việc giải quyết vấn đề.

1. Bài toán liệt kê tập hợp

Phát biểu bài toán

Liệt kê tất cả các tập hợp khác rỗng chứa các số từ \(1\) đến \(n\), theo thứ tự từ điển.
Input

3

Output

1
1 2
1 2 3
1 3
2
2 3
3

Phân tích bài toán

Ta thấy, việc liệt kê tất cả các tập hợp giống như việc liệt kê tất cả các dãy nhị phân, trong đó bit thứ \(i\) trong dãy nhị phân là \(0/1\) tương ứng với không chọn/chọn số thứ \(i\) vào tập hợp.
Với \(n=3\) ta có bảng minh hoạ xâu nhị phân và các tập hợp:

STT Xâu nhị phân Tập hợp Giải thích
1 000 {} Tập hợp rỗng
2 001 {3} Chỉ lấy 3
3 010 {2} Chỉ lấy 2
4 011 {2, 3} Lấy 2 và 3
5 100 {1} Lấy 1
6 101 {1, 3} Lấy 1 và 3
7 110 {1, 2} Lấy 1 và 2
8 111 {1, 2, 3} Lấy 1, 2 và 3

Giải quyết bài toán

Đến đây, việc giải quyết bài toán là vô cùng đơn giản. Ta chỉ việc duyệt ra các nghiệm \(X\) như cách duyệt nhị phân của bài viét trước, sau khi tạo được nghiệm \(X\) ta tiến hành tạo ra tập hợp tương ứng với nghiệm đó và cho vào mảng để lưu trữ (có thể sử dụng vector 2 chiều để lưu).
Để in các tập hợp theo thứ tự từ điển, ta chỉ việc gọi hàm sort như bình thường, vector trong C++ sẽ tự động ưu tiên sắp xếp các mảng theo sự so sánh giống so sánh chuỗi ký tự.
Code minh hoạ việc tạo tập hợp

void makeSet() {
	vector<int> a;
	for(int i = 1; i <= n;i++) 
		if(x[i] == 1)  a.push_back(i);
		res.push_back(a);
}

Cải tiến
Như đã nói ở bài viết trước, trong mọi bài toán backtrack ta nên luôn luôn tìm cách để tạo ra nghiệm đúng (kết quả) trong lúc hàm quay lui chạy mà không cần phải đợi duyệt xong nghiệm \(X\) mới xét lại từng phần tử để tổng hợp ra kết quả .
Bài toán này cũng không ngoại lệ, ta cần duy trì một vector để lưu tập hợp tạo được. Với mỗi phần tử có \(X[i] = 1\), tức là chọn phần tử \(i\) thì ta sẽ thêm phần tử \(i\) vào cuối vector và duyệt đến vị trí kế tiếp. Sau khi duyệt xong thì lại bỏ phần tử cuối của vector đi.
Code liệt kê tập hợp cải tiến

#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> res;
vector<int> a;
void backtrack(int i){
  if(i > n){
    res.push_back(a);
    return;
  }
  //Không chọn phần tử i, vector giữ nguyên
  backtrack(i + 1);

  //Chọn phần tử i, vector thêm phần tử i vào cuối
  a.push_back(i);
  backtrack(i + 1);
  a.pop_back();
}
int main(){
    cin >> n;
    backtrack(1);
    sort(res.begin(), res.end());
    for(auto i: res){
        for(auto j: i){
            cout << j << " ";
        }
        cout << "\n";
    }
}

Ảnh minh hoạ code khi chạy
backtrack

2. Bài toán phân tích số thành tổng các số

Phát biểu bài toán

Cho số nguyên dương \(n\) \((n \le 50) \). Liệt kê tất cả các cách phân tích \(n\) thành tổng các số nguyên nhỏ hơn \(n\), theo thứ tự từ điển.
Input

5

Output

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3

Phân tích bài toán

Ở bài này, ta cần sinh ra các cách tạo tổng \(n\) thoả mãn: Số sau lớn hơn hoặc bằng số trước trong dãy phân tích

Vì các cách tạo tổng có độ dài khác nhau, nên ở mỗi thời điểm backtrack ta chỉ cần quan tâm đến tổng hiện tại là bao nhiêu, và duy trì một vector để lưu các số trong quá trình phân tích

Vậy ta có hàm \(backtrack(s)\) là đang có tổng là \(s\), khi đó, ta sẽ thử các cách thêm các số trong khoảng \(a.back()\) đến \(n-s\). Trong đó \(a.back()\) là phần tử cuối cùng trong vector lưu nghiệm.

Code phân tích n thành tổng các số

#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> res;
vector<int> a;
void backtrack(int s){
  if(s == n){
    res.push_back(a);
    return;
  }
  int mina;
  if (a.size() == 0) mina = 1;
  else mina = a.back();
  for(int i = mina; i <= min(n-s, n-1); i++){
    a.push_back(i);
    backtrack(s + i);
    a.pop_back();
  }
}
int main(){
    cin >> n;
    backtrack(0);
    sort(res.begin(), res.end());
    for(auto i: res){
        for(auto j: i){
            cout << j << " ";
        }
        cout << "\n";
    }
}

3. Bài toán biểu thức

Phát biểu bài toán

Cho xâu \(S\) (chỉ gồm các ký tự \(‘0’\) đến \(‘9’\), độ dài nhỏ hơn \(10\)) và số nguyên \(M\).
Yêu cầu: Không thay đổi thứ tự của các ký tự trong xâu \(S\). Hãy đếm số cách lấy ra một số ký tự trong xâu \(S\) và chèn vào trước nó các dấu \(‘+’\) hoặc \(‘-‘\) để thu được số \(M\) cho trước?
Input

1234
6

Output

4

Giải thích
Có \(4\) cách tạo tổng là \(6\):

  • \(1+2+3\)
  • \(1-2+3+4\)
  • \(-1+3+4\)
  • \(2+4\)

Phân tích bài toán

Mỗi ký tự trong xâu \(S\) sẽ có 3 lựa chọn:

  • Không lấy số này
  • Lấy số này và đặt dấu \(‘-‘\) vào trước
  • Lấy số này và đặt dấu \(‘+’\) vào trước

Ta có hàm \(backtrack (i, sum)\) mang ý nghĩa: Xét đến phần tử thứ \(i\) của xâu \(S\), tổng đã tạo được là \(sum\)

Code bài toán biểu thức

#include <bits/stdc++.h>
using namespace std;
string s;
int n, m, ans;

void backtrack(int i, int sum) {
    if (i == n) {
        if (sum == m) ++ans;
        return;
    }
    backtrack(i + 1, sum + (s[i] - 48));
    backtrack(i + 1, sum - (s[i] - 48));
    backtrack(i + 1, sum);
}

int main() {
    cin >> s >> m;
    n = s.length();
    ans = 0;
    backtrack(0, 0);
    cout << ans;

    return 0;
}

4. Bài toán biểu diễn số ở hệ nhị phân

Phát biểu bài toán

Một số tự nhiên khi biểu diễn trong hệ đếm nhị phân thì chỉ có \(2\) chữ số \(0\) và \(1\).
Yêu cầu: Cho trước số \(n\) và số \(k\) . Hãy cho biết trong các số từ \(1\) đến \(n\) có bao nhiêu số mà khi biểu diễn trong hệ đếm \(2\) có đúng \(k\) chữ số \(1\).

Phân tích bài toán

Thuật toán ngây thơ
Xét từng số trong khoảng từ \(1\) tới \(n\), với mỗi số ta đổi số đó sang hệ nhị phân và đếm xem có bao nhiêu số \(1\) trong biểu diễn.
Cách này có thể dẫn đến TLE một số test lớn, do độ phức tạp là \(O(10^7*20)\).
Thuật toán backtrack

  • Ta có, tương ứng mỗi xâu nhị phân sẽ có một số nguyên ở hệ cơ số \(10\) biểu diễn nó. Thay vì xét các số ở hệ cơ số \(10\) như ở thuật toán trước, ta sinh nhị phân để tạo ra tất cả các số nguyên đó.
  • Nói là sinh nhị phân, nhưng thực chất, ở đây ta không cần phải lưu xâu đó, chỉ cần duy trì số lượng số \(1\) và tính được luôn xâu đó ở hệ cơ số \(10\) là số nào.
  • Để kiểm soát số được tạo ra phải nhỏ hơn số \(n\). Gọi độ dài của xâu biểu diễn số \(n\) dưới dạng nhị phân là \(m\). Các xâu nhị phân được xây dựng phải có độ dài bằng \(m\)

Ta có hàm \(backtrack(i,cnt1, dec)\), xây dựng đến vị trí thứ \(i\) của xâu nhị phân, số lượng số \(1\) đã tạo được là \(cnt1\), giá trị của xâu nhị phân ở dạng thập phân là \(dec\)

Đến đây dễ dàng có thể đặt thêm nhánh cận để giảm số trường hợp không thoả mãn:

  • \(cnt1>k\) => \(return;\)
  • \(dec>n\) => \(return;\)

Code bài toán biểu diễn số ở hệ nhị phân

#include<bits/stdc++.h>
using namespace std;
long long n, k, res, m;
void backtrack(int i, int cnt1, int dec){
  if (cnt1 > k) return;
  if (dec > n) return;
  if (i > m){
    if (cnt1 == k && dec <= n){
      res ++;
    }
    return;
  }
  backtrack(i + 1, cnt1, dec * 2);
  backtrack(i + 1, cnt1 + 1, dec * 2 + 1);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    long long t = n;
    while(t!=0){
      t/=2;
      m++;
    }
    backtrack(1, 0, 0);
    cout << res;
    return 0;
}

5. Một số dấu hiệu của việc dùng Backtrack

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

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 *