Bài giảng Toán rời rạc - Bài toán tối ưu
Bài toán tối ưu
TOÁN RỜI RẠC
NỘI DUNG
Giới thiệu
Kỹ thuật nhánh cận
Kỹ thuật nhánh cận giải bài toán người bán hàng
GIỚI THIỆU
Bài toán tối ưu: Là bài toán tìm ra tổ hợp tốt nhất trong
những tổ hợp có thể tạo ra, thỏa mãn yêu cầu cho trước.
Tối ưu tổ hợp có rất nhiều ứng dụng trong thực tế.
MỘT SỐ BÀI TOÁN TỐI ƯU
Xếp ba lô (1): có 1 chiếc ba lô, mang được không quá
trọng lượng b. Có n đồ vật với trọng lượng: a1, …, an và
giá trị c1, …, cn tương ứng. Hỏi ta xếp vào ba lô những
vật nào để mang được giá trị lớn nhất?
Xếp ba lô (2): tương tự như bài 1 nhưng mỗi loại đồ vật
có thể mang theo từ 0->m lần