+4

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 nhaucấu trúc con tối ưuQuy 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-downbottom-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:

{f0=0,f1=1.fi=fi1+fi2;i>2.\begin{cases}f_0 = 0, f_1 = 1.\\ f_i = f_{i - 1} + f_{i - 2}; \forall i > 2. \end{cases}

Yêu cầu: Cho trước số nguyên dương n,n, hãy tìm số Fibonacci thứ n?n?

Input:

  • Chứa duy nhất số nguyên dương nn.

Ràng buộc:

  • 1n1051 \le n \le 10^5.

Output:

  • In ra số fibonacci thứ nn. 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 109+710^9 + 7.

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 f[i]f[i] để lưu lại số fibonacci thứ ii. 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 nn đồ vật khác nhau, đồ vật thứ ii có trọng lượng wiw_i và giá trị viv_i. Bạn mang theo một chiếc túi có tải trọng tối đa là W,W, 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ừ nn đồ vật?

Input:

  • Dòng đầu tiên chứa hai số nguyên dương nn và WW.
  • nn dòng tiếp theo, mỗi dòng chứa hai số nguyên dương wiw_i và viv_i phân tách nhau bởi dấu cách.

Ràng buộc:

  • 1n10001 \le n \le 1000.
  • 1W10001 \le W \le 1000.
  • 1wi,vi100;i:1in1 \le w_i, v_i \le 100; \forall i: 1 \le i \le n.

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 dp(i,j)dp(i, j) 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ứ i,i, và giới hạn trọng lượng của chiếc túi là jj. Xét tới đồ vật thứ i,i, ta sẽ có hai phương án xử lý:

  • Nếu như ta lựa chọn đồ vật thứ ii vào danh sách các vật được chọn, thì giá trị nhận thêm được sẽ là vi,v_i, và giới hạn trọng lượng còn lại của chiếc túi là jwij - w_i. Dĩ nhiên, trường hợp này chỉ xảy ra khi jwij \ge w_i. Tức là ta có giá trị mới là: dp(i1,jwi)+vidp(i - 1, j - w_i) + v_i.
  • Nếu như không lựa chọn đồ vật thứ ii 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ừ 11 tới i1i - 1. Trường hợp này có thể xảy ra cả khi jwij \ge w_ij<wij < w_i. Khi đó ta có giá trị thu được là: dp(i1,j)dp(i - 1, j).

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:

dp(i,j)={dp(i1,j);neˆˊj<wi.max(dp(i1,j),dp(i1,jwi)+wi);neˆˊjwi.dp(i, j) = \begin{cases} dp(i - 1, j); \text{nếu } j < w_i. \\ \text{max}\big(dp(i - 1, j), dp(i - 1, j - w_i) + w_i \big); \text{nếu } j \ge w_i.\end{cases}

Bài toán cơ sở (neo) sẽ là dp(0,j)=0,dp(0, j) = 0, vì ta không thể chọn được vật nào nếu như i=0;i = 0; còn các dp(i,j)dp(i, j) với j<0j < 0 sẽ có giá trị -\infty. Kết quả cần tìm sẽ nằm ở trạng thái: dp(n,W)dp(n, W). Ta sẽ sử dụng một bảng phương án hai chiều dp[i][j]dp[i][j] để 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ó nn 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 n2n-2 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 n=5n=5 và số ghi trên các lá bài là [10,1,50,20,5][10,1,50,20,5]. Nếu lần lượt rút các lá bài có các số 1,201,205050 thì tổng chi phí là:

10×1×5+50×20×5+10×50×5=800010×1×5+50×20×5+10×50×5=8000

Còn nếu rút các lá bài với số 50,2050,2011 thì tổng chi phí sẽ là:

1×50×20+1×20×5+10×1×5=11501×50×20+1×20×5+10×1×5=1150

Yêu cầu: Hãy tìm tổng chi phí nhỏ nhất khi rút hết n2n-2 lá bài?

Input:

  • Dòng đầu tiên chứa số nguyên dương nn - số lá bài.
  • Dòng thứ hai chứa nn số nguyên dương a1,a2,...,ana_1, a_2,..., a_n - số ghi trên lá bài thứ ii.

Ràng buộc:

  • 1n1001 \le n \le 100.
  • 1ai1000;i:1in1 \le a_i \le 1000; \forall i: 1 \le i \le n.

Output:

  • Số nguyên duy nhất là chi phí nhỏ nhất để rút hết n2n - 2 lá bài ở giữa.

Sample Input:

5
10 1 50 20 5

Sample Output:

1150

Ý tưởng

Đặt dp[l][r]dp[l][r] là tổng chi phí nhỏ nhất để rút hết các lá bài trong đoạn [l,r],[l, r], nhưng giữ lại hai lá ở vị trí llrr.

Ta có công thức:

dp[l][r]=min(dp[l][k]+dp[k][r]+ak×al×ar)dp[l][r] = \text{min}\big(dp[l][k] + dp[k][r] + a_k \times a_l \times a_r\big)

<center>

(Do rút hết đoạn từ ll tới kk và đoạn từ kk tới r,r, giữ lại l,rl, rk,k, sau đó lại rút nốt kk để giữ lại ll và rr thì sẽ thêm chi phí là al×ak×ara_l \times a_k \times a_r)

</center>

Cơ sở quy hoạch động sẽ là các dp[i][i+1]=0dp[i][i + 1] = 0dp[i][i]=0dp[i][i] = 0. Còn lại các giá trị dpdp khác đều coi như bằng \infty 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à dp[1][n]dp[1][n].

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

Viblo
Let's register a Viblo Account to get more interesting posts.