TRƯỜNG ĐẠI HỌC TÂY ĐÔKHOA KỸ THUẬT-CÔNG NGHỆ NIÊN LUẬN 1CHUYÊN NGÀNH CÔNG NGHỆ THÔNG TIN BÀI TOÁN CÁI BALÔ BẰNG KĨ THUẬTTHAM VỚI SỐ LƯỢNG KHÔNG HẠN CHẾ Cán bộ hướng dẫn: Sinh viên thực hiện: Th.s: Lâm Tấn Phương Phan Thị Kiều Mỵ 197060027 Lê Nguyễn Nhật Minh 197060065 Cần Thơ, năm 2021  NỘI DUNGCHƯƠNG I: TỔNG QUAN1.LỜI MỞ ĐẦU Balo là một vật dụng thông thường được sử dụng hàng ngày trong cuộc sống, giúp chúng ta mang theo những vật dụng cần thiết nhất. Tuy nhiên balo chỉ có thể chứa được một khối lượng vật dụng nhất định vì vậy chúng tacần lựa chọn những vật dụng có giá trị nhất, cần thiết nhất để đem theo. Từ việc chọn những vật dụng có giá trị nhất để cho vào balo nên người ta đã lấy tên “Bài toán cái balo” để đặt tên cho một dạng bài toán này.Bài toán xếp ba lô (còn được biết đến bài toán cái túi) là một dạng bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với khối lượng nhất định) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp tính toán, mật mã học và ứng dụng. 2.MÔ TẢ BÀI TOÁN Đặt các đồ vật vào balo sao cho giá trị của cái balo là cao nhất nhưng vẫn đảm bảo được khối lượng của balo. Giả sử có 5 món đồ có giá trị lần lượt là 10$, 4$, 2$, 2$, 1$ và khối lượng của 5 món đồ lần lượt là 4kg, 12kg, 2kg, 1kg, 1kg. Khối lượng mà chiếc balocó thể chứa là 15kg. Vấn đề của chúng ta là chọn đồ vật như thế nào để giá trị của balo là nhiều $ nhất và đảm bảo khối lượng của balo không vượt quá 15kg. Hinh 1: mô tả bà toán cá tú. 3.Kiến thức cần có -Trang bị kiến thức về toán học.-Nắm vũng ngôn ngữ lập trình C, C++,….-Nắm vững lí thuyết cơ bản về cấu trúc dữ liệu và giải thuật để lựa chọn đồ vật sao cho hợp lí.-Dịch chương trình sang file thực thi. 4.Hướng giải quyết: Các bước giải quyết bài toán: Tính đơn giá cho các loại đồ vật. Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ. Với mỗi loại đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của bao cho phép Xác định trọng lượng còn lại của balo và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa. 5.Kế hoạch thực hiện Đề tài dự kiến hoàn thành sau 8 tuần, cụ thể như sau: Tìm hiểu thuật toán: 1 tuần. Lập trình demo cho ví dụ đã nêu, code demo: 2 tuần Tham số hóa chương trình để xét mọi dữ liệu nhập vào. Nộp chương trình: 2 tuần. Tinh chỉnh phần mềm, nộp phần mềm chỉnh sửa: 2 tuần. Viết tài liệu, nộp tài liệu: 1 tuần. |
