cpp-153Bước 1Trung bình
Nối Dây Kim Loại Chi Phí Nhỏ Nhất (Mã Hóa Huffman / Priority Queue)
Có N sợi dây kim loại, sợi thứ i có độ dài Li. Bạn cần nối tất cả N sợi dây này lại thành một sợi dây duy nhất.
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Thuật toán Tham lam (Greedy Algorithm) trong C++
Đưa ra lựa chọn tốt nhất ở từng bước để đạt được lời giải tối ưu toàn cục. Học cách nhận diện bài toán thỏa mãn tính chất tham lam và chứng minh lời giải.
6
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
0
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
5
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
1
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Tư duy Tham lam cơ bản
Sắp xếp theo tiêu chí phù hợp và chọn lựa chọn có lợi nhất ở bước hiện tại.
Bước 2
Lập lịch & Xếp đoạn
Bài toán chọn số lượng công việc không giao nhau nhiều nhất bằng cách sắp xếp theo thời gian kết thúc.
Bước 3
Kết hợp Priority Queue
Duy trì phần tử ưu tiên để cập nhật trạng thái tham lam liên tục.
Lỗi thường gặp & Cách phòng tránh
•
Áp dụng tham lam cho các bài toán cần quy hoạch động (không thỏa mãn thuộc tính lựa chọn tham lam).
•
Sắp xếp sai tiêu chí (ví dụ sắp xếp theo thời gian bắt đầu thay vì thời gian kết thúc).
Danh sách bài tập thực hành (6 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Trung bình 5 bài
cpp-150Bước 2Trung bình
Xếp Lịch Phòng Họp Không Trùng Lặp Tối Đa (Interval Scheduling)
Có N cuộc họp đăng ký sử dụng một phòng hội nghị duy nhất. Cuộc họp thứ i bắt đầu tại thời điểm Si và kết thúc tại thời điểm Ei (Si < Ei).
cpp-152Bước 3Trung bình
Bài Toán Ba-Lô Phân Số (Fractional Knapsack)
Có N món đồ kim loại quý dạng hạt/bột. Món đồ thứ i có giá trị Vi và trọng lượng Wi. Bạn có một chiếc ba-lô với sức chứa tối đa là C.
cpp-151Bước 4Trung bình
Hành Trình Qua Các Trạm Xăng Vòng Tròn (Gas Station)
Trên một cung đường tròn có N trạm xăng được đánh số từ 1 đến N theo chiều kim đồng hồ.
cpp-088Bước 5Trung bình
Xử lý khoảng thời gian: Gộp khoảng và Lập lịch tác vụ tối đa
Cho N khoảng thời gian [Li, Ri]. Hãy gộp tất cả các khoảng thời gian bị chồng lấn (overlapping) hoặc tiếp xúc nhau thành các khoảng rời rạc cực đại.
Nâng cao 1 bài
cpp-094Bước 1Nâng cao
Lập lịch khóa học: Tham lam kết hợp Hàng đợi ưu tiên Max-Heap
1. Sắp xếp các khóa học theo hạn chót (Deadline) tăng dần.