Bài giảng "Thiết kế và đánh giá thuật toán: Tham ăn" cung cấp cho người học các kiến thức: Bài toán trả tiền thừa, bài toán balo, chiến lược tham ăn, cây bao trùm nhỏ nhất. nội dung chi tiết. | Thiết Kế & Đánh Giá Thuật Toán Tham Ăn TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Bài toán Trả tiền thừa Ba lô Chiến lược tham ăn Cây bao trùm nhỏ nhất Thuật toán Prim Thuật toán Kruskal 1 Bài Toán Trả Tiền Thừa Các loại đồng xu 100c, 25c, 10c, 5c, 1c Với khoản tiền cần trả lại, sao cho số lượng đồng xu là ít nhất. Ví dụ: trả lại 189c 189 xu 1c => 189 18 xu 10c, 1 xu 5c, 4 xu 1c => 23 2 Bài Toán Trả Tiền Thừa Số lượng đồng xu trả lại là ít nhất? Ý tưởng: Sử dụng lần lượt các đồng xu có mệnh giá từ lớn nhất đến nhỏ nhất Hy vọng số lượng đồng xu là ít nhất Ví dụ: trả lại 189c 1 xu 100c, 3 xu 25c, 1 xu 10c, 4 xu 1c => 9 9 xu đã ít nhất chưa 3 Lập Trình Động – Nhắc Lại Thường áp dụng cho bài toán tối ưu Xác định được lời giải tối ưu Dựa trên lời giải tối ưu các bài toán con Có thể phức tạp hóa vấn đề Không khả thi với bài toán thực tế Không gian tìm kiếm rộng Thời gian tìm kiếm .
