CTDL và giải thuật - Giải thuật tham lam
Một nông dân đang muốn trồng hoa vào khu vườn của mình. Để cho khu vườn trở nên thật màu sắc ông quyết định trồng nhiều loài hoa khác nhau vào khu vườn. Mỗi loài hoa có mội cách trồng khác nhau do đó ông sẽ trồng từng loài hoa vào các ngày liên tiếp nhau. Cháu của ông rất mong chờ được thấy tất cả loài hoa trong khu vườn đều nở hoa trông sẽ tuyệt vời như thế nào. Tuy nhiên mỗi loài hoa lại có thời gian phát triển từ lúc trồng tới lúc nở hoa khác nhau.
Cho dãy a
gồm n
số nguyên dương lần lượt là thời gian phát triển của các loài hoa .Nhiệm vụ của bạn là giúp ông nông dân tìm ra ngày sớm nhất mà tất cả loài hoa đều nở hoa.
Ví dụ:
- Test mẫu 1:
Input Output 4
4 1 3 15
Vớia = [4, 1, 3, 1]
thì kết quả mong muốn là5
:
Giải thích: Ta sẽ trồng các loài hoa như sau:- Ngày thứ
1
: Trồng bông hoa thứ nhất với thời gian nở làa[0] = 4
, sẽ nở vào ngày thứ5
. - Ngày thứ
2
: Trồng bông hoa thứ ba với thời gian nở làa[2] = 3
, sẽ nở vào ngày thứ5
. - Ngày thứ
3
: Trồng bông hoa thứ hai với thời gian nở làa[1] = 1
, sẽ nở vào ngày thứ4
. - Ngày thứ
4
: Trồng bông hoa thứ bốn với thời gian nở làa[3] = 1
, sẽ nở vào ngày thứ4
.Vậy vào ngày thứ5
thì tất cả các bông hoa đều đã nở.
- Ngày thứ
- Test mẫu 2:
Input Output 5
1 1 2 1 16
Vớia = [1, 1, 2, 1, 1]
thì kết quả mong muốn là6
.
Lý thuyết.
Giới thiệu giải thuật tham lam.
Tham lam (hay tham ăn) là một trong những phương pháp phổ biến nhất để thiết kế giải thuật. Nếu bạn đã đọc truyện dân gian thì sẽ có câu chuyện như thế này: trên một mâm cỗ có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước, ăn hết món đó ta sẽ chuyển sang món ngon thứ hai, và chuyển tiếp sang món thứ ba, …
Rất nhiều giải thuật nổi tiếng được thiết kế dựa trên ý tưởng tham lam, ví dụ như giải thuật cây khung nhỏ nhất của Dijkstra, giải thuật cây khung nhỏ nhất của Kruskal, …
Giải thuật tham lam (Greedy Algorithm) là giải thuật tối ưu hóa tổ hợp. Giải thuật tìm kiếm, lựa chọn giải pháp tối ưu địa phương ở mỗi bước với hi vọng tìm được giải pháp tối ưu toàn cục.
Giải thuật tham lam lựa chọn giải pháp nào được cho là tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực hiện lựa chọn đó. Lựa chọn của giải thuật tham lam có thể phụ thuộc vào lựa chọn trước đó. Việc quyết định sớm và thay đổi hướng đi của giải thuật cùng với việc không bao giờ xét lại các quyết định cũ sẽ dẫn đến kết quả là giải thuật này không tối ưu để tìm giải pháp toàn cục.
Bài tập ví dụ:
Một ngân hàng có một số mệnh giá tiền và số lượng tờ mỗi loại được coi như vô hạn, hãy chọn các tờ tiền ít nhất có thể sao cho tổng tờ tiền đó có giá trị đúng bằng k
.
Nếu các mệnh giá lần lượt là [1, 2, 5, 10]
và lượng tiền cho trước là 18
thì giải thuật tham lam thực hiện như sau:
-
Chọn tờ tiền mệnh giá
10
, do đó sẽ còn18 – 10 = 8
. -
Chọn tờ tiền mệnh giá
5
, do đó sẽ còn là3
. -
Chọn tờ tiền mệnh giá
2
, còn lại là1
. -
Cuối cùng chọn tờ tiền mệnh giá
1
và giải xong bài toán.
Bạn thấy rằng cách làm trên là khá ổn, và số lượng tờ tiền cần phải lựa chọn là 4
tờ tiền. Nhưng nếu chúng ta thay đổi bài toán trên một chút thì cũng hướng tiếp cận như trên có thể sẽ không đem lại cùng kết quả tối ưu.
Chẳng hạn, một hệ thống tiền tệ khác có các tờ tiền có mệnh giá lần lượt là [1,8 10]
và lượng tiền cho trước ở đây thay đổi thành 24
thì theo giải thuật tham lam thì số tờ tiền cần chọn sẽ là 6
. Với giải thuật tham lam thì: 10 + 10 + 1 + 1 + 1 + 1
. Trong khi cùng bài toán như trên có thể được xử lý bằng việc chỉ chọn 3
tờ tiền (8 + 8 + 8
).
Do đó chúng ta có thể kết luận rằng, giải thuật tham lam tìm kiếm giải pháp tôi ưu ở mỗi bước nhưng lại có thể thất bại trong việc tìm ra giải pháp tối ưu toàn cục.
Hướng dẫn bài tập.
Ta nhận thấy rằng với ngày thứ k, thì nên trồng cây có thời gian phát triển cao nhất, để ưu tiền những cây phát triển nhanh hơn vào những ngày sau. Ví dụ như a = [1, 2]
thì thứ tự trồng cây phải là [2, 1]
, hai cây sẽ cùng nở vào ngày thứ 3. nếu như trồng theo cách [1, 2] thì tuy cây 1
sẽ nở vào ngày thứ 2
, những cây 2
số nở vào ngày thứ 4
.
Vậy nên với bài toán này ta sẽ sắp xếp thời gian phát trên của nó theo cách giảm dần, và trồng lần lượt nó vào các ngày.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
#include<algorithm>
using namespace std;
void quickSort(int a[], int l, int r){
int p = a[(l+r)/2];
int i = l, j = r;
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r){
quickSort(a, i, r);
}
if (l < j){
quickSort(a, l, j);
}
}
int a[100001];
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
quickSort(a, 0, n-1);
int k = 1;
int max = 0;
for (int i = n-1; i >= 0; i--){
if (a[i] + k > max){
max = a[i] + k;
}
k = k + 1;
}
cout << max;
return 0;
}