Bài 18: Thuật toán tham lam trong C++ và Python: đổi tiền, chọn hoạt động, xếp lịch và khi nào tham lam sai
Lời mở đầu
Đi siêu thị trả tiền thối 380 nghìn, cô thu ngân sẽ đưa ngay một tờ 200, một tờ 100, một tờ 50, một tờ 20 và một tờ 10: luôn chọn tờ lớn nhất còn dùng được. Không ai ngồi thử mọi cách kết hợp các tờ tiền, vậy mà kết quả luôn là ít tờ nhất. Cách nghĩ “mỗi bước chọn cái tốt nhất ngay lúc đó” gọi là tham lam (greedy).
Tham lam là chiến lược có code ngắn nhất và chạy nhanh nhất (thường chỉ là sắp xếp rồi duyệt một lượt, $O(n \log n)$). Nhưng nó cũng là chiến lược dễ sai nhất: rất nhiều bài trông như tham lam được, thật ra lại không. Bài này dạy em cả hai mặt: những bài tham lam kinh điển, và cách tìm phản ví dụ để không bị “lừa”.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Tham lam là gì?
Một thuật toán tham lam xây dựng lời giải từng bước. Ở mỗi bước, nó chọn phương án có vẻ tốt nhất ngay lúc đó theo một tiêu chí nào đó (lớn nhất, nhỏ nhất, kết thúc sớm nhất…), chốt luôn lựa chọn ấy và đi tiếp, không bao giờ quay lại xem xét lại. So với quay lui (bài 15) thử mọi nhánh, tham lam chỉ đi đúng một nhánh duy nhất của cây, nên cực nhanh.
2. Vì sao lựa chọn đó không làm mất lời giải tối ưu? Nếu chưa trả lời được, hãy thử tìm phản ví dụ nhỏ: viết thêm một chương trình vét cạn chắc chắn đúng, sinh nhiều test nhỏ ngẫu nhiên và so sánh (kỹ thuật “chấm trâu” ở bài 22). Chạy vài trăm test không thấy khác nhau thì mới yên tâm nộp.
Phần 2Bài toán đổi tiền
Bài toán: có các mệnh giá tiền $c_1 > c_2 > \dots > c_m$ (mỗi loại không giới hạn số tờ). Cần trả đúng số tiền $N$ với ít tờ nhất. Tham lam: lấy càng nhiều tờ mệnh giá lớn nhất càng tốt, phần dư chuyển sang mệnh giá tiếp theo.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int m; long long N;
cin >> m >> N;
vector<long long> c(m);
for(auto &v : c) cin >> v; // mệnh giá giảm dần
long long soTo = 0;
for(int i = 0; i < m; i++){
long long k = N / c[i];
soTo += k;
N -= k * c[i];
}
if(N == 0) cout << soTo;
else cout << -1;
return 0;
}m, N = map(int, input().split())
c = list(map(int, input().split()))
so_to = 0
for v in c:
k = N // v
so_to += k
N -= k * v
print(so_to if N == 0 else -1)Mô phỏng trực quan. Đổi tiền là ví dụ dễ hiểu nhất của tham lam, nhưng cũng là chỗ dễ "tin nhầm" nhất. Em chạy với mệnh giá tiền Việt Nam trước, sau đó tự đổi sang bộ 1 3 4 và số tiền 6: mô phỏng sẽ so với cách đổi tốt nhất để em thấy tận mắt khi nào tham lam sai.
Phần 3Chọn nhiều hoạt động nhất
Bài toán: hội trường nhận $n$ yêu cầu tổ chức sự kiện, sự kiện $i$ diễn ra trong $[s_i, e_i)$. Hai sự kiện không được chồng nhau (sự kiện kết thúc lúc 9 giờ thì sự kiện khác bắt đầu lúc 9 giờ được). Chọn nhiều sự kiện nhất.
Thử ba tiêu chí tham lam: bắt đầu sớm nhất (sai: một sự kiện bắt đầu sớm nhưng kéo dài cả ngày chặn hết các sự kiện khác), ngắn nhất (sai: một sự kiện ngắn nằm vắt ngang có thể chặn hai sự kiện dài), và kết thúc sớm nhất: đúng! Lý do: sự kiện kết thúc sớm nhất “trả lại” hội trường sớm nhất, để lại nhiều thời gian nhất cho phần còn lại. Nếu một lời giải tối ưu nào đó không chọn nó, ta thay sự kiện đầu tiên của lời giải đó bằng nó mà không gây chồng chéo, số sự kiện không đổi.
Thuật toán: sắp xếp theo $e_i$ tăng dần, duyệt lần lượt, sự kiện nào bắt đầu không sớm hơn thời điểm kết thúc của sự kiện vừa chọn thì chọn.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<pair<int,int>> a(n); // (kết thúc, bắt đầu)
for(auto &p : a) cin >> p.second >> p.first;
sort(a.begin(), a.end());
int dem = 0, ketThuc = INT_MIN;
for(int i = 0; i < n; i++){
if(a[i].second >= ketThuc){
dem++;
ketThuc = a[i].first;
}
}
cout << dem;
return 0;
}n = int(input())
a = []
for _ in range(n):
s, e = map(int, input().split())
a.append((e, s))
a.sort() # theo thời điểm kết thúc
dem, ket_thuc = 0, float('-inf')
for e, s in a:
if s >= ket_thuc:
dem += 1
ket_thuc = e
print(dem)Xem ba tiêu chí tham lam “đấu” với nhau: chọn tiêu chí rồi bấm Tự chạy. Với bộ dữ liệu mẫu, tiêu chí “bắt đầu sớm nhất” và “ngắn nhất” cho kết quả kém hơn “kết thúc sớm nhất”.
Phần 4Xếp hàng và lập luận đổi chỗ
Bài toán: $n$ người xếp hàng chờ một quầy duy nhất, người $i$ cần $t_i$ phút. Thời gian chờ của mỗi người là tổng thời gian phục vụ những người đứng trước. Xếp thứ tự sao cho tổng thời gian chờ nhỏ nhất. Trực giác: người làm nhanh đứng trước. Chứng minh bằng lập luận đổi chỗ (exchange argument), công cụ chứng minh tham lam quan trọng nhất:
Giả sử trong một cách xếp có hai người đứng liền nhau $A$ trước $B$ mà $t_A > t_B$. Đổi chỗ hai người: những người khác không bị ảnh hưởng; trước đây $B$ phải chờ thêm $t_A$, giờ $A$ chờ thêm $t_B$. Tổng giảm $t_A - t_B > 0$. Vậy cách xếp tối ưu không thể có cặp “nghịch thế” nào, tức là phải sắp xếp tăng dần.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<long long> t(n);
for(auto &v : t) cin >> v;
sort(t.begin(), t.end());
long long dangCho = 0, tong = 0;
for(int i = 0; i < n; i++){
tong += dangCho;
dangCho += t[i];
}
cout << tong;
return 0;
}n = int(input())
t = sorted(map(int, input().split()))
dang_cho = tong = 0
for v in t:
tong += dang_cho # người này chờ hết những người trước
dang_cho += v
print(tong)Phần 5Cái túi: khi nào tham lam đúng, khi nào sai?
Có $n$ món hàng, món $i$ nặng $w_i$, giá trị $v_i$; túi chở tối đa $W$. Hai phiên bản của bài toán cho kết quả hoàn toàn khác nhau:
- Cái túi phân số (được cắt nhỏ món hàng, ví dụ gạo, vàng cám): tham lam theo giá trị trên một đơn vị khối lượng $\frac{v_i}{w_i}$ giảm dần là tối ưu. Lấy hết món “đắt” nhất, rồi món tiếp theo, món cuối lấy một phần cho vừa túi.
- Cái túi 0/1 (mỗi món lấy cả hoặc không lấy): tham lam sai. Ví dụ $W = 10$, các món $(w, v) = (6, 30), (5, 20), (5, 20)$: tham lam theo $\frac{v}{w}$ lấy món đầu ($\frac{30}{6} = 5$ lớn nhất), còn 4 kg không lấy thêm được gì, tổng 30; trong khi lấy hai món sau được 40. Bài này cần quy hoạch động (bài 19).
Cái túi phân số: tham lam theo giá trị trên mỗi kg
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; double W;
cin >> n >> W;
vector<pair<double,double>> a(n); // (w, v)
for(auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end(), [](auto &x, auto &y){
return x.second / x.first > y.second / y.first; // v/w giảm dần
});
double tong = 0;
for(auto &p : a){
if(W <= 0) break;
double lay = min(p.first, W); // lấy hết, hoặc phần vừa túi
tong += lay * p.second / p.first;
W -= lay;
}
cout << fixed << setprecision(2) << tong;
return 0;
}n, W = map(float, input().split())
a = [tuple(map(float, input().split())) for _ in range(int(n))]
a.sort(key=lambda p: p[1] / p[0], reverse=True)
tong = 0.0
for w, v in a:
if W <= 0:
break
lay = min(w, W)
tong += lay * v / w
W -= lay
print(f"{tong:.2f}")- Taxi (Dễ)
- Đong Gạo (DONGGAO) (Dễ)
- Two Sets (CSES 1092) (Dễ)
- Tích Lớn Nhất (TICHMAX) (Dễ)
- Minimum Number of Moves to Seat Everyone (LeetCode 2037) (Dễ)
Mô phỏng trực quan. Cùng một chiến lược "món nào giá/kg cao thì lấy trước", vì sao túi cắt được thì đúng mà túi 0/1 lại sai? Em xem mô phỏng chạy lần lượt cả hai kiểu túi trên cùng một bộ món hàng, cuối cùng so với đáp án tối ưu thật sự.
Bài tậpLuyện tham lam
Tiền Việt Nam có các mệnh giá 1, 2, 5, 10, 20, 50, 100, 200, 500 (nghìn đồng). Cho số tiền $N$ ($N \le 10^{18}$, đơn vị nghìn đồng), in số tờ ít nhất để trả đúng $N$.
199911💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long N;
cin >> N;
long long c[] = {500, 200, 100, 50, 20, 10, 5, 2, 1}, dem = 0;
for(long long v : c){ dem += N / v; N %= v; }
cout << dem;
return 0;
}N = int(input())
dem = 0
for v in (500, 200, 100, 50, 20, 10, 5, 2, 1):
dem += N // v
N %= v
print(dem)Có $n$ khách ($n \le 10^5$), khách $i$ cần $t_i$ phút. Xếp thứ tự để tổng thời gian chờ (không tính thời gian được phục vụ của chính mình) nhỏ nhất. In tổng đó.
4
5 2 8 112💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<long long> t(n);
for(auto &v : t) cin >> v;
sort(t.begin(), t.end());
long long cho = 0, tong = 0;
for(long long v : t){ tong += cho; cho += v; }
cout << tong;
return 0;
}n = int(input())
t = sorted(map(int, input().split()))
cho = tong = 0
for v in t:
tong += cho
cho += v
print(tong)Có $n$ yêu cầu ($n \le 10^5$), yêu cầu $i$ dùng hội trường trong $[s_i, e_i)$. Chọn nhiều yêu cầu nhất không chồng nhau.
5
1 3
2 5
4 7
6 9
8 103💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<pair<long long,long long>> a(n);
for(auto &p : a) cin >> p.second >> p.first;
sort(a.begin(), a.end());
int dem = 0; long long kt = LLONG_MIN;
for(auto &p : a)
if(p.second >= kt){ dem++; kt = p.first; }
cout << dem;
return 0;
}n = int(input())
a = sorted((e, s) for s, e in (map(int, input().split()) for _ in range(n)))
dem, kt = 0, float('-inf')
for e, s in a:
if s >= kt:
dem += 1
kt = e
print(dem)Cho số nguyên dương $N$ dưới dạng xâu (độ dài $\le 10^5$, không có chữ số 0 ở đầu) và $k$. Xóa đúng $k$ chữ số để số còn lại (giữ nguyên thứ tự) là lớn nhất.
1924 294💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s; int k;
cin >> s >> k;
string st;
for(char d : s){
while(k > 0 && !st.empty() && st.back() < d){ st.pop_back(); k--; }
st.push_back(d);
}
st.resize(st.size() - k);
cout << st;
return 0;
}s, k = input().split()
k = int(k)
st = []
for d in s:
while k > 0 and st and st[-1] < d:
st.pop()
k -= 1
st.append(d)
if k:
st = st[:-k]
print(''.join(st))Có $n$ bao hàng ($n \le 10^5$), bao $i$ nặng $w_i$ kg và trị giá $v_i$, được phép lấy một phần bao (giá trị tỉ lệ theo khối lượng). Túi chở tối đa $W$ kg. In tổng giá trị lớn nhất, làm tròn 2 chữ số thập phân.
3 50
10 60
20 100
30 120240.00💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; double W;
cin >> n >> W;
vector<pair<double,double>> a(n);
for(auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end(), [](auto &x, auto &y){ return x.second * y.first > y.second * x.first; });
double tong = 0;
for(auto &p : a){
if(W <= 0) break;
double lay = min(p.first, W);
tong += lay * p.second / p.first;
W -= lay;
}
printf("%.2f", tong);
return 0;
}n, W = input().split()
n, W = int(n), float(W)
a = [tuple(map(float, input().split())) for _ in range(n)]
a.sort(key=lambda p: p[1] / p[0], reverse=True)
tong = 0.0
for w, v in a:
if W <= 0:
break
lay = min(w, W)
tong += lay * v / w
W -= lay
print(f"{tong:.2f}")Có $n$ điểm trên trục số ($n \le 10^5$, tọa độ nguyên). Mỗi tấm bạt phủ được một đoạn dài $L$ (phủ các điểm có tọa độ thuộc $[x, x + L]$). Cần ít nhất bao nhiêu tấm bạt để phủ hết các điểm?
6 3
1 2 5 6 9 43💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long L;
cin >> n >> L;
vector<long long> x(n);
for(auto &v : x) cin >> v;
sort(x.begin(), x.end());
int dem = 0, i = 0;
while(i < n){
long long bat = x[i];
dem++;
while(i < n && x[i] <= bat + L) i++;
}
cout << dem;
return 0;
}n, L = map(int, input().split())
x = sorted(map(int, input().split()))
dem = i = 0
while i < n:
bat = x[i]
dem += 1
while i < n and x[i] <= bat + L:
i += 1
print(dem)Có $n$ người cân nặng $w_i$ ($n \le 10^5$). Mỗi thuyền chở tối đa hai người với tổng cân nặng không quá $W$ (mỗi người nặng không quá $W$). Cần ít nhất bao nhiêu thuyền?
4 100
70 50 80 503💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long W;
cin >> n >> W;
vector<long long> w(n);
for(auto &v : w) cin >> v;
sort(w.begin(), w.end());
int i = 0, j = n - 1, thuyen = 0;
while(i <= j){
if(i < j && w[i] + w[j] <= W) i++; // người nhẹ đi cùng
j--; // người nặng luôn đi
thuyen++;
}
cout << thuyen;
return 0;
}n, W = map(int, input().split())
w = sorted(map(int, input().split()))
i, j, thuyen = 0, n - 1, 0
while i <= j:
if i < j and w[i] + w[j] <= W:
i += 1
j -= 1
thuyen += 1
print(thuyen)Có $n$ công việc ($n \le 10^5$), mỗi việc làm mất đúng 1 ngày, việc $i$ phải xong không muộn hơn ngày $d_i$ thì mới được trả $p_i$ đồng (làm trễ thì không được gì). Mỗi ngày làm một việc, bắt đầu từ ngày 1. Tìm tổng tiền lớn nhất.
5
2 100
1 19
2 27
1 25
3 15142💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<pair<int,long long>> a(n); // (hạn chót, tiền)
for(auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end());
priority_queue<long long, vector<long long>, greater<long long>> pq;
for(auto &p : a){
pq.push(p.second);
if((int)pq.size() > p.first) pq.pop(); // quá số ngày → bỏ việc rẻ nhất
}
long long tong = 0;
while(!pq.empty()){ tong += pq.top(); pq.pop(); }
cout << tong;
return 0;
}import heapq
n = int(input())
a = sorted(tuple(map(int, input().split())) for _ in range(n))
pq = []
for d, p in a:
heapq.heappush(pq, p)
if len(pq) > d:
heapq.heappop(pq)
print(sum(pq))
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét