Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận phương pháp Quy hoạch động để giải một số bài toán tối ưu phù hợp với dữ liệu bài toán; Giúp người đọc tiếp cận ngôn ngữ lập trình C++ tốt hơn trong khi lập trình. | SỞ GD amp ĐT NGHỆ AN TRƯỜNG THPT CON CUÔNG SÁNG KIẾN KINH NGHIỆM NÀ M TÊN ĐỀ TÀI PHƯƠNG PHÁP QUY HOẠCH ĐỘNG VÀ ỨNG DỤNG VÀO GIẢI MỘT SỐ BÀI TOÁN BỒI DƯỠNG HỌC SINH GIỎI THI CHUYÊN BẰNG NGÔN NGỮ LẬP TRÌNH PASCAL VÀ C Nhóm tác giả 1. Đặng Văn Hảo 2. Ngô Thị Thanh Huyền 3. Phan Thị Thuý An Lĩnh vực Tin học Đơn vị Trường THPT Con Cuông Con Cuông - Năm 2022 2 MỤC LỤC Phần I. Đặt vấn đề . 5 1. Lí do chọn đề tài . 5 2. Mục đích nghiên cứu đóng góp mới của đề tài . 5 3. Đối tượng nghiên cứu . 6 4. Phương pháp nghiên cứu . 6 5. Phạm vi nghiên cứu . 6 6. Cấu trúc của đề tài . 6 1. Cơ sở lý luận . 6 2. Cơ sở thực tiễn. 6 Phần II. Nội dung . 7 1. Cơ sở lý luận. 7 1. 1. Giới thiệu . 7 1. 2. Phương pháp quy hoạch động . 7 . Khái niệm . 7 . Đặc điểm chung của phương pháp quy hoạch động . 9 . Các bước giải bài toán bằng quy hoạch động . 9 1. 3. Cách tiếp cận quy hoạch động . 9 1. 4. Lớp các bài toán được giải bằng quy hoạch động . 9 1. 5. Ưu điểm và hạn chế của quy hoạch động. 10 . Ưu điểm. 10 . Hạn chế. 10 2. Cơ sở thực tiễn . 10 . Thực trạng của vấn đề trước khi áp dụng đề tài . 11 . Đặc điểm tình hình . 11 . Thực trạng trước khi nghiên cứu . 11 . Các giải pháp giải quyết vấn đề . 12 . Rèn luyện kỹ năng vận dụng phương pháp Quy hoạch động để giải một số bài toán cơ bản đến nâng cao . 12 . Bài toán 1. Tìm dãy con không giảm nhiều phần tử nhất . 12 . Bài toán 2. Dãy con chung dài nhất . 15 . Bài toán 3. dãy con có tổng bằng s . 19 . Bài toán 4. chia kẹo . 23 3 . Bài toán 5 Xếp đồ vật vào ba lô mỗi vật có số lượng hạn chế . 27 2. 3. Hướng dẫn giải một số bài toán bằng quy hoạch động . 32 . Bài toán 1. xâu con chung dài nhất . 32 . Bài toán 2. Cho thuê máy . 33 . Bài toán 3. Rô bốt . 35 . Một số bài toán áp dụng phương pháp quy hoạch động tự giải . 36 . Bài 1 Tổng lớn nhất . 36 . Bài toán 2 Phân tích . 37 . Bài toán 3 Bố trí phòng họp . 38 . Bài toán 4 Nối điểm . 38 . .
