Bài giảng Thiết kế và đánh giá thuật toán: Tham ăn - TS. Lê Nguyên Khôi

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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Tham ăn - TS. Lê Nguyên KhôiThiết Kế & Đánh Giá Thuật ToánTham ĂnTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNội DungBài toánTrả tiền thừa Ba lôChiến lược tham ăn Cây bao trùm nhỏ nhấtThuật toán Prim Thuật toán Kruskal1Bài Toán Trả Tiền ThừaCá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 189c189 xu 1c => 189 18 xu 10c, 1 xu 5c, 4 xu 1c => 232Bài Toán Trả Tiền ThừaSố 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ấtVí dụ: trả lại 189c1 xu 100c, 3 xu 25c, 1 xu 10c, 4 xu 1c => 9 9 xu đã ít nhất chưa3Lập Trình Động – Nhắc LạiThường áp dụng cho bài toán tối ưu Xác định được lời giải tối ưuDựa trên lời giải tối ưu các bài toán conCó 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 lâu4