Mục lục.................................................................................................................................................................... A. Lý thuyết chung.................................................................................................................................................. 1. Khái niệm......................................................................................................................................................... 2.Đặc điểm của chiến lược tham lam:................................................................................................................. 3ính chất lựa chọn tham lam............................................................................................................................ 4. Mô tả tổng quát của thuật toán......................................................................................................................... 5í dụ áp dụng:................................................................................................................................................... 6. Đánh giá chung:.............................................................................................................................................. B. Bài tập................................................................................................................................................................. Bài toán 1: VATSUA............................................................................................................................................ Bài toán 2: THANGMAY.................................................................................................................................... Bài toán 3: CHENDAU....................................................................................................................................... Bài toán 4: OTO................................................................................................................................................. A. Lý thuyết chung1. Khái niệmThuật toán tham lam là thuật toán luôn luôn tìm kiếm lựa chọn tối ưu ở thời điểm hiện tại để đưa ra kết quả tối ưu. Điều này có nghĩa rằng, sự lựa chọn tốt nhất ở mỗi bước sẽ dẫn tới lời giải tối ưu nhất Ví dụ: Bài toán trả tiền của máy rút tiền tự động ATM.Trong máy rút tiền tự động ATM, ngân hàng đã chuẩn bị sẵn các loại tiền có mệnh giá 100 đồng, 50 đồng, 20 đồng và 10 đồng. Giả sử mỗi loại tiền đều có số lượng không hạn chế. Khi có một khách hàng cần rút một số tiền n đồng (tính chẵn đến 10 đồng, tức là n chia hết cho 10000). Hãy tìm một phương án trả tiền sao cho trả đủ n đồng và số tờ giấy bạc phải trả là ít nhất. Gọi X = (X1, X2, X3, X4) là một phương án trả tiền, trong đó X1 là số tờ giấy bạc mệnh giá 100 đồng, X2 là số tờ giấy bạc mệnh giá 50 đồng, X3 là số tờ giấy bạc mệnh giá 20 đồng và X4 là số tờ giấy bạc mệnh giá 10 đồng. Theo yêu cầu ta phải có X1 + X2 + X3 + X4 nhỏ nhất và X1 * 100 + X2 * 50 + X3 * 20 + X4 * 10 = n. Áp dụng “tinh thần” tham lam để giải bài toán này là: để có số tờ giấy bạc phải trả (X1 + X2 + X3 + X4) nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải được chọn nhiều nhất. Trước hết ta chọn tối đa các tờ giấy bạc mệnh giá 100 đồng, nghĩa là X1 là số nguyên lớn nhất sao cho X1 * 100 ≤ n. Tức là X1 = n DIV 100. Xác định số tiền cần rút còn lại là hiệu n – X1 * 100000 và chuyển sang chọn loại giấy bạc 50 đồng... Ví dụ khách hàng cần rút 1.290 đồng (n = 1290000), phương án trả tiền như sau: X1 = 1290000 DIV 100000 = 12. Số tiền cần rút còn lại là 1290000 – 12 * 100000 = 90000. X2 = 90000 DIV 50000 = 1. Số tiền cần rút còn lại là 90000 – 1 * 50000 = 40000. X3 = 40000 DIV 20000 = 2. Số tiền cần rút còn lại là 40000 – 2 * 20000 = 0. X4 = 0 DIV 10000 = 0. Ta có X = (12, 1, 2, 0), tức là máy ATM sẽ trả cho khách hàng 12 tờ 100 đồng, 1 tờ 50 đồng và 2 tờ 20 đồng. 2. Đặc điểm của chiến lược tham lam:Phương pháp tham lam gợi ý chúng ta tìm một trật tự hợp lí để duyệt dữ liệu nhằm đạt được mục tiêu một cách chắc chắn và nhanh chóng. Thông thường, dữ liệu được duyệt theo một trong 5. Ví dụ áp dụng:Giải quyết bài toán trả tiền của máy rút tiền tự động ATM như đã nêu ở trên Input : - Có n loại tiền, mỗi loại tiền có giá trị tương ứng là d 1 ,d 2 ,..,dn. - Lượng tiền M đồng. Output : Đổi M đồng ra tiền lẻ sao cho số loại tiền đổi là ít nhất. *Phân tích : Cần phải tìm 1 nghiệm X = (x 1 ,x 2 ,.) với xi là số loại tiền thứ i có giá trị di sao cho M= i m i ∑ idx\= 1 ⇒Tìm cách đổi sao cho tổng loại tiền cần đổi là ít nhất. Vậy ta sẽ bắt đầu đổi từ đồng có giá trị lớn nhất và cứ giảm dần cho đến khi số tiền M đã được đổi hết thì thông báo là tìm được nghiệm, ngược lại thì thông báo không đổi được. Áp dụng tư tưởng của thuật toán tham lam, ta có thể viết như sau: void Đổitiền_Thamlam(M); { Const int D={d 1 ,d 2 ,..,dn} // mảng lưu giá trị từng loại tiền int x, sum, i; // x là nghiệm bài toán - Sắp xếp D giảm dần X= φ ; sum:= φ ; i:=1; While (sum!=M && i <=n) // Trong khi chưa đổi hết tiền { xi= (M - sum)/di ; // Số tờ tiền loại di if (sum+xi*di ≤ M) { X=X+{xi}; sum:=sum+xi*di; // Số tiền đã đổi được tính đến loại tiền i } i++; } If (sum=M ) Return(X); // Trả lại nghiệm của bài toán Else < Thông báo không đổi được>; } Nhận xét: - Tính chất tham lam thể hiện ở chỗ, tại mỗi bước luôn chọn “miếng ăn ngon nhất” mà không để ý hậu quả sau này. Cho nên, với một số trường hợp thuật toán cho ta nghiệm tối ưu, nhưng trong nhiều trường hợp nghiệm tìm được không phải là nghiệm tối ưu mà chỉ gần đúng với nghiệm tối ưu, thậm chí còn không tính được nghiệm đúng. Ví dụ: Nếu M=13 và các loại tiền có mệnh giá là: d 1 =3, d 2 =4, d 3 =6. Cần tìm cách đổi 13 đồng sao cho số tiền đổi là ít nhất. Với thuật toán trên ta cần 2 tờ 6 đồng dư 1 đồng. Như vậy số tiền này sẽ không đổi được, nhưng trong thực tế, ta có thể đổi được dễ dàng với 1 tờ 6 đồng, 1 tờ 4 đồng và một tờ 3 đồng. 6. Đánh giá chung:*Ưu điểm :
B. Bài tậpBài toán 1: VATSUAVào một buổi sáng anh Bo sắp một đàn bò gồm n con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ i có khả năng sẽ vắt được ai lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con 01 lít sữa. Nếu vắt sữa con bò thứ nhất, n-1 con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì n-2 con còn lại bị giảm sản lượng.... Bạn hãy giúp anh Bo tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé. Dữ liệu vào: gồm 2 dòng
Dữ liệu xuất:
Ví dụ input 4 4 4 4 4 output sort (a,a+n,cmp); for (int i=0; i<n; i++) kq=kq+max(0,a[i]-i); cout << kq; } Bài toán 2: THANGMAYCó n người đang đứng chờ trước một thang máy duy nhất tại tầng trệt trong một tòa cao ốc cao 2000 tầng, họ muốn đi đến các tầng trong tòa nhà. Các tầng của cao ốc được đánh số 1, 2, 3, 4, ..., 2000. Tầng trệt là tầng 1. Người thứ i muốn đi đến tầng ai. Thang máy chỉ chở được k người cùng lúc. Thời gian thang máy đi từ tầng x đến tầng y là |x - y| giây. Hãy tính thời gian tối thiểu để thang máy có thể vận chuyển hết n người đến tầng mà họ mong muốn và thang máy quay trở lại tầng trệt. (giả sử thời gian ra vào thang máy là không đáng kể) Dữ liệu nhập: gồm 2 dòng
Dữ liệu xuất:
Ví dụ input 3 2 2 3 4 output 8 input 4 2 50 100 50 100 output 296 input 10 3 2 2 2 2 2 2 2 2 2 2 output 8 Trong test 1:
Ý tưởng thuật toán: Sử dụng thuật toán tham lam Sắp xếp mảng a theo chiều tăng dần Vì mỗi lần vận chuyển chỉ được chở tối đa k người. Để có được kết quả tối ưu, ở lần vận chuyển thứ 1 ta sẽ vận chuyển n%k người đầu tiên trước, sau đó mỗi lần quay lại vận chuyển k người cho đến khi vận chuyển hết. Độ phức tạp: O(nlogn) Code tham khảo: include <bits/stdc++.h> using namespace std; int main() { int i,n,k, a[2001]; cin >> n >> k; for (i=1; i<=n; i++) cin >> a[i]; sort(a+1, a+n+1); long kq=max(0,a[n%k]-1);for (i=n%k+k; i<=n; i+=k) kq=kq+a[i]-1; cout << kq*2; } Bài toán 3: CHENDAUCho dãy số nguyên A gồm các số từ 1 -> n. Tìm cách chèn (n-1) dấu ‘+’ hoặc ‘–‘ vàogiữa các số sao cho khi tính biểu thức đó cho kết quả là S.Input :Cho n và S (1 ≤ n ≤ 500, |S| ≤ 125250)Output :Nếu có xuất ra biểu thức, không thì xuất ‘Impossible’Ví dụ:Input:9 5printf("Impossible"); return 0; } c=c/2; for (long i=n; i>=2; i--) { if (c-i>= 0) { a[i]=true; c=c-i; } } if (c!=0) printf("Impossible"); else { printf("1"); for (long i=2; i<=n; i++) { if (a[i]) printf("-"); else printf("+"); printf("%d",i); } } return 0; } Bài toán 4: OTOMột cơ sở sửa chữa ô tô có nhận n chiếc xe để sửa. Do các nhân viên làm việc quá lười nhác nên đã đến hạn trả cho khách hàng mà vẫn chưa tiến hành sửa được chiếc xe nào. Theo hợp đồng đã ký kết từ trước, nếu bàn giao xe thứ i quá hạn ngày nào thì sẽ phải trả thêm một khoản tiền phạt là A[i]. Ông chủ cơ sở sửa chữa quyết định sa thải toàn bộ công nhân và thuê nhân công mới. Với lực lượng mới này, ông ta dự định rằng để sửa chiếc xe thứ i sẽ cần B[i] ngày. Vấn đề đặt ra đối với ông là phải lập lịch sửa tuần tự các chiếc xe sao cho tổng số tiền bị phạt là ít nhất. Yêu cầu: Hãy lập lịch sửa xe giúp cho ông chủ cơ sở sửa chữa ô tô Input:
Output:
Ví dụ: Input: 4 1 3 4 2 3 2 3 1 Output: 44 4 2 3 1 Xong công việc 4 vào cuối ngày 1 => phải trả 2 * 1 = 2. Xong công việc 2 vào cuối ngày 3 => phải trả 3 * 3 = 9. Xong công việc 3 vào cuối ngày 6 => phải trả 6 * 4 = 24. Xong công việc 1 vào cuối ngày 9 => phải trả 1 * 9 = 9. Vậy tổng cộng phải trả 44. Ý tưởng thuật toán: Ta sửa dụng phương pháp tham lam để giải quyết bài toán như sau Đầu tiên, ta sắp các xe lại theo A/B giảm dần, sau đó lần lượt sửa các xe theo đúng thứ tự đó. Chứng minh tính đúng đắn của phương pháp: Để chứng minh cách làm trên là đúng, ta xét một lịch sửa xe bất kì, trong đó tồn tại 2 xe i và i+1 có A[i]/B[i]<A[i+1]/B[i+1]. Cần chứng minh khi đổi vị trí 2 xe đó thì tổng tiền phạt sẽ giảm. Khi đổi vị trí 2 xe, chỉ có tiền phạt của 2 xe đó bị thay đổi, còn các xe trước và sau đó vẫn giữ nguyên. Chứng minh: Gọi S là thời gian để sửa tất cả các xe từ 1 đến i- Ta có: |
