Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
I. Dãy con đơn điệu dài nhất 1. Mô hình Cho dãy a1,a2,an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. Đặc trưng: i) Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử aitrong dãy, khác với các bài toán của mô hình 4(đặc trưng là bài toán đổi tiền), các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn. | MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG ĐIỂN HÌNH. I. Dãy con đơn điệu dài nhất 1. Mô hình Cho dãy ai a2 .an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. Đặc trưng i Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử aitrong dãy khác với các bài toán của mô hình 4 đặc trưng là bài toán đổi tiền các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị. ii Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu. Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bao nhau. 2. Công thức QHĐ Hàm mục tiêu f độ dài dãy con. Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi L i là độ dài dãy con tăng dài nhất các phần tử lấy trong miền từ ai đến ai và phần tử cuối cùng là ai. Nhận xét với cách làm này ta đã chia 1 bài toán lớn dãy con của n số thành các bài toán con cùng kiểu có kích thước nhỏ hơn dãy con của dãy i số . Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con. Ta có công thức QHĐ để tính L i như sau L 1 1. Hiển nhiên L i max 1 L j 1 với mọi phần tử j 0 j i và aj ai . Tính L i phần tử đang được xét là ai .Ta tìm đến phần tử aj ai có L j lớn nhất. Khi đó nếu bổ sung ai vào sau dãy con .aj ta sẽ được dãy con tăng dần dài nhất xét từ a1.ai. 3. Cài đặt Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L i . Đoạn chương trình tính các giá trị của mảng L như sau for i 1 to n do begin LH 1 . for j 1 to i-1 do if a j a i and L i L j 1 then L i L j 1 end Như vậy chi phí không gian của bài toán là O n chi phí thời gian là O n2 . Có một phương pháp cài đặt tốt hơn so với phương pháp trên cho chi phí thời gian là O nlogn 4. Một số bài toán khác Bài toán dãy con đơn điệu tăng dài nhất có biến thể đơn giản nhất là bài toán dãy con đơn điệu giảm dài nhất tuy nhiên chúng ta có .
