Backtrack – duyệt – quay lui cho người mới bắt đầu (Phần 3): Chia đôi tập

Mục lục

1. Tư tưởng Backtrack: Duyệt chia đôi tập hợp

Ở hai phần 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ị và Backtrack – duyệt – quay lui cho người mới bắt đầu (Phần 2) – Bài tập áp dụng , chúng ta đã đề cập đến việc duyệt toàn bộ các véc tơ nghiệm thoả mãn tiêu chí tối ưu hoặc là đếm số lượng các nghiệm thoả mãn yêu cầu nào đó. Tuy nhiên, phương pháp này còn hạn chế do độ phức tạp lớn \(O( |D|^n )\) với \(D\) là tập các giá trị mà các phần tử của nghiệm \(X\) có thể nhận được, \(|D|\) là số phần tử của tập.

Ở phương pháp Backtrack – duyệt – quay lui: chia đôi tập, ý tưởng là ta sẽ chia đôi nghiệm \(X\) ra để duyệt, sau đó kết hợp lại bằng tìm kiếm nhị phân để tìm ra nghiệm đúng.

Giả thiết: Nghiệm \(X\) có \(n\) phần tử, dạng: \(X = x_1, x_2,…, x_n\)

Bước 1: Chia \(X\) thành 2 nửa:
\(X_1 = x_1, x_2,…, x_{n/2};\)
\(X_2 = x_{n/2+1}, x_{n/2+2},…, x_n\)

Bước 2: Ta tiến hành duyệt như bình thường. Với mỗi nghiệm \(X_1, X_2\) được sinh ra, ta cần lưu lại những giá trị cần thiết để có thể kiểm tra được điều kiện \(X\) thoả mãn.

Bước 3: Sort lại các giá trị đã lưu được ở tập 1

Bước 4: Với mỗi giá trị tìm được ở tập 2, ta tìm kiếm nhị phân các nghiệm tương ứng thoả mãn ở tập 1 để tìm kết quả.

Hãy cùng phân tích các bài toán ví dụ ở các phần sau để hiễu rõ hơn nhé!

2. Bài toán tổng Vector

Nguồn bài: Tổng vector – VNOJ

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

Cho \(n\) \((1 ≤ n ≤ 40)\) vector có dạng \((x, y)\). Đếm số cách chọn một số vector sao cho tổng các vector đã chọn bằng vector \((U, V)\)
Sample Input

Sample Output

Giải thích
Có \(4\) cách chọn sao cho tổng các vector bằng \((2, 5)\):

\((0, 0) + (2, 5)\)
\((-1, 2) + (3, 3)\)
\((0, 0) + (-1, 2) + (3, 3) + (2, 5)\)

Phân tích bài toán theo cách duyệt toàn bộ

Bài toán yêu cầu xây dựng vector nghiệm có \(n\) phần tử, dạng: \(X = x_1, x_2,…, x_n\)

Trong đó \(0 ≤ x_i ≤ 1\) tương ứng là chọn/không chọn vector thứ \(i\)

Điều kiện để \(X\) thoả mãn:

\( \sum_{i=1}^{n}a_i*x_i = U\) và \( \sum_{i=1}^{n}a_i*y_i = V\)

Phân tích bài toán theo cách duyệt cải tiến

Ở bài trước ta đã thống nhất việc: thay vì duyệt ra nghiệm \(X\) rồi mới quay lại tính tổng để kiểm tra, ta sẽ tính tổng các vector đã chọn ngay trong lúc duyệt. Vậy có thể mô tả thuật toán duyệt như sau:

void backtrack(int i, int sumx, int sumy){ 
  if(i > n){
    if(sumx == U && sumy == V) res++;
    return;
  }
  //Không chọn vector thứ i thì sumx, sumy giữ nguyên
  backtrack(i + 1, sumx, sumy);
  //Chọn vector thứ i thì sumx, sumy cộng thêm a[i], b[i]
  backtrack(i + 1, sumx + a[i], sumy + b[i]);
}

Phân tích bài toán theo cách duyệt chia đôi tập hợp

Với cách duyệt toàn bộ ta thấy: để kiểm tra mỗi nghiệm xem có thoả mãn hay không, ta cần biết tổng các vector đã chọn là bao nhiêu?
Vậy các giá trị cần lưu lại sau khi duyệt mỗi nửa của thuật toán duyệt chia đôi chính là tổng của các vector đã chọn.

Các bước làm
Bước 1: Xét ví dụ bên trên, ta sẽ sinh ra hai tập, mỗi tập tương ứng \(2\) phần tử của nghiệm \(X\).

Ở tập thứ nhất: \(X_1 = x_1, x_2\)
Gọi \(X_1\) là danh sách các giá trị lưu được tương ứng với từng nghiệm của \(X_1\).
\(X_1 = [ \{0, 0\}, \{-1, 2\}, \{0, 0\}, \{-1, 2\} ]\)

STT	Nghiệm X	Tổng được sinh ra	Giải thích
1	00	(0, 0)	Không chọn vector nào
2	01	(-1, 2)	Không chọn vector 1, chọn vector 2
3	10	(0, 0)	Chọn vector 1, không chọn vector 2
4	11	(-1, 2)	Chọn cả hai vector 1, 2

Ở tập thứ hai: \(X_2 = x_3, x_4\)
Gọi \(X_2\) là danh sách các giá trị lưu được tương ứng với từng nghiệm của \(X_2\).
\(X_2 = [ \{0, 0\}, \{3, 3\}, \{2, 5\}, \{5, 8\} ]\)

STT	Nghiệm X	Tổng được sinh ra	Giải thích
1	00	(0, 0)	Không chọn vector nào
2	01	(3, 3)	Không chọn vector 3, chọn vector 4
3	10	(2, 5)	Chọn vector 3, không chọn vector 4
4	11	(5, 8)	Chọn cả hai vector 3, 4

Bước 2: Tìm kiếm
Tiến hành sắp xếp lại các giá trị lưu được ở danh sách \(X_1\) theo thứ tự tăng dần.

\(X_1 = [ \{-1, 2\}, \{-1, 2\}, \{0, 0\}, \{0, 0\} ] \)

Xét từng phần tử của \(X_2\)

Phần tử \(1\): \((0, 0)\) – Không chọn cả hai vector \(3, 4\)

Để cả hai nửa đạt được tổng là \((U, V)\) ta cần tìm những cách chọn ở nửa thứ nhất sao cho cách chọn đó sinh ra tổng \((U-0, V- 0)\) hay \((2-0, 5-0) = (2, 5)\).
Đến đây ta sẽ Tìm kiếm nhị phân trên \(X_1\) để đếm xem có bao nhiêu giá trị \({2, 5}\) là xong.
Trong trường hợp này, không có phần tử nào có giá trị \((2, 5)\) ở \(X_1\) cả. Nên ta không có cách nào để tạo được tổng \((2, 5)\) nếu không chọn cả hai vector \(3, 4\).

Phần tử \(2\): \((3, 3)\) – Không chọn vector \(3\), chọn vector \(4\)

Để cả hai nửa đạt được tổng là \((U, V)\) ta cần tìm những cách chọn ở nửa thứ nhất sao cho cách chọn đó sinh ra tổng \((U-3, V- 3)\) hay \((2-3, 5-3) = (-1, 2)\).

Trong trường hợp này, có \(2\) giá trị \((-1, 2)\) ở \(X_1\). Nên sẽ có hai cách chọn tương ứng với nghiệm \(X\) khi được ghép lại là: \(0101, 1101\)

Phần tử \(3\): \((2, 5)\) – Chọn vector \(3\), không chọn vector \(4\)

