Nội dung

Giải các bài toán tin bằng phương pháp QUY HOẠCH ĐỘNG Có thể tóm lược nguyên lý QHĐ do Bellman phát biểu như sau: Quy hoạch động là lớp các bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các bước đã xử lý trước đó.  Nhận dạng các bài toán có thể giải bằng phương pháp quy hoạch động. Một bài toán P muốn giải bằng phương pháp quy hoạch động cần có 2 đặc điểm sau: - Bài toán P thỏa mãn nguyên lý tối ưu Bellman, nghĩa là có thể sử dụng lời giải tối ưu của các bài toán con từ mức thấp nhất để tìm dần lời giải tối ưu cho bài toán con ở mức cao hơn và cuối cùng là lời giải tối ưu cho bài toán P. - Bài toán P có các bài toán con phủ chồng lên nhau, nghĩa là không gian bài toán con “hẹp” không tạo dạng hình cây.  Các bước giải quyết bài toán bằng phương pháp quy hoạch động. Bước 1:Xây dựng hàm mục tiêu Áp dụng nguyên lý tối ưu của Bellman ta phân rã bài toán ban đầu thành các bài toán con có cùng cấu trúc sao cho việc giải quyết bài toán con cấp i phụ thuộc vào kết quả của các bài toán con trước đó. Cụ thể hóa bước này là ta phải xây dựng được hàm mục tiêu F(i) là nghiệm của bài toán con cấp i. Bước 2: Xác định các bài toán cơ sở. Bài toán cơ sở là các bài toán con nhỏ nhất mà ta có thể biết ngay kết quả hoặc tính được kết quả dễ dàng. Đây chính là cơ sở để tính nghiệm cho các bài toán cấp lớn hơn. Bước 3: Xây dựng công thức truy hồi Căn cứ vào ý nghĩa của hàm mục tiêu, tìm mối quan hệ giửa các bài toán con các cấp, ta tiến hành xây dựng công thức tính kết quả của bài toán cấp i dựa vào kết quả của các bài toán con cấp trước đó. Bước 4: Lập bảng phương án Sử dụng công thức truy hồi và nghiệm các bài toán cơ sở tính nghiệm tất cả các bài toán con và lưu trữ chúng vào bảng phương án. Bước 5: Kết luận nghiệm của bài toán. Dựa vào bảng phương án chỉ ra nghiệm của bài toán. Các bước bước giải quyết trên tuy rất cụ thể nhưng vẫn trừu tượng đối với học sinh. Để các em bước đầu làm quen ta cùng nhau giải quyết các bài toán đơn giản sau: Bài toán 1: Tìm số Fibonaci thứ N? Bước 1: Hàm mục tiêu F(i) là số fibonaci thứ i. Bước 2: Các bài toán cơ sở F(1) = 1; F(2) = 1 Bước 3: Công thức truy hồi: F(i) = F(i-1) + F(i-2) Bước 4: Bảng phương án i F(i) 1 1 2 1 3 2 4 3 5 5 6 8 7 13 … … Bước 5: Nghiệm F(N) Bài toán 2: Di chuyển quân tốt. Cho một bàn cờ kích thước NxN. Các dòng từ trên xuống dưới, các cột từ trái qua phải được đánh số từ một đến N. Ô nằm ở hàng i, cột j gọi là Ô(i, j). Người ta đặt một con tốt trắng tại Ô(1,1) và M con tốt đen trên các ô còn lại của bàn cờ sao cho không có 2 con tốt nào nằm trên cùng một ô. Ta có thể di chuyển con tốt trắng sang ô bên phải, hoặc xuống dưới ô đang chứa nó nếu như ô đó không chứa tốt đen. Bạn hãy tính xem có bao nhiêu cách di chuyển tốt trắng đến Ô(N, N). Bước 1: Hàm mục tiêu F(i, j) là số cách di chuyển quân tốt trắng đến O(i, j). Bước 2: Các bài toán cơ sở F(0,j) = 0 j:1..N ; F(i,0) = 0 i:1..N F(1,1) = 0; F(u, v) =0 (u, v) là tọa độ các quân tốt đen Bước 3: Công thức truy hồi Ta thấy chỉ đứng ở O(i-1, j) và O(i, j-1) mới có thể để đến được O(i, j). Do đó số cách đến được O(i, j) bằng số cách đến O(i-1, j) cộng với số cách đến O(i,j-1) Ta được: F(i, j) = F (i-1, j) + F(i, j-1) Bước 4: Bảng phương án 0 1 2 3 4 5 6 1 T 2 D 3 4 D D 5 6 D Minh họa hiện trạng bàn cờ Bước 5: Nghiệm F(N, N) = 42 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 2 3 0 1 2 0 1 0 3 3 4 0 0 1 1 4 7 11 11 0 1 2 6 0 11 22 Bảng phương án 0 1 3 9 9 20 42 Dạng 1: Tìm dãy các phần tử là dãy con dài nhất thỏa mãn điều kiện bài toán. Phương pháp chung + Hàm mục tiêu: F(i) là độ dài dãy con + Bài toán cơ sở: F(1) = 1 + Công thức truy hồi: F(i) = Max {1, F(j)+1 } với A j và Ai thỏa điều kiện bài toán + Bảng phương án: Dùng mảng 1 chiều lưu trữ. + Nghiệm bài toán: F(N) Các bài tập áp dụng: Bài 1: Xếp Tháp Tên chương trình: Tower.Pas Một lần nữa, Bờm lại thể hiện được mình không chỉ là người học giỏi mà chơi cũng rất giỏi. Ở lớp Bờm, các bạn đang rất thích chơi xếp tháp và cậu đang thể hiện mình là người vô địch trong trò chơi này khi thắng rất nhiều bạn cùng lớp. Liệu bạn có thể thắng được Bờm? Ở trò chơi này, người chơi được cho N hình trụ đứng với nhiều kích thước khác nhau và yêu cầu người chơi xếp được tòa tháp cao nhất từ các hình trụ theo đúng thứ tự từ 1 đến N sao cho khối ở trên phải được xếp khít với khối ở dưới, hay đường kính đáy của hình trên không vượt quá đường kính đáy hình dưới. Một khối trụ có thể dùng hoặc không dùng nhưng phải đúng theo thứ tự đã cho. Dữ liệu: Cho từ file Tower.Inp Dòng đầu ghi số N (N≤ 1000000) N dòng tiếp theo mỗi dòng ghi 2 số Ri và Hi là bán kính đáy và chiều cao hình trụ thứ i. Kết quả: Ghi ra file Tower.Out Một số nguyên duy nhất là chiều cao lớn nhất của tòa tháp xếp được. Ví du: Tower.Inp 4 4 2 2 5 1 3 3 1 Tower.Out 10 Nhận xét: Đây là bài toán tìm dãy con không tăng theo Ri có tổng chiều cao lớn nhất. Hướng dẫn Gọi F[i] là độ cao lớn nhất của tòa tháp xếp được với khối i là đỉnh. F[i] = H[i] i:1..N; Công thức truy hồi: Nếu khối i xếp được trên khối j (1≤ j < i) hay R[i] ≤ R[j].Ta được: F[i] = Max{F[j]+H[i]} j:1..i-1. Nghiệm bài toán: Max{F[i]} i:1..N Bài 2: Dãy số WAVIO: Dãy số Wavio là dãy số nguyên thỏa mãn các tính chất : các phần tử đầu sắp xếp thành 1 dãy tăng dần đến 1 phần tử đỉnh sau đó giảm dần. Ví dụ dãy số 1 2 3 4 5 2 1 là 1 dãy Wavio độ dài 7. Cho 1 dãy gồm N số nguyên, hãy chỉ ra một dãy con Wavio có độ dài lớn nhất trích ra từ dãy đó . Hướng dẫn: - L1[i] là độ dài lớn nhất của 1 dãy con tăng dần của dãy A1, A2,...Ai . - L2[i] là độ dài lớn nhất của 1 dãy con giảm dần của dãy Ai, A2,...AN. - Công thức truy hồi giống như bài toán dãy con tăng. - Nghiệm bài toán: Tìm phần tử j trong 2 mảng L1, L2 thỏa mãn L1[j]+L2[j] lớn nhất. Bài 3: Xâu con đối xứng Tên chương trình: Palin.Pas Xâu đối xứng là xâu mà khi đọc từ bên trái sang phải hay ngược lại đều cho một kết quả. Bạn hãy tìm một xâu con đối xứng dài nhất của một xâu cho trước. Xâu con của một xâu S có được bằng cách bỏ đi một số kí tự của S. Dữ liệu: Palin.Inp gồm một dòng duy nhất ghi xâu S có độ dài không quá 10000 kí tự. Kết quả: Palin.Out gồm một số duy nhất là độ dài lớn nhất tìm được Ví du: Palin.Inp Palin.Out banana 5 Hướng dẫn Gọi F[i,len] là chỉ số j lớn nhất sao cho j ≤ i và trong đoạn xâu kí tự j đến kí tự thứ i có tồn tại xâu con đối xứng có độ dài len. Nếu không tìm được j thì F[j, len]=0. F[i, 1] = i i:1..N F[i, 2] bằng Max của F[i-1, 2] và j với j lớn nhất nhỏ hơn i và kí tự thứ j bằng kí tự thứ i trong xâu ban đầu. Công thức truy hồi: - F[i, len] = F[i-1, len] nếu không chọn kí tự i vào xâu đối xứng. - F[i, len] = giá tri j lớn nhất nhỏ hơn F[i-1, len-2] và kí tự thứ j bằng kí tự thứ i. Dạng 2: Tìm dãy các phần tử là dãy con chung dài nhất Phương pháp chung Giả sử cho 2 dãy A1, A2,…, AM; B1, B2,…, BN (Các phần tử của dãy có thể là số hoặc kí tự). Yêu cầu tìm dãy con chung dài nhất của hai dãy đã cho. +Hàm mục tiêu: F(i, j) là độ dài dãy con chung dài nhất của hai dãy A 1, A2, …, Ai; B1, B2,…, Bj. + Các bài toán cơ sở: F(0, j) = 0 = F(i, 0) i:1..M; j:1..N + Công thức truy hồi: Nếu A[i]=B[j] thì F(i, j) = F(i-1, j-1) +1 Ngược lại F(I, j) = Max(F(i-1, j), F(i, j-1) + Bảng phương án: Dùng mảng hai chiều để lưu trữ. + Nghiệm bài toán: F(M, N) Các bài tập áp dụng: Bài 1: Xâu con chung dài nhất Cho 2 xâu X,Y. Hãy tìm xâu con của X và của Y có độ dài lớn nhất. Hướng dẫn - Gọi L(i,j) là độ dài xâu con chung dài nhất của xâu X(i) gồm i kí tự phần đầu của X (X(i)=X[1..i]) và xâu Y(j) gồm j kí tự phần đầu của Y (Y(j) =Y[1..j]). - Bài toán cơ sở L(0,j)=L(i,0)=0. - Công thức truy hồi L(i,j) = L(i 1,j 1)+1 nếu X[i] = Y[j]. L(i,j) = max(L(i 1,j), L(i,j 1)) nếu X[i]≠Y[j]. Bài 2: Dãy con chung bội hai dài nhất Tên chương trình: Lcs2x.Pas Dãy C = c1, c2, .. ck được gọi là dãy con của dãy A = a1, a2, .., an nếu C có thể nhận được bằng cách xóa bớt một số phần tử của dãy A và giữ nguyên thứ tự của các phần tử còn lại, nghĩa là tìm được dãy các chỉ số 1 ≤ l1 < l2 < … < lk ≤ n sao cho c1 = a_l1, c2 = a_l2, …, ck = a_lk. Ta gọi độ dài của dãy là số phần tử của dãy. Cho hai dãy A = a1, a2, …, am và B = b1, b2, …, bn Dãy C = c1, c2, …, ck được gọi là dãy con chung bội hai của dãy A và B nếu C vừa là dãy con của dãy A, vừa là dãy con của dãy B và thỏa mãn điều kiện 2 × ci ≤ c(i+1) (i = 1, 2, …, k – 1). Yêu cầu Cho hai dãy A và B. Hãy tìm độ dài dãy con chung bội hai có độ dài lớn nhất của hai dãy A và B. Input (Lcs2x.Inp) Dòng đầu tiên chứa T là số lượng bộ dữ liệu. Tiếp đến là T nhóm dòng, mỗi nhóm cho thông tin về một bộ dữ liệu theo khuôn dạng sau:  Dòng đầu chứa 2 số nguyên dương m và n.  Dòng thứ hai chứa m số nguyên không âm a1, a2, ..., am mỗi số không vượt quá 109.  Dòng thứ ba chứa n số nguyên không âm b1, b2, ..., bn mỗi số không vượt quá 109.  Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. Giới hạn  30% số test có m, n <= 15.  30% số test khác có m, n <= 150.  có 40% số test còn lại có m, n <= 1500. Output (Lcs2x.Out) Ghi ra T dòng, mỗi dòng ghi một số nguyên là độ dài dãy con chung bội hai dài nhất của dãy A và B tương ứng với bộ dữ liệu vào. Example Lcs2x.Inp 1 5 5 5 1 6 10 20 1 8 6 10 20 Lcs2x.Out 3 Hướng dẫn: Gọi F[i, j] là độ dài dãy con chung dài nhất của dãy A[1..i] và dãy B[1..j] thỏa điều kiện đề bài và A[i]=B[j]. Công thức truy hồi: - Nếu A[i]<>B[j] thì F[i, j]=0 - F[i, j]= Max{F[u, v]/ u 1) Bờm mua chuộc tên cướp thứ i thì F[i, j] = F[i-1, j-T[i]]+H[i] (điều kiện: F[i-1, j-T[i]] ≠ -1) Bờm không mua chuộc tên cướp thứ i thì F[i, j] = F[i-1, j] (điều kiện: F[i-1, j] ≥ H[i]) Nghiệm của bài toán là j nhỏ nhất sao cho F[n, j] <> -1 hoặc F[n,v] nếu F[n,v]= -1. Bài 2: Hệ thống tiền tệ Tên chương trình: Money.Pas Chúng ta hãy cùng theo dõi một hệ thống tiền tệ rất riêng. Đó là giá trị của những đồng xu. Thông thường các đồng xu có các giá trị nhứ, 5, 10, 20 đơn vị, đôi khi đồng xu 2 đơn vị cũng được dùng để đo lường tốt hơn. Mọi người đều muốn biết có bao nhiêu cách khác nhau để có thể lấy ra một lượng tiền cho trước bằng cách dùng các hệ thống tiền xu khác nhau. Ví dụ dùng hệ thống [1, 2,…,18] có thể lấy ra 18 đồng bằng nhiều cách khác nhau như: 1 xu 18 đơn vị, 2 xu 9 đơn vị, 2 xu 8 đơn vị và 2 xu 1 đơn vị,… và nhiều cách khác. Yêu cầu: Với hệ thống tiền xu cho trước và một lượng tiền S hãy cho biết có bao nhiêu cách lấy được số tiền S từ hệ thống tiền xu đã có. Dữ liệu: Cho từ file Money.Inp - Dòng đầu ghi hai số N (1A[i]) Bài 3: Du lịch vòng quanh thế giới Tên chương trình: Travel.Pas Trên tuyến đường của xe chở khách du lịch vòng quanh thế giới xuất phát từ bến X có N khách sạn đánh số từ 1 đến N theo thứ tự xuất hiện trên tuyến đường, trong đó khách sạn N là địa điểm cuối cùng của hành trình mà tại đó tài xế bắt buộc phải dừng. Khách sạn i cách địa điểm xuất phát Ai Km (i=1, 2, …, N); A1

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.