Quy hoạch động 7.6: Top-down và Bottom-up
I. Giới thiệu chung
Ta đã biết rằng, giải pháp chúng ta thường sử dụng để giải một bài toán có bản chất đệ quy mà tồn tại các bài toán con gối nhau và cấu trúc con tối ưu là Quy hoạch động. Thông thường, khi cài đặt các bài toán quy hoạch động, chúng ta hay quen với việc đi từ những bài toán nhỏ, dần dần tiến lên tính toán các bài toán lớn hơn dựa vào công thức truy hồi. Cách cài đặt đó được gọi là cách cài đặt bottom-up (đi từ dưới lên trên), hay tabulation. Tuy nhiên, còn một cách cài đặt nữa cũng có thể sử dụng được, đó là cách cài đặt top-down (đi từ trên xuống dưới). Trong cách làm này, ta sẽ sử dụng đệ quy để phân tách bài toán lớn thành các bài toán nhỏ, rồi tính toán kết quả của chúng dựa trên công thức truy hồi, đồng thời lưu luôn kết quả lại vào một bảng phương án để tránh việc phải tính toán lại các bài toán con gối nhau. Điều này sẽ giúp tối ưu thời gian chạy cho giải thuật đệ quy, chính vì vậy, cách làm này còn được gọi là ***đệ quy có nhớ (recursion with memoization)***.
Lược đồ tổng quát của cài đặt top-down có thể mô tả đơn giản như sau:
void top_down_dp({Danh_sách_tham_số})
{
{Nếu đã tiến tới bài toán nhỏ nhất}
return;
{Nếu bài toán hiện tại đã được tính rồi}
return;
{Gọi đệ quy phân tách bài toán hiện tại thành các bài toán con}
}
Phương án cài đặt top-down có ưu điểm là cài đặt ngắn gọn, đơn giản, minh họa ý tưởng tốt, tuy nhiên lại có nhược điểm là tốn bộ nhớ hơn, vì các lời gọi đệ quy sẽ được lưu trữ trong vùng nhớ stack
(nên thời gian chạy của cách cài đặt này sẽ chậm hơn bottom-up một chút xíu). Ngoài ra, các kĩ thuật tối ưu cho quy hoạch động sẽ khó áp dụng hơn khi sử dụng phương án cài đặt top-down. Vì vậy, tùy vào bài toán mà chúng ta sẽ lựa chọn cách cài đặt sao cho phù hợp.
Dưới đây là bảng so sánh về hiệu quả giữa hai cách cài đặt top-down và bottom-up:
Top-down approach | Bottom-up approach |
---|---|
Sử dụng kĩ thuật đệ quy có ghi nhớ | Sử dụng kĩ thuật điền bảng phương án liên tục |
Dựa trên mô hình đệ quy phân rã bài toán lớn thành bài toán con | Sử dụng các vòng lặp để tính toán bài toán lớn dựa trên các bài toán con |
Dễ cài đặt nhưng chạy chậm hơn do phải gọi đệ quy | Cài đặt khó hơn nhưng tốc độ chạy cao hơn |
Khó hơn trong việc áp dụng các kĩ thuật cải tiến | Dễ dàng áp dụng các kĩ thuật cải tiến như cấu trúc dữ liệu |
Sau đây, tôi sẽ trình bày một vài bài toán minh họa cho cách cài đặt top-down để bạn đọc hiểu rõ hơn về cách cài đặt này.
II. Một số bài toán minh họa
1. Dãy Fibonacci
Đề bài
Dãy số Fibonacci được định nghĩa theo công thức:
Yêu cầu: Cho trước số nguyên dương hãy tìm số Fibonacci thứ
Input:
- Chứa duy nhất số nguyên dương .
Ràng buộc:
- .
Output:
- In ra số fibonacci thứ . Do kết quả có thể rất lớn nên chỉ cần đưa ra phần dư của kết quả khi chia cho .
Sample Input:
5
Sample Output:
5
Ý tưởng
Đây là bài toán rất cơ bản mà ai cũng được học cả trong đệ quy lẫn nhập môn quy hoạch động. Ta có thể giải bài toán này bằng đệ quy theo mô hình dưới đây, tuy nhiên thời gian chạy sẽ rất lâu do đây là một bài toán có nhiều bài toán con gối nhau:
int fibo(int n)
{
if (n == 0 || n == 1)
return n;
return fibo(n - 1) + fibo(n - 2);
}
Để cải tiến, ta sẽ dùng bảng phương án để lưu lại số fibonacci thứ . Cài đặt theo phương pháp top-down hay bottom-up trong trường hợp này đều được, vì độ đơn giản là như nhau!
Cài đặt
Kiểu top-down:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int fibo(int n, vector < int > &f)
{
if (n <= 1)
return n;
if (f[n] != 0)
return f[n];
f[n] = (fibo(n - 1) + fibo(n - 2)) % mod;
return f[n];
}
main()
{
int n;
cin >> n;
vector < int > f(n + 1);
cout << fibo(n, f);
}
Kiểu bottom-up:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
main()
{
int n;
cin >> n;
vector < int > f(n + 1);
f[0] = 0; f[1] = 1;
for (int i = 2; i <= n; ++i)
f[i] = (f[i - 1] + f[i - 2]) % mod;
cout << f[n];
}
2. Bài toán cái túi 0 - 1
Đề bài
Cho đồ vật khác nhau, đồ vật thứ có trọng lượng và giá trị . Bạn mang theo một chiếc túi có tải trọng tối đa là nhiệm vụ của bạn là chọn ra các đồ vật để cho vào túi sao cho tổng giá trị của các đồ vật lấy được là lớn nhất có thể.
Yêu cầu: Tìm ra tổng giá trị lớn nhất có thể lấy được từ đồ vật?
Input:
- Dòng đầu tiên chứa hai số nguyên dương và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và phân tách nhau bởi dấu cách.
Ràng buộc:
- .
- .
- .
Output:
- In ra tổng giá trị lớn nhất của các vật lấy được.
Sample Input:
3 50
10 60
20 100
30 120
Sample Output:
220
2 3
Ý tưởng
Đây là bài toán quy hoạch động khá quen thuộc. Tuy nhiên, trong bài viết này chúng ta sẽ tìm hiểu về cách cài đặt top-down cho bài toán trên.
Trước hết, ta xem xét tính đệ quy của bài toán:
Gọi là tổng giá trị lớn nhất thu được khi chọn các đồ vật từ vật thứ nhất tới vật thứ và giới hạn trọng lượng của chiếc túi là . Xét tới đồ vật thứ ta sẽ có hai phương án xử lý:
- Nếu như ta lựa chọn đồ vật thứ vào danh sách các vật được chọn, thì giá trị nhận thêm được sẽ là và giới hạn trọng lượng còn lại của chiếc túi là . Dĩ nhiên, trường hợp này chỉ xảy ra khi . Tức là ta có giá trị mới là: .
- Nếu như không lựa chọn đồ vật thứ vào danh sách các vật được chọn, thì giá trị tối ưu nhận được vẫn sẽ giống như khi lựa chọn trong các đồ vật từ tới . Trường hợp này có thể xảy ra cả khi và . Khi đó ta có giá trị thu được là: .
Mà chúng ta đang cần chọn được giá trị lớn nhất, nên ta có công thức truy hồi:
Bài toán cơ sở (neo) sẽ là vì ta không thể chọn được vật nào nếu như còn các với sẽ có giá trị . Kết quả cần tìm sẽ nằm ở trạng thái: . Ta sẽ sử dụng một bảng phương án hai chiều để lưu trữ lại kết quả trong quá trình tính toán.
Cài đặt
Kiểu top-down:
#include <bits/stdc++.h>
using namespace std;
int top_down_dp(int i, int j, vector < vector < int > > &dp,
vector < vector < int > > &items)
{
// Xử lý trước các trường hợp neo (cơ sở quy hoạch động).
if (j < 0)
return -INFTY;
if (i == 0)
return 0;
// Nếu bài toán con hiện tại đã được tính xong thì không tính lại.
if (dp[i][j] != 0)
return dp[i][j];
// Hai trường hợp không chọn và chọn đồ vật thứ i.
int skip = top_down_dp(i - 1, j);
int take = top_down_dp(i - 1, j - items[i].first) + items[i].second;
// Tính kết quả bài toán hiện tại và lưu luôn vào bảng phương án.
if (j >= items[i].first)
dp[i][j] = max(skip, take);
else
dp[i][j] = skip;
// Trả về kết quả cho bài toán hiện tại.
return dp[i][j];
}
main()
{
int n, W;
cin >> n >> W;
vector < pair < int, int > > items(n + 1);
for (int i = 1; i <= n; ++i)
cin >> items[i].first >> items[i].second;
vector < vector < int > > dp(n + 1, vector < int >(W + 1, 0));
cout << top_down_dp(n, W, dp, items);
return 0;
}
Kiểu bottom-up:
#include <bits/stdc++.h>
using namespace std;
void enter(int &n, int &W, vector < pair < int, int > > items)
{
cin >> n >> W;
items.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> items[i].first >> items[i].second;
}
// Quy hoạch động.
void solution(int n, int W, vector < pair < int, int > > &items)
{
vector < vector < int > > dp(n + 1, vector < int >(W + 1, 0));
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= W; ++j)
{
dp[i][j] = dp[i - 1][j];
if (j >= items[i].first)
dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i].first] + items[i].second);
}
// In kết quả.
cout << dp[n][W] << endl;
}
main()
{
int n, W;
vector < pair < int, int > > items;
enter(n, W, items);
solution(n, W, items);
return 0;
}
3. Rút bài
Đề bài
Trên bàn có lá bài, trên mỗi lá bài có ghi một số nguyên dương. Các quân bài được xếp thành một chồng. Người ta lần lượt rút các lá bài bên trong chồng bài (tức là trừ lá bài trên cùng và dưới cùng), mỗi lần rút một quân cho đến khi chỉ còn lại lá trên cùng và dưới cùng. Chi phí để rút một lá bài là tích của ba số nguyên ghi trên lá bài được rút, lá bài ngay trên lá bài được rút và lá bài ngay dưới lá bài được rút. Đến khi rút hết lá bài ở giữa, ta có tổng chi phí rút bài. Mỗi trình tự rút bài khác nhau sẽ có tổng chi phí khác nhau.
Ví dụ: Với và số ghi trên các lá bài là . Nếu lần lượt rút các lá bài có các số và thì tổng chi phí là:
Còn nếu rút các lá bài với số và thì tổng chi phí sẽ là:
Yêu cầu: Hãy tìm tổng chi phí nhỏ nhất khi rút hết lá bài?
Input:
- Dòng đầu tiên chứa số nguyên dương - số lá bài.
- Dòng thứ hai chứa số nguyên dương - số ghi trên lá bài thứ .
Ràng buộc:
- .
- .
Output:
- Số nguyên duy nhất là chi phí nhỏ nhất để rút hết lá bài ở giữa.
Sample Input:
5
10 1 50 20 5
Sample Output:
1150
Ý tưởng
Đặt là tổng chi phí nhỏ nhất để rút hết các lá bài trong đoạn nhưng giữ lại hai lá ở vị trí và .
Ta có công thức:
<center>
(Do rút hết đoạn từ tới và đoạn từ tới giữ lại và sau đó lại rút nốt để giữ lại và thì sẽ thêm chi phí là )
</center>Cơ sở quy hoạch động sẽ là các và . Còn lại các giá trị khác đều coi như bằng ban đầu.
Do bài toán này khá khó để xác định thứ tự cập nhật quy hoạch động, nên các bạn hãy ưu tiên sử dụng phương án đệ quy có nhớ hơn là quy hoạch động thông thường.
Kết quả cuối cùng là .
Cài đặt
Kiểu top-down:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 100 + 10, INFTY = 1e18;
void enter(int &n, vector < int > &a)
{
cin >> n;
a.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
int top_down_dp(int l, int r, vector < vector < int > > &dp,
vector < int > &a)
{
if (l + 1 == r || l >= r)
return 0;
if (dp[l][r] != INFTY)
return dp[l][r];
for (int k = l + 1; k <= r - 1; ++k)
{
int t1 = top_down_dp(l, k, dp, a);
int t2 = top_down_dp(k, r, dp, a);
dp[l][r] = min(dp[l][r], t1 + t2 + a[k] * a[l] * a[r]);
}
return dp[l][r];
}
void solution(int n, vector < int > &a)
{
vector < vector < int > > dp(n + 1, vector < int >(n + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = INFTY;
cout << top_down_dp(1, n, dp, a);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
vector < int > a;
enter(n, a);
solution(n, a);
return 0;
}
Kiểu bottom-up:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INFTY = 1e18;
void enter(int &n, vector < int > &a)
{
cin >> n;
a.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
void solution(int n, vector < int > &a)
{
vector < vector < int > > dp(n + 1, vector < int >(n + 1, INFTY));
for (int i = 1; i <= n; ++i)
{
dp[i][i] = 0;
if (i < n)
dp[i][i + 1] = 0;
}
for (int r = 3; r <= n; ++r)
for (int l = r - 2; l >= 1; --l)
for (int k = l + 1; k < r; ++k)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[r] * a[k]);
cout << dp[1][n];
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
vector < int > a;
enter(n, a);
solution(n, a);
return 0;
}
III. Tài liệu tham khảo
All Rights Reserved