Để cả hai nửa đạt được tổng là \((U, V)\) ta cần tìm những cách chọn ở nửa thứ nhất sao cho cách chọn đó sinh ra tổng \((U-2, V- 5)\) hay \((2-2, 5-5) = (0, 0)\).
Trong trường hợp này, có \(2\) giá trị \((0, 0)\) ở \(X_1\). Nên sẽ có hai cách chọn tương ứng với nghiệm \(X\) khi được ghép lại là: \(0010, 1010\)

Phần tử \(4\): \((5, 8)\) – Chọn vector \(3\), \(4\)

Để cả hai nửa đạt được tổng là \((U, V)\) ta cần tìm những cách chọn ở nửa thứ nhất sao cho cách chọn đó sinh ra tổng \((U-5, V- 8)\) hay \((2-5, 5-8) = (-3, -3)\).
Trong trường hợp này, không có phần tử nào có giá trị \((-3, -3)\) ở \(X_1\) cả. Nên ta không có cách nào để tạo được tổng \((-3, -3)\) nếu chọn cả hai vector \(3, 4\).

Vậy kết quả là \(4\)

Code bài Vector C++

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

string N;
int n, u,v, x[31], a[31], b[31];
vector<pii> x1,x2;


// X = x1,x2,x3,...,xn
//t là vị trí cuối cùng của tập
void backtrack(int i, int sumx, int sumy, int t){
  if (i > t){
    if(t == n/2) 
      x1.push_back({sumx,sumy});
    else
      x2.push_back({sumx,sumy});
    return;
  }
  backtrack(i + 1, sumx, sumy, t);
  backtrack(i + 1, sumx + a[i], sumy + b[i], t);

}
//trả về số lần xuất hiện của cặp x trong vector x1 => O(2^(n/2))
int find(pii x){
  int cnt = 0;
  for(int i = 0; i < x1.size(); i++)
    if(x == x1[i]) 
      cnt++;
  return cnt;
}
int find1(pii v){
  vector<pii>::iterator low,up;
  //vị trí đầu tiên xh cặp v
  low = lower_bound (x1.begin(), x1.end(), v); 
  //vị trí đầu tiên > cặp v
  up = upper_bound (x1.begin(), x1.end(), v); 
  return up - low;
}
int main() {
  cin >> n;
  
  for(int i = 1; i <= n; i++) 
    cin >> a[i] >> b[i];
  cin >> u >> v;
  backtrack(1, 0, 0, n/2);
  backtrack(n/2+1, 0, 0, n);
  sort(x1.begin(), x1.end());
  int res = 0;
  for(int i = 0; i < x2.size(); i++){
    int xx = u - x2[i].first;
    int yy = v - x2[i].second;
    res += find1({xx,yy});
  }
  cout<<res;
  return 0;
}

Đánh giá độ phức tạp của thuật toán

Thuật toán backtrack chia đôi có độ phức tạp \(O(a^{n/2} * log(a^{n/2} ))\)

Mỗi tập \(X_1, X_2\) sẽ có tối đa \(a^{n/2}\) phần tử. Tại mỗi phần tử ta chặt nhị phân để tìm kiếm trong tập còn lại mất chi phí \(log(a^{n/2} )\)

3. Bài toán 34 đồng xu

Nguồn bài: 34 đồng xu – VNOJ

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

Cho \(34\) đồng xu có giá trị như sau:

\(xu[1]\) có giá trị \(2\)
\(xu[2]\) có giá trị \(3\)
\(xu[3]\) có giá trị \(5\)
\(xu[i]\) có giá trị bằng \(xu[i-1] + xu[i-2] + xu[i-3]\)

Mỗi đồng xu chỉ được dùng tối đa \(1\) lần, hãy tìm cách sử dụng nhiều đồng xu nhất để tạo ra số tiền là \(X\).
Ví dụ

Với số tiền là \(5\) ta sử dụng tối đa là \(2\) đồng xu có giá trị là \(2\) và \(3\)
Với số tiền là \(8\) ta sử dụng tối đa là \(2\) đồng xu có giá trị là \(5\) và \(3\)

