Quy hoạch động cho người mới bắt đầu (Phần 6) – Sử dụng đệ quy có nhớ truy vết

Đỗ Thị Hồng Ngát 21/11/2023
21
Th11

Quy hoạch động cho người mới bắt đầu (Phần 6) – Sử dụng đệ quy có nhớ truy vết

Thuật toán quy hoạch động được ưa chuộng bởi vì ban đầu, bài toán có muôn hình vạn trạng và bạn phải suy nghĩ rất nhiều mới tìm ra được lời giải. Không có một công thức chuẩn mực nào áp dụng được cho mọi bài toán. Bởi vì sự phổ biến của nó, bạn bắt buộc phải cực kỳ thuần thục thuật toán này nếu muốn có kết quả tốt trong các cuộc thi.
Series Quy hoạch động cho người mới bắt đầu gồm 6 phần, chia ra làm hai hướng tiếp cận:

  • Sử dụng vòng lặp for – với cách tiếp cận Bottom-up
  • Sử dụng đệ quy có nhớ – với cách tiếp cận Top-down

Series quy hoạch động sẽ đi từ các ví dụ cơ bản đến nâng cao, quy hoạch động 1 chiều, 2 chiều. So sánh và đánh giá hai cách tiếp cận, để từ đó giúp các bạn có cái nhìn tổng quan về Quy hoạch động, hình thành tư duy, lối suy nghĩ khi gặp các bài toán về quy hoạch động.

1. Khi nào thì dùng quy hoạch động

Khi nào thì chúng ta cần đến quy hoạch động? Đó là một câu hỏi rất khó trả lời. Không có một công thức nào cho các bài toán như vậy.
Tuy nhiên, có một số tính chất của bài toán mà bạn có thể nghĩ đến quy hoạch động. Dưới đây là hai tính chất nổi bật nhất trong số chúng:

  • Bài toán có các bài toán con gối nhau (bài toán có công thức quy nạp giống trong toán học): Sử dụng kết quả của bài toán nhỏ để giải quyết bài toán lớn (bài toán chia để trị)
  • Bài toán có cấu trúc con tối ưu

2. Truy vết trong quy hoạch động sử dụng đệ quy có nhớ

Các bài toán giải quyết bằng Quy hoạch động sử dụng đệ quy có nhớ với cách tiếp cận Top-down, thứ tự thực hiện tính toán các bài toán sẽ là: Đi vào bài toán cần tính, nếu bài toán đó sử dụng kết quả của bài toán nhỏ hơn thì tiếp tục đệ quy xuống để tính bài toán con, sau đó tổng hợp lại để tính toán bài toán lớn.

Ý tưởng của việc truy vết kết quả có thể được mô tả bằng cây sau:
quy hoạch động
Bài toán ban đầu sẽ được tính bởi nhiều bài toán con, ta xem bài toán con nào là bài toán tối ưu nhất (để tạo ra được đáp án của bài toán hiện tại). Sau đó nhảy đến bài toán con đó và truy vết tiếp, đến khi đi đến bài toán cơ sở.

3. Bài toán Xếp hàng mua vé

Link đề bài: Xếp hàng mua vé

Yêu cầu đề bài: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Công thức và cách quy hoạch động để tìm kết quả bạn có thể xem thêm ở blog Quy hoạch động cho người mới bắt đầu (Phần 4) – Sử dụng đệ quy có nhớ cơ bản

Truy vết kết quả

Ở đây, ta cần biết những người nào cần ra khỏi hàng và nhờ người phía trước mua hộ vé.
Xét ví dụ đề bài, ta có cây đệ quy như sau:
quy hoạch động

  • Đầu tiên kết quả nằm ở \(dp(1)\), ta thấy nếu đi theo nhánh \(dp(3)\) sẽ cho ra kết quả tốt hơn, nghĩa là người \(2\) rời khỏi hàng, nhờ người \(1\) mua hộ vé sẽ cho ra kết quả tốt hơn, ta thực hiện đệ quy xuống \(dp(3)\)
  • Tại \(dp(3)\), ta thấy đi theo nhánh \(dp(5)\) sẽ cho ra kết quả tốt hơn, nghĩa là người \(3\) và \(4\) sẽ mua vé chung. Vậy ta thực hiện đệ quy xuống \(dp(5)\)
  • \(dp(5)\) chỉ có một nhánh duy nhất là \(dp(6)\), nghĩa là người \(5\) tự mua vé. Thực hiện đệ quy xuống \(dp(6)\)
  • \(dp(6)\) rơi vào điều kiện dừng đệ quy. Kết thúc

Code truy vết

#include <bits/stdc++.h>
using namespace std;
#define MAXN 60005

int n, t[MAXN], r[MAXN], f[MAXN];
vector<int> tr;
int dp(int i){
    if (i > n) return 0;
    if(f[i] != -1) return f[i];
    f[i] = dp(i + 1) + t[i];
    if(i<n)
    	f[i] = min(f[i], dp(i + 2) + r[i]);
    return f[i];
}
//Hàm trace có tham số giống với hàm quy hoạch động
void trace(int i){
	//Điều kiện dừng đệ quy của hàm QHĐ
	if (i>n) return;
	//i==n, chỉ có 1 nhánh duy nhất là người i tự mua vé, ko cần truy vết
	if (i==n) return;
	//Nếu hai nhánh bằng nhau, ta ưu tiên đi theo nhánh mua vé chung của người i và i+1
	//Vì i sẽ tiếp tục tăng, người i+1 ra khỏi hàng sẽ cho ra thứ tự từ điển bé nhất.
	if (dp(i+2) + r[i] <= dp(i+1) + t[i]){
		tr.push_back(i+1);
		trace(i+2);
	}else{
		trace(i+1);
	}
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> t[i];
    for(int i = 1; i < n; i++) cin >> r[i];
    memset(f, 255, sizeof(f));
    cout << dp(1)<<"\n";
    trace(1);
    for(int i = 0; i < tr.size(); i++)
    	cout<<tr[i]<<" ";
    
    return 0;
}

4. Bài toán cái túi – Knapsack

Link đề bài: Atcoder Educational DP Contest D – Knapsack 1
Yêu cầu đề bài: Xác định cách lấy các đồ vật sao cho tổng trọng lượng các đồ vật không quá \(W\) và giá trị của các đồ vật là lớn nhất.
Công thức và cách quy hoạch động để tìm kết quả bạn có thể xem thêm ở blog Quy hoạch động cho người mới bắt đầu (Phần 5) – Sử dụng đệ quy có nhớ nâng cao

Truy vết kết quả

Ở đây, ta cần biết nên lấy những đồ vật nào trong \(n\) đồ vật đã cho sao cho giá trị thu được là lớn nhất.
Xét ví dụ đề bài, ta có cây đệ quy như sau:
quy hoạch động

  • Đầu tiên kết quả nằm ở \(dp(1,0)\), \(dp(1,0) = dp(2,3) + 30 \). Nghĩa là chọn đồ vật \(1\). Vậy ta tiếp tục đệ quy xuống \(dp(2,3)\)
  • \(dp(2,3) = dp(3,3) \). Nghĩa là không chọn đồ vật \(2\). Vậy ta tiếp tục đệ quy xuống \(dp(3,3)\)
  • \(dp(3,3) = dp(4,8) + 60 \). Nghĩa là chọn đồ vật \(3\). Vậy ta tiếp tục đệ quy xuống \(dp(4,8)\)
  • \(dp(4,8) \) rơi vào điều kiện dừng đệ quy. Kết thúc

Code truy vết

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define MAXN 105
#define MAXW 100005
int n, W;
ll w[MAXN],v[MAXN];
ll f[MAXN][MAXW];
vector<int> tr;
ll dp(int i, int t){
	if (i > n) return 0;
	if (f[i][t] != -1) return f[i][t];
	f[i][t] = dp(i+1, t);
	if (t + w[i] <= W)
		f[i][t] = max (f[i][t], dp(i + 1, t + w[i]) + v[i]);
	return f[i][t];
}
void trace(int i, int t){
	if (i > n) return;
	if (t + w[i] <= W && dp(i + 1, t + w[i]) + v[i] == dp(i, t)){
		tr.push_back(i);
		trace(i + 1, t + w[i]);
	}else{
		trace(i + 1, t);
	}
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	cin >> n >> W;
	for(int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	memset(f, -1, sizeof(f));
	cout << dp(1, 0) << "\n";
	trace(1, 0);
	for(int i = 0; i < tr.size(); i++)
		cout << tr[i] << " ";
	return 0;
}

5. Bài toán Dãy con tăng dài nhất

Link đề bài: Dãy con tăng dài nhất (bản dễ)
Yêu cầu đề bài: Xác định dãy con tăng (không liên tiếp) dài nhất của dãy \(a\).

Công thức và cách quy hoạch động để tìm kết quả bạn có thể xem thêm ở blog Quy hoạch động cho người mới bắt đầu (Phần 5) – Sử dụng đệ quy có nhớ nâng cao

Truy vết kết quả

Ở đây, ta cần biết dãy con tăng dài nhất là dãy con nào?.
Lưu ý: ở bài này, phần truy vết không đảm bảo dãy con sau khi tạo ra sẽ là dãy con có thứ tự từ điển nhỏ nhất.

Code truy vết

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1005
int n, a[MAXN], f[MAXN][MAXN];
vector<int> tr;

int dp (int i, int j){
	if (i > n) return 0;
	if (f[i][j] != -1) return f[i][j];
	f[i][j] = dp(i + 1, j);
	if (a[i] > a[j])
		f[i][j] = max(f[i][j], dp(i + 1, i) + 1);
	return f[i][j];
}
void trace(int i, int j){
	if (i > n) return;
	if(dp(i, j) == dp(i + 1, j)){
		trace(i + 1, j);
	}
	else{
		tr.push_back(a[i]);
		trace(i + 1, i);
	}
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	a[0] = -1e9;
	memset(f, -1, sizeof(f));
	cout << dp(1, 0)<<"\n";
	trace(1, 0);
	for(int i = 0; i < tr.size(); i++){
		cout<<tr[i]<<" ";
	}
	return 0;
}

6. Tổng kết

Việc truy vết là rất quan trọng, ta có thể dựa và việc truy vết để debug chương trình quy hoạch động. Nếu code ra kết quả sai, thực hiện truy vết để xem với công thức quy hoạch động hiện tại, tại sao kết quả lại ra như vậy, từ đó dễ dàng chỉnh sửa công thức để phù hợp với bài toán.

Xem thêm các bài trong Series Quy hoạch động cho người mới bắt đầu:

7. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic 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

Unable to display PDF file. Download instead. 

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 *