Quy hoạch động cho người mới bắt đầu (Phần 3) – Sử dụng vòng lặp for truy vết

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

Quy hoạch động cho người mới bắt đầu (Phần 3) – Sử dụng vòng lặp for 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 for

Các bài toán giải quyết bằng Quy hoạch động sử dụng vòng lặp for với cách tiếp cận Bottom-up, thứ tự thực hiện tính toán các bài toán sẽ là: Tính trước các bài toán con, rồi sau đó sử dụng kết quả của những bài toán này để tính lên cho các bài toán lớn hơn.
Ý tưởng của việc truy vết kết quả như sau:

  • Đầu tiên tìm ra bài toán tối ưu nhất (chính là phần “Kết quả nằm ở đâu” trong bước quy hoạch động ở phần trước), giả sử gọi là bài toán X
  • Sau đó, tìm xem bài toán X được tính bởi bài toán nào? Giả sử bài toán X được tính bởi max(bài toán X1.1, bài toán X1.2) thì ta xem trong hai bài toán đó, giá trị X lớn nhất đạt được bởi bài toán X1.1 hay X1.2. Ta gọi X1 là tên của bài toán đó.
  • Tương tự, từ bài toán X1, ta tìm xem X1 được tính bởi bài toán nào giống bên trên
  • Lần ngược kết qủa cho đến khi gặp 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 1) – Sử dụng vòng lặp for 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ó bảng kết quả quy hoạch động như sau:
quy hoạch động

  • Đầu tiên kết quả nằm ở \(F[5]\), \(F[5] = F[4] + T[5] \). Nghĩa là người 5 tự mua vé của mình. Vậy ta tiếp tục lần ngược kết quả từ \(F[4]\)
  • \(F[4] = F[3] + R[2] \). Nghĩa là người 3 và 4 sẽ mua vé chung. Vậy ta tiếp tục lần ngược kết quả từ \(F[2]\)
  • \(F[2]\) là bài toán cơ sở, \(F[2] = R[1] \). Nghĩa là người 1 và 2 sẽ mua vé chung. 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;
void trace(){
	int m = n;
	while(true){
		if (m == 1) break;
		if (m == 2){
			if (f[m] == r[1]) 
				tr.push_back(2);
			break;
		}
		if(f[m] == f[m-1] + t[m]){
			m = m - 1;
		}else{
			tr.push_back(m);
			m = m - 2;
		}
	}
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) 
		cin >> t[i];
	for(int i = 1; i<n; i++) 
		cin>>r[i];
	f[1] = t[1];
	f[2] = min(t[1]+t[2],r[1]);
	for(int i = 3; i <= n; i++)
		f[i] = min(f[i-1] + t[i], f[i-2] + r[i-1]);
	cout << f[n]<<"\n";
	trace();
	for(int i = tr.size()-1; i>=0; i--){
		cout<<tr[i]<<" ";
	}
	return 0;
}

4. Bài toán Đường đi có tổng lớn nhất

Link đề bài: Đường đi có tổng lớn nhất

Yêu cầu đề bài: Xác định cách để đi từ ô bất kỳ thuộc cột \(1\) đến ô bất kỳ thuộc cột \(n\) sao cho tổng các ô trên đường đi 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 2) – Sử dụng vòng lặp for nâng cao

Truy vết kết quả

Ở đây, ta cần biết đường đi nào là đường đi có tổng các ô là lớn nhất.
Xét ví dụ đề bài, ta có bảng kết quả quy hoạch động như sau:
quy hoạch động

  • Đầu tiên kết quả nằm ở \(F[5][7]\), \(F[5][7] = F[4][6] + A[5][7] \). Nghĩa là ô \((5,7)\) được đi tới bởi ô \((4,6)\) . Vậy ta tiếp tục lần ngược kết quả từ ô \((4,6)\)
  • \(F[4][6] = F[3][5] + A[4][6] \). Nghĩa là ô \((4,6)\) được đi tới bởi ô \((3,5)\) . Vậy ta tiếp tục lần ngược kết quả từ ô \((3,5\)
  • \(F[3][5] = F[2][4] + A[3][5] \). Nghĩa là ô \((3,5)\) được đi tới bởi ô \((2,4)\) . Vậy ta tiếp tục lần ngược kết quả từ ô \((2,4)\)
  • \(F[2][4] = F[3][3] + A[2][4] \). Nghĩa là ô \((2,4)\) được đi tới bởi ô \((3,3)\) . Vậy ta tiếp tục lần ngược kết quả từ ô \((3,3)\)
  • \(F[3][3] = F[2][2] + A[3][3] \). Nghĩa là ô \((3,3)\) được đi tới bởi ô \((2,2)\) . Vậy ta tiếp tục lần ngược kết quả từ ô \((2,2)\)
  • \(F[2][2] = F[1][1] + A[2][2] \). Nghĩa là ô \((2,2)\) được đi tới bởi ô \((1,1)\) . Vậy ta tiếp tục lần ngược kết quả từ ô \((1,1)\)
  • \(F[1][1] = F[1][0] + A[1][1] \). Nghĩa là ô \((1,1)\) được đi tới bởi ô \((1,0)\) . Vậy ta tiếp tục lần ngược kết quả từ ô \((1,0)\)
  • \(F[1,0]\) là trường hợp cơ sở. Kết thúc

Code truy vết

#include<bits/stdc++.h>
#define maxN 105
using namespace std;
const int INF = 1e9;

int n, m;
int a[maxN][maxN], f[maxN][maxN];
int res = -INF;
vector< pair<int, int> > tr;

void trace(){
	//Đầu tiên, ta tìm hàng ở cột n có giá trị lớn nhất
	int p, q = n; //truy vết từ ô (p,q), q=n
	for (int i = 1; i <= m; i++)
		if (res == f[i][n]){
			p = i;
			break;
		}
	while(q > 0){
		//Thêm ô (p,q) vào đường đi
		tr.push_back({p,q});
		if (f[p][q] == f[p-1][q-1] + a[p][q]) p --;
		else if (f[p][q] == f[p+1][q-1] + a[p][q]) p ++;
		q--;
	}
}

void enter()
{
	cin >> m >> n;
	for (int i =1; i <= m; i++){
		for (int j =1; j <= n; j++)
			cin >> a[i][j];
	}
}

void solve(){
	for (int i = 0; i <= m; i++)
		f[i][0] = 0;
	for (int i =0; i <= n; i++)
		f[0][i] = -INF;
	for (int i =0; i <= n; i++)
		f[m+1][i] = -INF;
	for (int j = 1; j <=n; j++){
		for (int i =1; i <= m; i++){
			f[i][j] = max(max(f[i-1][j-1], f[i][j-1]), f[i+1][j-1]) + a[i][j];	
		}
	}
	for (int i = 1; i <=m; i++)
		res = max(res, f[i][n]);
	cout<<res<<"\n";
	trace();
	for(int i = tr.size()-1; i>=0; i--)
		cout<<tr[i].first<<" "<<tr[i].second<<"\n";
}

int main(){
	enter();
	solve();
}

5. Bài toán Xâu con chung dài nhất

Link đề bài: Atcoder Educational DP Contest F – LCS
Yêu cầu đề bài: Xác định xâu con chung (không liên tiếp) dài nhất của hai xâu \(s\) và \(t\) cho trước.

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 2) – Sử dụng vòng lặp for nâng cao

Truy vết kết quả

Ở đây, ta cần biết xâu con chung dài nhất là xâu nào.
Xét ví dụ đề bài, ta có bảng kết quả quy hoạch động như sau:
quy hoạch động

  • Đầu tiên kết quả nằm ở \(F[4][5]\). Vì \(S[4] = T[5]\) nên \(F[4][5] = F[3][4] + 1 \). Nghĩa là xâu S và T có chung ký tự \(S[4]\). Vậy ta tiếp tục lần ngược kết quả từ \(F[3][4]\)
  • Vì \(S[3] \neq T[4]\) nên \(F[3][4] = max(F[3][3], F[2][4]) = F[2][4] \). Vậy ta tiếp tục lần ngược kết quả từ \(F[2][4]\)
  • Vì \(S[2] = T[4]\) nên \(F[2][4] = F[1][3]+1 \). Nghĩa là xâu S và T có chung ký tự \(S[2]\). Vậy ta tiếp tục lần ngược kết quả từ \(F[1][3]\)
  • Vì \(S[1] \neq T[3]\) nên \(F[1][3] = max(F[0][3], F[1][2]) = F[1][2] \). Vậy ta tiếp tục lần ngược kết quả từ \(F[1][2]\)
  • Vì \(S[1] \neq T[2]\) nên \(F[1][2] = max(F[0][2], F[1][1]) = F[1][1] \). Vậy ta tiếp tục lần ngược kết quả từ \(F[1][1]\)
  • Vì \(S[1] = T[1]\) nên \(F[1][1] = F[0][0]+1 \). Nghĩa là xâu S và T có chung ký tự \(S[1]\). Vậy ta tiếp tục lần ngược kết quả từ \(F[0][0]\)
  • \(F[0][0]\) là trường hợp cơ sở. Kết thúc

Code truy vết

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

#define MAXN 3005

int n, m, f[MAXN][MAXN];
string s, t;
string res;
void trace(){
	int i = n;
	int j = m;
	while(i > 0 && j > 0){
		if (s[i] == t[j]){
			res += s[i];
			i --;
			j --;
		}else if (f[i][j] == f[i-1][j]) i--;
		else j--;
	}
}
int main() {
	cin >> s >> t;
	n = s.size();
	m = t.size();
	s = "#" + s;
	t = "#" + t;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if (s[i] == t[j])
				f[i][j] = f[i-1][j-1] + 1;
			else
				f[i][j] = max(f[i-1][j], f[i][j-1]);
		}
	}
	cout<<f[n][m]<<"\n";
	trace();
	reverse(res.begin(), res.end());
	cout<<res;
	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.
Tuy nhiên, khi truy vết kết quả dựa trên code quy hoạch động sử dụng vòng lặp for, sẽ cho ra kết quả không theo thứ tự từ điển (nếu đề bài yêu cầu). Do khi truy vết, ta lần ngược từ cuối về, nếu có nhiều hơn 1 trường hợp cho ra kết quả tốt nhất, ta sẽ không biết ưu tiên trường hợp nào để truy vết tiếp.
Vì vậy, để tìm được thứ tự từ điển nhỏ nhất, phải ưu tiên xét từ trái qua phải, lần kết quả từ đầu. Muốn làm được như vậy ta phải tiếp cận bài toán bằng phương pháp Top-down (sử dụng đệ quy có nhớ). Xem thêm phần 4,5,6 của Series Quy hoạch động cho người mới bắt đầu để biết thêm về phương pháp này nhé!

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 *