Phân tích bài toán theo cách duyệt chia đôi tập hợp

Với cách duyệt toàn bộ ta thấy: để kiểm tra mỗi nghiệm (cách chọn các đồng xu) xem có thoả mãn hay không, ta cần biết tổng số tiền của các đồng đã chọn là bao nhiêu, đồng thời cần biết, số lượng đồng xu đã sử dụng
Vậy các giá trị cần lưu lại sau khi duyệt mỗi nửa của thuật toán duyệt chia đôi chính là tổng của các đồng xu, số lượng đồng xu đã chọn.

Chuẩn bị trước

Mảng \(xu[i]\) lưu giá trị của đồng xu thứ \(i\) với \(1 \le i \le 34 \)
Hai danh sách \(X_1, X_2\) lưu các nghiệm của hai tập sau khi duyệt chia đôi
Sắp xếp lại danh sách \(X_1\) để chuẩn bị cho việc tìm kiếm.

Với mỗi số tiền \(X\) ta cần: Thử từng cặp giá trị \((sum, cnt)\) đã lưu được trong danh sách \(X_2\), cần tìm cặp \((sum’, cnt’)\) trong danh sách \(X_1\) sao cho:

\(sum + sum’ = X\)
\(cnt + cnt’\) lớn nhất

Vì sau khi sắp xếp lại, các phần tử có cùng tổng \((sum)\) sẽ đứng cạnh nhau, phần tử có số lượng xu \((cnt\)) nhỏ nhất sẽ xếp đầu tiên, phần tử có số lượng xu lớn nhất sẽ xếp cuối cùng.
Vậy phần tử cần tìm là phần tử ngay phía trước của phần tử đầu tiên có tổng xu lớn hơn \(X-sum\), tức là phần tử đầu tiên lớn hơn hoặc bằng cặp \(((X – sum) + 1, 0)\)
Có thể dùng hàm lower_bound như sau: \(prev(L1.lower\_bound({X – sum + 1,0}))\)

Code bài 34 đồng xu

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

int n;
int xu[35];
vector<pii> x1,x2;


// X = x1,x2,x3,...,xn
//t là vị trí cuối cùng của tập
void backtrack(int i, int sum, int cnt, int t){
  if (i > t){
    if(t == n/2) 
      x1.push_back({sum, cnt});
    else
      x2.push_back({sum, cnt});
    return;
  }
  backtrack(i + 1, sum, cnt, t);
  backtrack(i + 1, sum + xu[i], cnt + 1, t);

}

int main() {
  n = 34;
  xu[1] = 2;
  xu[2] = 3;
  xu[3] = 5;
  for(int i = 4; i <= n; i++) 
    xu[i] = xu[i - 1] + xu[i - 2] + xu[i - 3]; 
  backtrack(1, 0, 0, n/2);
  backtrack(n/2+1, 0, 0, n);
  sort(x1.begin(), x1.end());
  int test;
  cin >> test;
  for(int i = 1; i <= test; i++){
    int x, res = -1;
    cin >> x;
    for (auto v : x2){
      if (v.first <= x){
        vector<pii>::iterator low = lower_bound(x1.begin(), x1.end(), make_pair(x - v.first + 1,0));
        if ( low != x1.begin() && (*prev(low)).first + v.first == x){
          res = max(res, v.second + (*prev(low)).second);
        }
      }
            
    }
    cout << "Case #" << i << ": " << res << '\n';
  }
  return 0;
}

4. Dấu hiệu của việc dùng Backtrack chia đôi tập

\(n \le 30 – 40\)
Có thể lưu lại tham số nào đó để có thể tìm kiếm trong tập còn lại.

Xem thêm các bài trong Series Backtrack – duyệt – quay lui cho người mới bắt đầu:

5. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Advanced của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn