Giao diện
Greedy: Bài toán lập lịch
🎯 Mục tiêu
Luyện tập thuật toán tham lam qua bài toán chọn hoạt động, lập lịch công việc có deadline, ba lô phân số và mã hóa Huffman.
Mô tả bài tập
Thuật toán tham lam (Greedy) chọn phương án tốt nhất tại mỗi bước cục bộ, hy vọng đạt kết quả tối ưu toàn cục. Bài tập này bao gồm các bài toán kinh điển mà greedy cho lời giải tối ưu.
Yêu cầu
Bài 1: Chọn hoạt động (Activity Selection)
Cho danh sách hoạt động với thời gian bắt đầu và kết thúc, chọn số lượng hoạt động tối đa không trùng lặp.
python
def activity_selection(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
# TODO: Cài đặt greedy
pass
acts = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]
result = activity_selection(acts)
assert len(result) == 4 # Ví dụ: (1,4), (5,7), (8,11), (12,16)Bài 2: Lập lịch công việc với Deadline
Cho n công việc, mỗi công việc có deadline và lợi nhuận. Mỗi công việc mất 1 đơn vị thời gian. Tìm lịch trình tối đa lợi nhuận.
python
def job_scheduling(jobs: list[tuple[str, int, int]]) -> tuple[int, list[str]]:
# TODO: Cài đặt greedy
pass
jobs = [("a",2,100), ("b",1,19), ("c",2,27), ("d",1,25), ("e",3,15)]
profit, schedule = job_scheduling(jobs)
assert profit == 142 # jobs a, c, eBài 3: Ba lô phân số (Fractional Knapsack)
Khác với 0/1 Knapsack, ở đây bạn có thể lấy một phần của vật phẩm.
python
def fractional_knapsack(items: list[tuple[int, int]], capacity: int) -> float:
# TODO: Cài đặt greedy theo tỷ lệ value/weight
pass
items = [(10, 60), (20, 100), (30, 120)]
assert abs(fractional_knapsack(items, 50) - 240.0) < 1e-6Bài 4: Mã hóa Huffman
Xây dựng cây Huffman từ tần suất các ký tự và trả về bảng mã.
python
import heapq
def huffman_coding(freq: dict[str, int]) -> dict[str, str]:
# TODO: Cài đặt bằng priority queue
pass
codes = huffman_coding({"a": 5, "b": 9, "c": 12, "d": 13, "e": 16, "f": 45})
assert all(isinstance(v, str) and set(v) <= {"0", "1"} for v in codes.values())Phân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - Activity Selection | O(n log n) | O(n) |
| 2 - Job Scheduling | O(n log n) | O(n) |
| 3 - Fractional Knapsack | O(n log n) | O(1) |
| 4 - Huffman Coding | O(n log n) | O(n) |
Gợi ý
Gợi ý Bài 1
Sắp xếp hoạt động theo thời gian kết thúc tăng dần. Chọn hoạt động đầu tiên, sau đó chọn hoạt động tiếp theo có start >= end của hoạt động cuối được chọn.
Gợi ý Bài 2
Sắp xếp giảm dần theo lợi nhuận. Với mỗi job, tìm slot trống lớn nhất ≤ deadline để đặt job vào.
Gợi ý Bài 4
Dùng min-heap. Lặp: lấy 2 nút tần suất nhỏ nhất, tạo nút cha với tần suất bằng tổng, đưa lại vào heap. Duyệt cây để tạo bảng mã (trái = 0, phải = 1).
Lời giải tham khảo
Xem lời giải
python
def activity_selection(activities):
sorted_acts = sorted(activities, key=lambda x: x[1])
result = [sorted_acts[0]]
for i in range(1, len(sorted_acts)):
if sorted_acts[i][0] >= result[-1][1]:
result.append(sorted_acts[i])
return result
def fractional_knapsack(items, capacity):
sorted_items = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
total_value = 0.0
remaining = capacity
for weight, value in sorted_items:
if remaining >= weight:
total_value += value
remaining -= weight
else:
total_value += value * (remaining / weight)
break
return total_value
def job_scheduling(jobs):
sorted_jobs = sorted(jobs, key=lambda x: x[2], reverse=True)
max_deadline = max(j[1] for j in sorted_jobs)
slots = [None] * (max_deadline + 1)
total_profit = 0
schedule = []
for job_id, deadline, profit in sorted_jobs:
for slot in range(deadline, 0, -1):
if slots[slot] is None:
slots[slot] = job_id
total_profit += profit
schedule.append(job_id)
break
return total_profit, schedule