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

Cấu trúc dữ liệu và giải thuật

0.0 (0 đánh giá)
Tạo bởi Katsu Cập nhật lần cuối 16:13 08-07-2022 789 lượt xem 0 bình luận
Tác giả/Dịch giả: huulam3011 K9
Học nhanh

Danh sách bài học

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ề:

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à ai và giá trị là bi. 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≤103)
  • Dòng 2…n+1: Mỗi dòng gồm hai số nguyên dương ai bi lần lượt thể hiện cho trọng lượng và giá trị của đồ vật đó (ai,b≤ 103)

Output:

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

Ví dụ:

Input Output

4 7

2 4

3 1

5 2

4 3     

7

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:

dp[i][j]=dp[i-1][[j]-b[i]]+a_{i}

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ì dp[i][j]=dp[i-1][j]. Do đó, công thức đầy đủ là

dp[i][j]=MAX(dp[i-1][j], dp[i-1][j-b[i]]+a_{i}) 


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;
}

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 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á 103

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ụ:

Input Output

abcdbc

bdac

3

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 tự thứ i của xâu s và 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 s1s2s3si-1 và w1w2w3wj-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à si và tự kết thúc ở xâu w là wj. 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à 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| 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 swj dp[i][j] dp[i-1][j], dp[i][j-1] nếu s≠ w 

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;
}

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à \small O(|s|\times|w|).


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à ai, mua vé cho mình và người phía sau (mua cho mình và người thứ i+1) với giá bi. 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é \small (2 \leq n \leq 10^5)
  • Dòng 2…n+1: Mỗi dòng gồm 2 số nguyên dương ai bi 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ụ:

Input Output

4

3 2

4 1

3 6

2 1

6

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;
}

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


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ó”.


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ê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.

Nội dung bài viết

Tác giả/Dịch giả

Mình là Nguyễn Hữu Lâm, một người có niềm đam mê rất lớn đối với lập trình. Hiện tại, mình đang là sinh viên Khoa học máy tính của Đại học Bách Khoa Hà Nội. Mong muốn của mình là có thể chia sẻ những kiến thức mà bản thân có cho mọi người, học hỏi, kết bạn với tất cả những người có cùng đam mê với mình.


K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Cấu trúc dữ liệu và giải thuật

Bạn đã từng đau đầu với các cấu trúc stack, queue,.. hoặc cảm thấy cực kỳ khó khăn với các thuật toán sắp xếp, tìm kiếm được sử dụng trong lập trình. Đừng lo lắng! Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu một cách đơn giản nhất về cấu trúc dữ liệu và giải thuật, cũng như giúp bạn nắm rõ hơn về các kiến thức này.

Hãy cùng xem cấu trúc dữ liệu và giải thuật có gì đáng sợ không nhé!

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.