Các dạng bài sử dụng thuật toán tham lam – Greedy Algorithm Problems
Thuật toán tham lam là gì Thuật toán tham lam hay chính xác hơn là một kĩ thuật (technique) tương tự quy hoạch động hay chia để trị cũng là những kĩ thuật luôn chọn quyết định tốt nhất ở thời điểm hiện tại hay lựa chọn tối ưu cục bộ và hy vọng rằng quyết định đó sẽ dẫn tới giải pháp tối ...
Thuật toán tham lam là gì
Thuật toán tham lam hay chính xác hơn là một kĩ thuật (technique) tương tự quy hoạch động hay chia để trị cũng là những kĩ thuật luôn chọn quyết định tốt nhất ở thời điểm hiện tại hay lựa chọn tối ưu cục bộ và hy vọng rằng quyết định đó sẽ dẫn tới giải pháp tối ưu toàn cục của bài toán. Do đó nó khác với quy hoạch động luôn duyệt hết và đảm bảo tìm thấy lời giải, với quy hoạch động mọi quyết định đều phải dựa vào quyết định của bài toán con đã được giải ở bước trước đó và có thể xét lại đường đi của bước trước hướng tới lời giải. Giải thuật tham lam quyết định sớm và thay đổi đường đi thuật toán theo quyết định đó, và không bao giờ xét lại các quyết định cũ. Chính vì vậy trong nhiều bài toán tham lam có thể không cho kết quả chính xác nhất.
Tham lam không dựa vào quyết định của bài toán trước đó để đưa ra quyết định mà tại mỗi bước nó tự ra quyết định tối ưu cục bộ và quyết định này sẽ quyết định đường đi của mọi bước tiếp theo, quyết định này cũng không thể quay lại hay phục hồi.
https://vi.wikipedia.org/wiki/Giải_thuật_tham_lam
Ưu điểm của tham lam
- Thuật toán tham lam dễ dàng tiếp cận với các bài toán đặc biệt là các bài toán đồ thị và NP-đầy đủ mặc dù không đảm bảo tìm ra được lời giải tối ưu tuy nhiên nó vẫn trở nên rất hữu ích bởi việc dễ dàng thiết kế để cho ra lời giải ước lượng (tương đối chính xác).
- Độ phức tạp của tham lam là khá rõ ràng từ đó bạn có thể xem xét độ phù hợp của tham lam đối với thời gian chạy của bài toán cần giải quyết.
- Nếu có thể chứng minh rằng một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ trở thành phương pháp được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như quy hoạch động.
Nhược điểm
- Rất khó để hiểu hay chứng minh 1 lời giải tham lam là kết quả tối ưu ngay kể cả khi nó đưa ra lời giải tối ưu
- Đa số các thuật toán tham lam là không chính xác.
Bài toán trồng cây
Problem: 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ó 1 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. 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.
Trong kho của ông nông dân hiện tại có một số loài hoa
| Loài hoa | Thời gian hoa sẽ nở | |
|---|---|---|
| 1 | Hoa hồng | 3 |
| 2 | Hoa lan | 4 |
| 3 | Hoa cúc | 2 |
| 4 | Hoa mười giờ | 1 |
Idea: Mỗi cách trồng là 1 hoán vị của N (N là số loài hoa) với mỗi cách trồng sẽ cần một thời gian chờ để tất cả loài hoa đều nở. Ví dụ
Với hoán vị 1234:
- Trồng hoa hồng (1) vào ngày thứ 1 => sau 1 + 3 = 4 ngày hoa sẽ nở
- Trồng hoa lan (2) vào ngày thứ 2 => sau 2 + 4 = 6 ngày hoa sẽ nở
- Trồng hoa cúc (3) vào ngày thứ 3 => sau 3 + 2 = 5 ngày hoa sẽ nở
- Trồng hoa mười giờ (1) vào ngày thứ 4 => sau 4 + 1 = 5 ngày hoa sẽ nở
Thời gian sớm nhất tất cả loài hoa đều nở là ngày thứ 7
Với hoán vị 2134:
Thời gian sớm nhất tất cả loài hoa đều nở là ngày thứ 6
Dễ thấy với các loài hoa có thời gian phát triển lâu cần được trồng trước các loài hoa phát triển nhanh (tham lam) => Sort theo thứ tự giảm dần thời gian phát triển của hoa để sinh ra hoán vị tốt nhất.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 | sort(a,a+n); intres=1,j=1; for(inti=n-1;i>=0;i--) { a[i]+=j++; if(res<a[i]) res=a[i]; } res++; printf("%d
",res); |
Ngoài ra, còn có 1 số bài toán tham lam tương tự dạng này nữa:
https://www.hackerrank.com/challenges/angry-children/problem
https://www.hackerrank.com/challenges/greedy-florist/problem
Bài toán sắp xếp công việc
Problem: Ngày CN, Minh có rất nhiều dự định muốn hoàn thành chẳng hạn như làm bài tập lớn môn A, viết bài viblo, ôn tập môn B, nghe nhạc, chạy bộ, … Mỗi công việc đều có thời gian lý tưởng để bắt đầu và kết thúc của nó. Tuy nhiên có một số công việc không thể cùng hoàn thành bởi công việc trước chưa kết thúc công việc sau đã bắt đầu. Chẳng hạn
| Task | start | end |
|---|---|---|
| làm btl môn A | 8 (h) | 10 (h) |
| viết bài viblo | 9 | 11 |
| ôn tập môn B | 10 | 12 |
| nghe nhạc | 14 | 15 |
| chạy bộ | 17 | 18 |
Chúng ta không thể hoàn thành cả 2 task là viết bài viblo và làm btl môn A hay ôn tập môn B. Nếu chọn thực hiện viết bài viblo bạn chỉ có thể hoàn thành 3/5 task trong khi nếu không chọn viết bài viblo bạn có thể hoàn thành 4/5 task.
Chúng ta cần giúp Minh tìm ra được số task có thể hoàn thành nhiều nhất mỗi khi ngày CN tới.
Idea: Dễ thấy để chọn được ra nhiều task nhất ta sẽ chọn ra task có thời gian kết thúc sớm nhất và đảm bảo thời gian bắt đầu của nó muộn hơn thời gian kết thúc của các task được chọn trước đó. Riêng với task đầu tiên ta chỉ cần chọn ra task kết thúc sớm nhất.
Ý tưởng tham lam này cũng đã được chứng minh là đúng trong mọi TH tuy nhiên mình nhớ được link để trích dẫn.
Implementation:
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #define MAX 100009 ints[MAX],e[MAX]; intN; voidswap(inti,intj) { inttmp=e[i]; e[i]=e[j]; e[j]=tmp; tmp=s[i]; s[i]=s[j]; s[j]=tmp; } voidqsort(inta[],intstart,intend) { // quicksort theo thời gian kết thúc if(start>=end) return; intindex=rand()%(start-end)+start; intpivot=a[index]; intk=start-1; swap(index,end); for(inti=start;i<end;i++) if(a[i]<pivot) { k++; swap(i,k); } k++; swap(k,end); qsort(a,start,k-1); qsort(a,k+1,end); } voidproc() { // xử lí intres=1; intend=e[0]; for(inti=1;i<N;i++) { if(e[i]==end) continue; if(s[i]>=end) { res++; end=e[i]; } } printf("%d
",res); } intmain() { scanf("%d",&N); for(inti=0;i<N;i++) scanf("%d %d",&s[i],&e[i]);//nhập vào thời bắt đầu và kết thúc của task i qsort(e,0,N-1);// sort theo thời gian kết thúc proc();// xử lí } } |
Ngoài ra, còn có 1 số bài toán tham lam tương tự dạng này kết hợp với disjoin set nữa:
https://www.geeksforgeeks.org/job-sequencing-problem-set-1-greedy-algorithm/
Bài toán ATM withdrawal
Đây là link gốc của bài toán: http://codeforces.com/problemset/gymProblem/100541/C
Đây là lời dịch tiếng viết và solution
Vinh làm việc cho 1 nhà máy sản xuất cây ATM. Chức năng cơ bản của cây ATM đó là rút tiền. Khi người dùng yêu cầu rút W VND, cây ATM sẽ trả ra N tờ tiền có tổng đúng bằng W. Ở thế hệ tiếp theo của cây ATM, Vinh phải làm việc với thuật toán để tối ưu số tờ tiền trả ra cho mỗi giao dịch là nhỏ nhất.
Nhiệm vụ của bạn là giúp Vinh thực hiện công việc của anh ý với các tờ tiền được đưa vào có giá trị 1000, 2000, 3000, 5000, 1000 * 101, 2000 * 101, 3000 * 101, 5000 * 101, …, 1000 * 10c, 2000 * 10c, 3000 * 10c, 5000 * 10c. Với c là số nguyên dương.
Với dữ liệu đầu vào là 2 số W ( W <= 1018) và c (c <= 15).
Và đầu ra là 2 số N và S trong đó S là số cách để trả ra số tờ tiền ít nhất N sao cho tổng bằng W. Nếu không thể trả ra W thì chương trình trả về 0.
Idea: Dễ thấy đơn vị nhỏ nhất để thanh toán là 1000. Do đó nếu W không chia hết cho 1000 thì cây ATM không thể thanh toán => Bài toán trở thành dùng các tờ 1, 2, 3, 5, 1 * 101, 2 * 101, 3 * 101, 5 * 101, …, 1 * 10c, 2 * 10c, 3 * 10c, 5 * 10c để trả ra W2 = W/1000. Ý tưởng tham lam đầu tiên đó nếu W lớn ta ưu tiên sử dụng các tờ mệnh giá lớn trước tức đầu tiên nếu W > 1 * 10c ta sẽ dùng các tờ 1 * 10c, 2 * 10c, 3 * 10c, 5 * 10c trước, sau đó tới các tờ 1 * 10c-1, 2 * 10c-1, 3 * 10c-1, 5 * 10c-1 và tới c-2, … 0.
Ví dụ
Với số tiền W = xyzt000 => W2= xyzt và c = 2 ta sẽ làm như sau
- Dùng các tờ 100, 200, 300, 500 để trả ra xy00 đồng => dùng các tờ 1, 2, 3, 5 trả ra xy đồng (1)
- Dùng các tờ 10, 20, 30, 50 trả ra z0 đồng => dùng các tờ 1, 2, 3 , 5 trả ra z đồng ( z ∈ [0, 9]) (2)
- dùng các tờ 1, 2, 3 , 5 trả ra t đồng ( t ∈ [0, 9]) (3)
Giả sử mỗi trường hợp (TH) (1), (2), (3) ta cần lấy số tờ ít nhất là u và số cách là v thì
Số tờ ít nhất cần lấy ra để có tổng bằng W là ∑ci = 0(u)
Số cách ứng với cách lấy trên là ∏ci = 0(v)
Với TH (2) và (3) ( z,t ∈ [0, 9]) ta có thể lập bảng để tra cứu như sau
| Số tờ | Số cách | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 1 |
| 4 | 2 | 2 (dùng tờ số 3 và 1 hoặc 2 tờ số 2) |
| 5 | 1 | 1 |
| 6 | 2 | 2 (dùng tờ số 5 và 1 hoặc 2 tờ số 3) |
| 7 | 2 | 1 |
| 8 | 2 | 1 |
| 9 | 3 | 3 (dùng tờ số 5, 3 và 1 hoặc 5 và 2 tờ số 2 hoặc 3 tờ số 3) |
Với TH (1) ta tiếp tục tham lam bằng cách sử dụng tờ mệnh giá cao nhất tờ số 5 để lấy ra xy/5 đồng phần dư còn lại xy%5 ta tiếp tục tra bảng trên.
Ví dụ xy = 29
Ta sử dụng 5 tờ 5 đồng để lấy được 25 đồng ( chỉ có 1 cách) sau đó còn 4 đồng ta dùng 2 tờ ( có 2 cách) Tuy nhiên ta còn 1 cách lấy nữa đó là chỉ lấy 4 tờ 5 đồng để được 20 đồng và dùng 3 tờ 3 đồng => với TH này ta cần 7 tờ và có tới tận 3 cách lấy
Tổng quát lại ta có các TH sau
- xy%5 = 0 => cần xy/5 tờ 5 đồng và có 1 cách lấy
- xy%5 = 1 => có 2 TH con
- xy != 1 => có thêm cách là lấy xy/5 -1 tờ 5 đồng và lấy 6 đồng nữa => cần xy/5 + 1 tờ và có 2 cách lấy
- xy đúng bằng 1 => cần 1 tờ 1 đồng và có 1 cách lấy
- xy%5 = 2 => có 2 TH con tuy nhiên với TH lấy 7 đồng cũng chỉ có 1 cách => cần xy/5 + 1 và có 1 cách
- xy%5 = 3 => có 2 TH con tuy nhiên với TH lấy 8 đồng cũng chỉ có 1 cách => cần xy/5 + 1 và có 1 cách
- xy%5 = 4 => có 2 TH con
- xy != 4 => có thêm cách là lấy xy/5 -1 tờ 5 đồng và lấy 6 đồng nữa => cần xy/5 + 1 tờ và có 3 cách lấy
- xy == 4 => cần 4 đồng => cần 2 tờ và có 2 cách lấy
Implementation
