CÁCH GIẢI MỘT SỐ BÀI TOÁN TRONG PASCAL - TIN HỌC 11

Tài liệu đính kèm: Tải về

Khi giải quyết các bài toán trong tin học,  có rất nhiều bài toán sẽ phải áp dụng phương pháp quy hoạch động (Dynamic Programming). Quy hoạch động là kĩ thuật được được dùng khi có một công thức và một (hoặc một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã tìm ra trước đó. Quy hoạch động có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui. Để hiểu rõ về phương pháp quy hoạch động, mời các bạn theo dõi các ví dụ cụ thể sau:

1. Dãy con đơn điệu dài nhất

1.1. Mô hình

Cho dãy A1,A2,...,AnA1,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:

  • 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ử AA trong 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ị.
  • 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ể.

1.2. Công thức QHĐ

Hàm mục tiêu: ff: độ dài dãy con.

Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi LiLi là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ A1A1 đến AiAi và phần tử cuối cùng là AiAi.

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 nn 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 ii 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 LiLi như sau:

  • L1=1L1=1. (Hiển nhiên)
  • Li=max(1,Lj+1)Li=max(1,Lj+1) với mọi phần tử jj thỏa mãn: 0<j<i0 và AjAiAj≤Ai

Tính LiLi: phần tử đang được xét là AiAi. Ta tìm đến phần tử Aj<AiAj có LjLj lớn nhất. Khi đó nếu bổ sung AiAi vào sau dãy con ...Aj...Aj ta sẽ được dãy con tăng dần dài nhất xét từ A1...AiA1...Ai.<>

1.3. Cài đặt

Bảng phương án là một mảng một chiều LL để lưu trữ các giá trị của hàm QHĐ LiLi. Đoạn chương trình tính các giá trị của mảng LL như sau:

for i:= 1 to n do
   begin
         L[i]:=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 độ phức tạp bộ nhớ của bài toán là O(n)O(n), độ phức tạp thời gian là O(n2)O(n2).

Có một số 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)O(nlogn), một trong những cách đó là dùng Segment Tree.

1.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ó thể coi chúng như là một. Sau đây là một số bài toán khác.

Bố trí phòng họp (mất tính thứ tự so với dãy ban đầu)

Bài toán:

nn cuộc họp, cuộc họp thứ ii bắt đầu vào thời điểm AiAi và kết thúc ở thời điểm BiBi. Do chỉ có một phòng hội thảo nên 2 cuộc họp bất kì sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của chúng chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để phục vụ được nhiều cuộc họp nhất.

Hướng dẫn:

Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc BiBi. Thế thì cuộc họp ii sẽ bố trí được sau cuộc họp jj khi và chỉ khi j<ijBjAiBj≤Ai. Yêu cầu bố trí được nhiều cuộc họp nhất có thể đưa về việc tìm dãy các cuộc họp dài nhất thoả mãn điều kiện trên.<>

Cho thuê máy

Bài toán:

Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của nn khách hàng. Khách hàng ii muốn sử dụng máy trong khoảng thời gian từ aiai đến bibi và trả tiền thuê là cici. Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê).

Bài tin liên quan
Tin đọc nhiều
Liên kết website
Thống kê truy cập
Hôm nay : 13
Hôm qua : 51
Tháng 08 : 832
Năm 2018 : 7.723