Một số bài toán điển hình về quy hoạch động

Dẫn nhập

Ở bài học trước, chúng ta đã có cái nhìn đầu tiên về quy hoạch động. Trong bài học này, chúng ta sẽ cùng nhau làm thử một số bài toán cơ bản về quy hoạch động nhé!

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Tổng quan về Quy hoạch động

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Một số bài toán điển hình về quy hoạch động

Bài toán 1

Đề bài:

Cho n đồ vật, đồ vật thứ i có trọng lượng là a_i và giá trị là b_i. Bạn có một cái balo có thể chứa được khối lượng tối đa là W. Hỏi tổng giá trị lớn nhất của các đồ vật có thể cho vào balo là bao nhiêu?

Input:

• Dòng 1: 2 số nguyên dương n,W lần lượt thể hiện cho số lượng đồ vật và khối lượng tối đa của balo (n,W≤10³)
• Dòng 2…n+1: Mỗi dòng gồm hai số nguyên dương a_i và b_i lần lượt thể hiện cho trọng lượng và giá trị của đồ vật đó (a_i,b_i ≤ 10³)

Output:

• Một số nguyên duy nhất là kết quả của bài toán

Ví dụ:

Giải thích ví dụ:

Hai đồ vật được chọn là đồ vật thứ nhất và đồ vật thứ tư. Khi đó, tổng khối lượng các đồ vật trong balo là 2 + 4 = 6 và tổng giá trị các đồ vật là 4 + 3 = 7.

Ý tưởng

Ta thấy, nếu như ta chọn một đồ vật có khối lượng là k thì khi đó, khối lượng mà balo có thể chứa còn lại là W-k. Ta sẽ cần phải biết xem với khối lượng W-k thì giá trị lớn nhất của các đồ vật mà balo có thể chứa là bao nhiêu. 

Gọi dp[i][j] là giá trị lớn nhất của các đồ vật có thể cho vào balo khi xét đến đồ vật thứ i và trọng lượng balo là j.

Dựa vào những gì mà ta đã nhận xét ở trên, ta rút ra công thức sau:

Công việc tiếp theo của chúng ta sẽ là tìm giá trị cơ sở. Ta thấy khi xét đồ vật đầu tiên thì trước đó hoàn toàn không thể có gì trong balo. Do đó, dp[0][j] = 0 với j từ 0 đến W là giá trị cơ sở. Mặt khác, các giá trị này mặc định bằng 0 nên ta cũng không cần khởi tạo.

Theo các bạn, chuỗi suy luận trên của mình có thiếu sót gì không?

Trong toàn bộ quá trình trên, mình luôn đặt giả thiết là vật thứ i sẽ được chọn. Vậy nếu không chọn vật thứ i mà ta có được kết quả tốt hơn thì sao? Nếu không chọn vật thứ i thì . Do đó, công thức đầy đủ là

Code

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

typedef long long ll;

const int MaxN = 1 + 1e3;

int n, w, a[MaxN], b[MaxN], dp[MaxN][MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> w;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i] >> b[i];
    for(int i = 1 ; i <= n ; ++i)
    for(int j = 1 ; j <= w ; ++j)
    if(j >= a[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);
    else dp[i][j] = dp[i - 1][j];
    int ans = 0;
    for(int i = 1 ; i <= w ; ++i) ans = max(ans, dp[n][i]);
    cout << ans << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Lưu ý: Ở đoạn code trên của mình, phần lấy kết quả, mình phải xét hết tất cả các khối lượng mà balo có thể chứa. Lí do là vì không phải tổng trọng lượng các món đồ lớn nhất thì sẽ cho giá trị lớn nhất (giống như ví dụ).

Với việc sử dụng hai vòng lặp lồng nhau thì độ phức tạp thời gian của bài toán sẽ là O(n×W).

Bài toán 2

Đề bài:

Cho hai xâu s và w chỉ gồm các chữ cái latin in thường. Hãy tìm độ dài xâu con chung dài nhất của hai xâu biết xâu con chung của một xâu có thể thu được bằng cách xoá đi một số phần tử thuộc xâu đó.

Ví dụ: xâu “abd”, “bd” là xâu con của xâu “abcd”.

Input:

• Gồm 2 dòng, mỗi dòng là một xâu chỉ gồm các chữ cái latin in thường, độ dài một xâu không vượt quá 10³

Output:

• Số nguyên duy nhất là độ dài xâu con chung dài nhất của hai xâu

Ví dụ:

Giải thích ví dụ:

Xâu con chung dài nhất của hai xâu trong ví dụ là “bdc”.

Ý tưởng

Giả sử hai xâu s và w có độ dài xâu con chung dài nhất là k. Ta thấy, nếu chèn thêm cùng một ký tự vào cuối hai xâu thì xâu con chung dài nhất sẽ có độ dài là k+1 và kết thúc tại ký tự này. Do đó, khi có hai ký tự trong hai xâu giống nhau thì ta sẽ quan tâm đến xâu con chung dài nhất của xâu phía trước hai ký tự này.

Gọi dp[i][j] là độ dài xâu con chung dài nhất của hai xâu khi ta xét đến ký tự thứ i của xâu s và ký tự thứ j của xâu w.

Ta thấy, nếu s[i]=w[j] thì dp[i][j] = dp[i-1][j-1] + 1, tức là độ dài xâu con chung dài nhất kết thúc tại vị trí i của xâu s và vị trí j của xâu w sẽ là độ dài xâu con chung dài nhất của hai xâu s₁s₂s₃…s_i-1 và w₁w₂w₃…w_j-1 rồi cộng thêm 1.

Còn nếu s[i]≠w[j] thì điều gì sẽ xảy ra? Ta thấy khi này sẽ không thể tồn tại một xâu con chung mà kí tự kết thúc ở xâu s là s_i và ký tự kết thúc ở xâu w là w_j. Do đó, ta sẽ cần quan tâm đến xâu con chung dài nhất mà kí tự kết thúc là ký tự liền trước các kí tự này. Như vậy, ta có công thức dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Trường hợp cơ sở của bài này khá đơn giản. Khi không có bất cứ ký tự nào thì độ dài xâu con chung dài nhất sẽ là 0 hay dp[0][j] = 0 ∀j ≤ |w| và dp[i][0] = 0 ∀i ≤ |s|. Mặc định các giá trị này bằng 0 nên ta không cần khởi tạo.

Như vậy, ta có công thức:

dp[i][j] = dp[i-1][j-1]+1 nếu s_i = w_j dp[i][j] = dp[i-1][j], dp[i][j-1] nếu s_i ≠ w_j  

Code

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

typedef long long ll;

const int MaxN = 1 + 1e3;

int dp[MaxN][MaxN];
string s, w;

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> s;
    cin >> w;
    int n = s.length(), m = w.length();
    s = " " + s;
    w = " " + w;
    for(int i = 1 ; i <= n ; ++i)
    for(int j = 1 ; j <= m ; ++j)
    if(s[i] == w[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
    else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n][m] << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Lưu ý: Có thể một số bạn sẽ cảm thấy thắc mắc dòng code thứ 17 và 18. Lí do mình làm vậy là vì chỉ số các phần tử của xâu là 0,1,2,…,n-1 trong khi công thức của chúng ta bắt đầu từ 1 nên việc cộng thêm một phần tử trống ở phía trước sẽ làm chỉ số các phần tử của xâu bắt đầu từ 1.

Độ phức tạp thời gian của đoạn code trên là .

Bài toán 3

Đề bài:

Có một đoàn khách gồm n người xếp hàng mua vé xem phim. Người thứ i có 2 lựa chọn: mua vé cho mình với giá tiền là a_i, mua vé cho mình và người phía sau (mua cho mình và người thứ i+1) với giá b_i. Hỏi chi phí nhỏ nhất để mua vé cho toàn bộ n người là bao nhiêu?

Input:

• Dòng 1: số nguyên dương n thể hiện cho số người xếp hàng mua vé 
• Dòng 2…n+1: Mỗi dòng gồm 2 số nguyên dương a_i và b_i lần lượt thể hiện cho số tiền phải trả nếu mua vé cho bản thân mình và số tiền phải trả nếu mua vé cho mình và người phía sau.

Output:

• Số nguyên duy nhất là số tiền phải trả ít nhất để mua vé cho tất cả mọi người

Ví dụ:

Giải thích ví dụ:

Người thứ nhất sẽ mua vé cho mình, người thứ hai sẽ mua vé cho mình và người thứ ba, người thứ tư sẽ mua vé cho mình. Tổng chi phí là 3+1+2=6.

Ý tưởng

Bài toán này thực chất khá đơn giản và giống với bài toán thứ nhất.

Gọi dp[i] là chi phí nhỏ nhất để mua vé từ người thứ i đến người thứ n. Ta thấy, nếu người thứ I mua vé cho chính mình thì dp[i] = dp[i+1] + a[i], nếu người thứ i mua vé cho mình và người phía sau thì dp[i] = dp[i+2] + b[i]. Ta chỉ cần so sánh hai chi phí này và lấy giá trị nhỏ hơn.

Do đó, công thức của bài toán này là dp[i][j] = min(dp[i+1] + a[i], dp[i+2] + b[i]).

Trường hợp cơ sở của bài toán này cũng giống như các bài toán ở trên, khi chưa mua vé cho ai thì chi phí mua vé bằng 0 hay dp[n+1] = 0.

Tuy nhiên, bài toán này có một chi tiết khác với các bài toán ở trên. Ta thấy, ở người cuối cùng (i = n), người này sẽ không thể mua vé cho người nào phía sau. Nếu như áp dụng công thức trên với người cuối cùng, trong trường hợp b[n]<a[n], chúng ta sẽ để người cuối cùng mua vé cho cả người thứ n+1 (vô lí). Do vậy, chúng ta sẽ cần xét riêng người thứ n.

Code

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

typedef long long ll;

const int MaxN = 1 + 1e3;

int n, a[MaxN], b[MaxN], dp[MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i] >> b[i];
    dp[n] = a[n];
    for(int i = n - 1 ; i >= 1 ; --i) dp[i] = min(dp[i + 1] + a[i], dp[i + 2] + b[i]);
    cout << dp[1] << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Độ phức tạp thời gian của đoạn code trên là .

Mở rộng

Đọc xong phần trên, liệu có bạn nào thắc mắc: “Tại sao dp[i] phải là chi phí mua vé từ người thứ i đến người thứ n. Nếu ta coi dp[i] là chi phí mua vé từ người thứ nhất đến người thứ i được không?”. Câu trả lời là hoàn toàn có. Hãy thử tự code với cách thứ hai. Đây sẽ là một phần bài tập nhỏ cho các bạn nhé!

Kết luận

Qua bài này chúng ta đã nắm về Một số bài toán điển hình về quy hoạch động

Bài sau chúng ta sẽ đi đến với bài cuối cùng trong khóa học này Một số tài liệu tham khảo và chia sẻ kết thúc

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Một số bài toán điển hình về quy hoạch động dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

CỘNG ĐỒNG HỎI ĐÁP HOWKTEAM.COM

GROUP THẢO LUẬN FACEBOOK