Một số bài toán quy hoạch động điển hình

Nội dung text: Một số bài toán quy hoạch động điển hình

1. 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 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 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ó thể coi chúng như là một. Sau đây là một số bài toán khác. a) Bố trí phòng họp( mất tính thứ tự so với dãy ban đầu) Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm ai và kết thúc ở thời điểm bi. 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 (bi). Thế thì cuộc họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu j<i và bj<=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. b) Cho thuê máy Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của n khách hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ ai đến bi và trả tiền thuê là ci. 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ê). Hướng dẫn: Tương tự như bài toán a), nếu sắp xếp các đơn đặt hàng theo thời điểm kết thúc, ta sẽ đưa được bài toán b) về bài toán tìm dãy con có tổng lớn nhất. Bài toán này là biến thể của bài toán tìm dãy con tăng dài nhất, ta có thể cài đặt bằng đoạn chương trình như sau: for i:=1 to n do begin L[i]:=c[i]; for j:=1 to i–1 do if (b[j]<=a[i]) and (L[i]<L[j]+c[i]) then L[i]:=L[j]+c[i]; end; c) Dãy tam giác bao nhau Cho n tam giác trên mặt phẳng. Tam giác i bao tam giác j nếu 3 đỉnh của tam giác j đều nằm trong tam giác i (có thể nằm trên cạnh). Hãy tìm dãy tam giác bao nhau có nhiều tam giác nhất. Hướng dẫn: Sắp xếp các tam giác tăng dần về diện tích. Khi đó tam giác i sẽ bao tam giác j nếu j<i và 3 đỉnh của j nằm trong i. Từ đó có thể đưa về bài toán tìm dãy “tăng” dài nhất. Trang 2
2. • Các dòng sau ghi các khối được chọn, mỗi khối đá ghi 4 số T, D, R, C trong đó T là số thứ tự của mỗi khối đá. D, R, C là kích thước của khối đá tương ứng. II. Vali (B) 1. Mô hình Có n đồ vật, vật thứ i có trọng lượng a[i] và giá trị b[i]. Hãy chọn ra một số các đồ vật, mỗi vật một cái để xếp vào 1 vali có trọng lượng tối đa W sao cho tổng giá trị của vali là lớn nhất. 2. Công thức Hàm mục tiêu : f: tổng giá trị của vali. Nhận xét : giá trị của vali phụ thuộc vào 2 yếu tố: có bao nhiêu vật đang được xét và trọng lượng của các vật. Do đó bảng phương án sẽ là bảng 2 chiều. L[i,j] : tổng giá trị lớn nhất của vali khi xét từ vật 1 vật i và trọng lượng của vali chưa vượt quá j. Chú ý rằng khi xét đến L[i,j] thì các giá trị trên bảng phương án đều đã được tối ưu. • Tính L[i,j] : vật đang xét là ai với trọng lượng của vali không được quá j. Có 2 khả năng xảy ra : • Nếu chọn aiđưa vào vali, trọng lượng vali trước đó phải ≤ j-a[i]. Vì mỗi vật chỉ được chọn 1 lần nên giá trị lớn nhất của vali lúc đó là L[i-1,j-a[i]) + b[i] • Nếu không chọn ai , trọng lượng của vali là như cũ (như lúc trước khi chọn ai ): L[i-1,j]. Tóm lại ta có L[i,j]=max(L(i-1,j-a[i]) + b[i], L[i-1,j]). 3. Cài đặt For i:=1 to n do For j:=1 to W do If b[i]<=j then L[i,j]:=max(L(i-1,j-a[i]) + b[i], L[i-1,j]) else L[i,j]:=L[i-1,j]; 4. Một số bài toán khác a) Dãy con có tổng bằng S: Cho dãy a1,a2, an. Tìm một dãy con của dãy đó có tổng bằng S. Hướng dẫn Đặt L[i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1,a2, ai. Ngược lại thì L[i,t)=0. Nếu L[n,S)=1 thì đáp án của bài toán trên là “có”. Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i–1,t–a[i]]=1. Cài đặt Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i–1. Bảng phương án khi đó chỉ cần 1 mảng 1 chiều L[0 S] và được tính như sau: L[t]:=0; L[0]:=1; for i := 1 to n do for t := S downto a[i] do if (L[t]=0) and (L[t–a[i]]=1) then L[t]:=1; Trang 4
3. Hướng dẫn: Gọi T là tổng n số nguyên đó. Giả sử ta chia dãy thành 2 nhóm, gọi S là tổng của một nhóm, tổng nhóm còn lại là T–S và tích của tổng 2 nhóm là S*(T–S). Bằng phương pháp đánh dấu ta xác định được mọi số S là tổng của một nhóm (như bài Market) và tìm số S sao cho S*(T–S) đạt max. III. Biến đổi xâu: 1. Mô hình Cho 2 xâu X,F. Xâu nguồn có n kí tự X1X2 Xn , xâu đích có m kí tự F1F2 Fm .Có 3 phép biến đổi : • Chèn 1 kí tự vào sau kí tự thứ i :I i C • Thay thế kí tự ở vị trí thứ i bằng kí tự C : R i C. • Xoá kí tự ở vị trí thứ i. D i Hãy tìm số ít nhất các phép biến đổi để biến xâu X thành xâu F. Hướng dẫn: Hàm mục tiêu : f: số phép biến đổi. Dễ thấy số phép biến đổi phụ thuộc vào vị trí i đang xét của xâu X và vị trí j đang xét cuả xâu F. Do vậy để cài đặt cho bang phương án ta sẽ dùng mảng 2 chiều Gọi L(i,j) là số phép biến đổi ít nhất để biến xâu X(i) gồm i kí tự phần đầu của X (X(i)= X[1 i]) thành xâu F(j) gồm j kí tự phần đầu của F(F(j) =F[1 j]). Dễ thấy F(0,j)=j và F(i,0)=i. Có 2 trường hợp xảy ra: Nếu X[i]=F[j] : X X1X2 Xi-1 i X F1F2 Fj-1 i thì ta chỉ phải biến đổi xâu X(i-1) thành xâu Y(j-1). Do đó F(i,j)=F(i-1,j-1). Ngược lại, ta có 3 cách biến đổi: X Xoá kí tự X[i]: X1X2 Xi-1 i Fj F1F2 Fj-1 Xâu X(i-1) thành F(j). Khi đó F(i,j)=F(i-1,j)+1.(Cộng 1 là do ta đã dùng 1 phép xóa) Fj Thay thế X[i] bởi F[j] : X1X2 Xi-1 Fj F1F2 Fj-1 Xâu X(i-1) thành F(j-1). Khi đó F(i,j)=F(i-1,j-1)+1. Chèn F[j] vào X(i): X1X2 Xi-1XiFj Fj F1F2 Fj-1 Xâu X(i) thành Y(j-1). Khi đó F(i,j)=F(i,j-1)+1. Tổng kết lại, ta có công thức QHĐ: • F(0,j)=j • F(i,0)=i Trang 6
4. cầu không được cắt nhau và mỗi thành phố chỉ là đầu cầu cho nhiều nhất là một cây cầu, hãy chỉ ra cách bắc cầu được nhiều cầu nhất. Hướng dẫn: Gọi các thành phố của Anpha lần lượt là a1,a2, am; các thành phố của Beta là b1,b2, bn. Nếu thành phố ai và bj kết nghĩa với nhau thì coi ai “bằng” bj. Để các cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố (ai,bj) để xây cầu thì cặp tiếp theo phải là cặp (au,bv) sao cho u>i và v>j. Như vậy các cặp thành phố được chọn xây cầu có thể coi là một dãy con chung của hai dãy a và b. Bài toán của chúng ta trở thành bài toán tìm dãy con chung dài nhất, ở đây hai phần tử “bằng” nhau nếu chúng có quan hệ kết nghĩa. d) Palindrom (IOI 2000) Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Hướng dẫn: Bài toán này có một công thức QHĐ như sau: Gọi L(i,j) là số kí tự ít nhất cần thêm vào xâu con S[i j] của S để xâu đó trở thành đối xứng. Đáp số của bài toán sẽ là L(1,n) với n là số kí tự của S. Ta có công thức sau để tính L(i,j): • L(i,i)=0. • L(i,j)=L(i+1,j–1) nếu S[i]=S[j] • L(i,j)=max(L(i+1,j), L(i,j–1)) nếu S[i]≠S[j] Bạn đọc dễ dàng có thể kiểm chứng công thức đó. Ta có thể cài đặt trực tiếp công thức đó bằng phương pháp đệ quy có nhớ. Tuy nhiên khi đó chi phí không gian là O(n2). Có một phương pháp cài đặt tiết kiệm hơn (bạn đọc có thể tham khảo ở bài báo trên của thầy Trần Đỗ Hùng), tuy nhiên phương pháp đó khá phức tạp. Ta có thuật toán đơn giản hơn như sau: Gọi P là xâu đảo của S và T là xâu con chung dài nhất của S và P. Khi đó các kí tự của S không thuộc T cũng là các kí tự cần thêm vào để S trở thành đối xứng. Đáp số của bài toán sẽ là n–k, với k là độ dài của T. Ví dụ: S=edbabcd, xâu đảo của S là P=dcbabde. Xâu con chung dài nhất của S và P là T=dbabd. Như vậy cần thêm 2 kí tự là e và c vào để S trở thành xâu đối xứng. IV. Vali (A) 1. Mô hình Cho n vật, vật i nặng ai và có giá trị bi. Hãy chọn ra một số vật để cho vào balô sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. Chú ý rằng mỗi vật có thể được chọn nhiều lần. 2. Công thức Gọi L(i,j) là tổng giá trị lớn nhất khi được chọn i vật từ 1 đến i cho vào balô với tổng khối lượng không vượt quá j. L(n,W) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật và tổng khối lượng không vượt quá W). Công thức tính L(i,t) như sau: Trang 8
5. Do đó ta cũng xây dựng hàm QHĐ một cách tương tự: Gọi L(i,t) là số đồng xu ít nhất nếu đổi t đồng ra i loại tiền xu (từ 1 đến i). Công thức tính L(i,t) như sau: • L(i,0)=0; • L(0,t)= ∞ với t>0. • L(i,t)=L(i–1,t) nếu t i+1 thì ta thấy có thể tính Ai.Ai+1 Aj bằng cách chọn một vị trí k nào đó để đặt ngoặc theo trình tự: Ai.Ai+1 Aj = (Ai Ak).(Ak+1 Aj) × Ma trận kết quả của phép nhân (Ai Ak) có kích thước di–1 dk, ma trận kết quả của phép nhân × (Ak+1 Aj) có kích thước dk dj. Với cách đặt đó ta sẽ mất F(i,k) phép nhân để có kết quả trong dấu ngoặc thứ nhất, mất thêm F(k+1,j) phép nhân để có kết quả trong dấu ngoặc thứ hai, và cuối cùng mất di–1.dk.dj để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt .d .d . đó là: F(i,k)+F(k+1,j)+di–1 k j Ta chọn vị trí k cho số phép nhân ít nhất. Trang10
6. • F(i,i)=ai • F(i,i+1)=ai•ai+1 • F(i,j)=max(F(i,k)•F(k+1,j) với k=i+1,i+2, j–1). (Chú là là các hạng tử của dãy đều không âm và các phép toán là + hoặc × nên F(i,k) và F(k+1,j) đạt max thì F(i,k)•F(k+1,j) cũng đạt max). VI. Ghép cặp 1.Mô hình Có n lọ hoa sắp thẳng hàng và k bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cằm k bó hoa trên vào n lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ tương ứng khi cắm hoa i vào lọ thứ j là v(i,j) Hãy tìm 1 cách cắm sao cho tổng giá trị thẫm mỹ là lớn nhất. Chú ý rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được 1 bó hoa. (IOI –1999) 2. Công thức : Nhận xét rằng bài toán nêu trên là một bài toán ghép cặp có yêu cầu về thứ tự nên ta có thể giải quyết bằng phương pháp QHĐ. Hàm mục tiêu : f: tổng giá trị thẩm mỹ của cách cắm. Giá trị thẩm mỹ phụ thuộc vào các hoa và các lọ đang được xét nên ta sẽ dùng mảng 2 chiều để lưu bảng phương án. L(i,j): tổng giá trị thẩm mỹ lớn nhất khi xét đến hoa i và lọ j. Khi tính L(i,j) hoa đang xét sẽ là hoa i và lọ j. • Nếu i = j. Chỉ có một cách cắm L(i,i):= v[1,1]+v[2,2]+ v[i,i] • Nếu i>j . Không có cách cắm hợp lý • Nếu i<j : Có 2 trường hợp xảy ra: Cắm hoa i vào lọ j. Tổng giá trị thẩm mỹ là L(i-1,j-1)+v(i,j). (Bằng tổng giá trị trước khi cắm cộng với giá trị thẩm mỹ khi cắm hoa i vào lọ j) Không cắm hoa i vào lọ j (có thể cắm vào lọ trước j), giá trị thẫm mỹ của cách cắm là như cũ : L(i,j-1) 3. Cài đặt : L[i,j]:= -maxint; For i:=1 to k do For j:=i to n do If i = j then L[i,j]:=sum(i) else if i<j then L[i,j]:=max(L[i-1,j-1]+v[i,j],L[i,j-1]); 4. Một số bài toán khác a) Câu lạc bộ:( Đề thi chọn HSG Tin Hà Nội năm 2000) Có n phòng học chuyên đề và k nhóm học được đánh số thứ tự từ nhỏ đến lớn. Cần xếp k nhóm trên vào n phòng học sao cho nhóm có số hiệu nhỏ được xếp vào phòng có số hiệu nhỏ, nhóm có số hiệu lớn phải được xếp vào phòng có số hiệu lớn.Với mỗi phòng có chứ học sinh, các ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì lấy vào cho đủ ghế .Biết phòng i có Trang12
7. • F(1,1)=A[1,1] • F(i,1)=F(i–1,1)+A[i,1] • F(i,j)=max(F(i–1,j–1),F(i–1,j))+A[i,j] b) Con kiến Có một ống hình trụ, khi trải phẳng ra có thể là một bảng MxN ô. Giá trị A[i,j] là lượng thức ăn có ở ô ở dòng i cột j. Một con kiến xuất phát từ một ô ở mép bên trái của hình trụ và bò sang mép bên phải. Từ ô (i,j) kiến có thể bò sang 1 trong 3 ô (i–1,j+1), (i,j+1) hoặc (i+1,j+1). (Chú ý: vì ống hình trụ nên kiến đang ở dòng 1 có thể bò xuống dòng M và ngược lại). Bò qua ô nào thì kiến mang theo toàn bộ lượng thức ăn ở ô đó. Hãy tìm đường đi mà kiến kiếm được nhiều thức ăn nhất. Hướng dẫn: Để xử lí tình huống hình trụ, ta lưu dòng 0 là dòng M và dòng M+1 là dòng 1. Khi đó tương tự như bài toán ban đầu, gọi F(i,j) là lượng thức ăn kiến có được khi bò đến ô (i,j), ta thiết lập được công thức QHĐ sau: • F(i,1)=A[i,1] • F(i,j)=max(F(i–1,j–1),F(i,j–1),F(i+1,j+1))+A[i,j] với j>1 Trang14