Cơ Sở Quy Hoạch Động (Bài Toán Nhỏ Nhất):

§3. MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG

3.1. DÃY CON ĐƠN ĐIỆU TĂNG DÀI NHẤT

Cho dãy số nguyên A = a1, a2, …, an. (n  5000, -10000  ai  10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có 2n dãy con.

Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.

Ví dụ: A = (1, 2, 3, 4, 9, 10, 5, 6, 7). Dãy con đơn điệu tăng dài nhất là: (1, 2, 3, 4, 5, 6, 7).

Input: file văn bản INCSEQ.INP

 Dòng 1: Chứa số n

 Dòng 2: Chứa n số a1, a2, …, an cách nhau ít nhất một dấu cách

Output: file văn bản INCSEQ.OUT

 Dòng 1: Ghi độ dài dãy con tìm được

 Các dòng tiếp: ghi dãy con tìm được và chỉ số những phần tử được chọn vào dãy con

đó.

INCSEQ.INP

INCSEQ.OUT
11	8
1 2 3 8 9 4 5 6 20 9 10	a[1] = 1
	a[2] = 2
	a[3] = 3
	a[6] = 4
	a[7] = 5
	a[8] = 6
	a[10] = 9
	a[11] = 10

Có thể bạn quan tâm!

Xem toàn bộ 316 trang tài liệu này.

Cách giải:

Bổ sung vào A hai phần tử: a0 = - và an+1 = +. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a0 và kết thúc ở an+1.

Với  i: 0  i  n + 1. Ta sẽ tính L[i] = độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại ai.

3.1.1. Cơ sở quy hoạch động (bài toán nhỏ nhất):

L[n + 1] = Độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại an+1 = +. Dãy con này chỉ gồm mỗi một phần tử (+) nên L[n + 1] = 1.

3.1.2. Công thức truy hồi:

Giả sử với i chạy từ n về 0, ta cần tính L[i]: độ dài dãy con tăng dài nhất bắt đầu tại ai. L[i]

được tính trong điều kiện L[i + 1], L[i + 2], …, L[n + 1] đã biết:

Dãy con đơn điệu tăng dài nhất bắt đầu từ ai sẽ được thành lập bằng cách lấy ai ghép vào đầu một trong số những dãy con đơn điệu tăng dài nhất bắt đầu tại vị trí aj đứng sau ai. Ta sẽ chọn

dãy nào để ghép ai vào đầu? Tất nhiên là chỉ được ghép ai vào đầu những dãy con bắt đầu tại aj nào đó lớn hơn ai (để đảm bảo tính tăng) và dĩ nhiên ta sẽ chọn dãy dài nhất để ghép ai vào đầu (để đảm bảo tính dài nhất). Vậy L[i] được tính như sau: Xét tất cả các chỉ số j trong khoảng từ i + 1 đến n + 1 mà aj > ai, chọn ra chỉ số jmax có L[jmax] lớn nhất. Đặt L[i] := L[jmax] + 1.

3.1.3. Truy vết

Tại bước xây dựng dãy L, mỗi khi gán L[i] := L[jmax] + 1, ta đặt T[i] = jmax. Để lưu lại rằng: Dãy con dài nhất bắt đầu tại ai sẽ có phần tử thứ hai kế tiếp là ajmax.

Sau khi tính xong hay dãy L và T, ta bắt đầu từ 0. T[0] là phần tử đầu tiên được chọn, T[T[0]] là phần tử thứ hai được chọn,

T[T[T[0]]] là phần tử thứ ba được chọn …Quá trình truy vết có thể diễn tả như sau:

i := T[0];

while i <> n + 1 do {Chừng nào chưa duyệt đến số an+1=+ở cuối}

begin

<Thông báo chọn ai> i := T[i];

end;

Ví dụ: với A = (5, 2, 3, 4, 9, 10, 5, 6, 7, 8). Hai dãy L và T sau khi tính sẽ là:

Calculating

0	1	2	3	4	5	6	7	8	9	10	11
ai		5	2	3	4	9	10	5	6	7	8	
L[i]	9	5	8	7	6	3	2	5	4	3	2	1
T[i]	2	8	3	4	7	6	11	8	9	10	11

Tracing

Hình 49: Tính toán và truy vết

P_3_03_1.PAS * Tìm dãy con đơn điệu tăng dài nhất

program LongestSubSequence; const

InputFile = 'INCSEQ.INP'; OutputFile = 'INCSEQ.OUT'; max = 5000;

var

a, L, T: array[0..max + 1] of Integer; n: Word;

procedure Enter; var

i: Word; f: Text;

begin

Assign(f, InputFile); Reset(f); ReadLn(f, n);

for i := 1 to n do Read(f, a[i]); Close(f);

end;

procedure Optimize; {Quy hoạch động}

var

i, j, jmax: Word; begin

a[0] := -32768; a[n + 1] := 32767; {Thêm hai phần tử canh hai đầu dãy a}

L[n + 1] := 1; {Điền cơ sở quy hoach động vào bảng phương án}

for i := n downto 0 do {Tính bảng phương án}

begin

{Chọn trong các chỉ số j đứng sau i thoả mãn aj > ai ra chỉ số jmax có L[jmax] lớn nhất}

jmax := n + 1;

for j := i + 1 to n + 1 do

if (a[j] > a[i]) and (L[j] > L[jmax]) then jmax := j;

L[i] := L[jmax] + 1; {Lưu độ dài dãy con tăng dài nhất bắt đầu tại ai}

T[i] := jmax; {Lưu vết: phần tử đứng liền sau ai trong dãy con tăng dài nhất đó là ajmax}

end;

procedure Result; var

f: Text;

i: Integer; begin

Assign(f, OutputFile); Rewrite(f);

WriteLn(f, L[0] - 2); {Chiều dài dãy con tăng dài nhất}

i := T[0]; {Bắt đầu truy vết tìm nghiệm}

while i <> n + 1 do begin

WriteLn(f, 'a[', i, '] = ', a[i]); i := T[i];

end; Close(f);

end;

begin

Enter;

Optimize;

Result;

end.

Nhận xét: Công thức truy hồi tính các L[.] có thể tóm tắt là:

⎧L[n  1] : 0

⎪

⎨L[i] : max L[ j]  1 (i  0, n)

i jn1

⎩ai a j

và để tính hết các L[.], ta phải mất một đoạn chương trình với độ phức tạp tính toán là O(n2). Ta có thể cải tiến cách cài đặt để được một đoạn chương trình với độ phức tạp tính toán là O(nlogn) bằng kỹ thuật sau:

Với mỗi số k, ta gọi StartOf[k] là chỉ số x của phần tử a[x] thoả mãn: dãy đơn điệu tăng dài nhất bắt đầu từ a[x] có độ dài k. Nếu có nhiều phần tử a[.] cùng thoả mãn điều kiện này thì ta chọn phần tử a[x] là phần tử lớn nhất trong số những phần tử đó. Việc tính các giá trị StartOf[.] được thực hiện đồng thời với việc tính các giá trị L[.] bằng phương pháp sau:

L[n + 1] := 1;

StartOf[1] := n + 1;

m := 1; {m là độ dài dãy con đơn điệu tăng dài nhất của dãy ai, ai+1, …, an+1 (ở bước khởi tạo này i = n + 1)}

for i := n downto 0 do begin

<Tính L[i]; đặt k := L[i]>;

if k > m then {Nếu dãy con tăng dài nhất bắt đầu tại a[i] có độ dài > m}

begin

m := k; {Cập nhật lại m}

StartOf[k] := i; {Gán giá trị cho StartOf[m]}

end else

if a[i] > a[StartOf[k]] then {Nếu có nhiều dãy đơn điệu tăng dài nhất độ dài k thì}

StartOf[k] := i; {chỉ ghi nhận lại dãy có phần tử bắt đầu lớn nhất}

end;

Khi bắt đầu vào một lần lặp với một giá trị i, ta đã biết được:

m: Độ dài dãy con đơn điệu tăng dài nhất của dãy ai+1, ai+2, …, an+1

StartOf[k] (1  k  m): Phần tử aStartOf[k] là phần tử lớn nhất trong số các phần tử ai+1, ai+2, …, an+1 thoả mãn: Dãy con đơn điệu tăng dài nhất bắt đầu từ aStartOf[k] có độ dài k. Do thứ tự tính toán được áp đặt như trong sơ đồ trên, ta dễ dàng nhận thấy rằng: aStartOf[k] < aStartOf[k - 1]

<…<aStartOf[1].

Điều kiện để có dãy con đơn điệu tăng độ dài p+1 bắt đầu tại ai chính là aStartOf[p] > ai (vì theo thứ tự tính toán thì khi bắt đầu một lần lặp với giá trị i, aStartOf[p] luôn đứng sau ai). Mặt khác nếu đem ai ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu tại aStartOf[p] mà thu được dãy tăng thì đem ai ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu tại aStartOf[p - 1] ta cũng thu được dãy tăng. Vậy để tính L[i], ta có thể tìm số p lớn nhất thoả mãn aStartOf[p] > ai bằng thuật toán tìm kiếm nhị phân rồi đặt L[i] := p + 1 (và sau đó T[i] := StartOf[p], tất nhiên)

P_3_03_2.PAS * Cải tiến thuật toán tìm dãy con đơn điệu tăng dài nhất program LongestSubSequence;

const

InputFile = 'INCSEQ.INP'; OutputFile = 'INCSEQ.OUT';

const

max = 5000; var

a, L, T, StartOf: array[0..max + 1] of Integer; n, m: Integer;

procedure Enter; var

i: Word; f: Text;

begin

Assign(f, InputFile); Reset(f); ReadLn(f, n);

for i := 1 to n do Read(f, a[i]); Close(f);

end;

procedure Init; begin

a[0] := -32768;

a[n + 1] := 32767;

m := 1;

L[n + 1] := 1;

StartOf[1] := n + 1; end;

{Hàm Find, tìm vị trí j mà nếu đem ai ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu từ aj sẽ được dãy đơn điệu tăng dài nhất bắt đầu tại ai}

function Find(i: Integer): Integer;

var

inf, sup, median, j: Integer; begin

inf := 1; sup := m + 1;

repeat {Thuật toán tìm kiếm nhị phân}

median := (inf + sup) div 2; j := StartOf[median];

if a[j] > a[i] then inf := median {Luôn để aStartOf[inf] > ai aStartOf[sup]}

else sup := median; until inf + 1 = sup; Find := StartOf[inf];

end;

procedure Optimize; var

i, j, k: Integer; begin

for i := n downto 0 do begin

j := Find(i);

k := L[j] + 1;

if k > m then begin

m := k;

StartOf[k] := i;

end else

if a[StartOf[k]] < a[i] then StartOf[k] := i;

L[i] := k;

T[i] := j;

end;

procedure Result; var

f: Text;

i: Integer; begin

Assign(f, OutputFile); Rewrite(f); WriteLn(f, m - 2);

i := T[0];

while i <> n + 1 do begin

WriteLn(f, 'a[', i, '] = ', a[i]); i := T[i];

end; Close(f);

end;

begin

Enter;

Init;

Optimize;

Result;

end.

Dễ thấy chi phí thời gian thực hiện giải thuật này cấp O(nlogn), đây là một ví dụ điển hình cho thấy rằng một công thức truy hồi có thể có nhiều phương pháp tính.

3.2. BÀI TOÁN CÁI TÚI

Trong siêu thị có n gói hàng (n  100), gói hàng thứ i có trọng lượng là Wi  100 và trị giá Vi

 100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M ( M  100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.

Input: file văn bản BAG.INP

 Dòng 1: Chứa hai số n, M cách nhau ít nhất một dấu cách

 n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Wi, Vi cách nhau ít nhất một dấu cách

Output: file văn bản BAG.OUT

 Dòng 1: Ghi giá trị lớn nhất tên trộm có thể lấy

 Dòng 2: Ghi chỉ số những gói bị lấy

BAG.INP

BAG.OUT
5	11	11
3	3	5 2 1
4	4
5	4
9	10
4	4

Cách giải:

Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, …, i} với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n, M].

3.2.1. Công thức truy hồi tính F[i, j].

Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, …,i - 1, i} để có giá trị lớn nhất sẽ có hai khả năng:

Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói

{1, 2, …, i - 1} với giới hạn trọng lượng là j. Tức là

F[i, j] = F[i - 1, j]

Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà Wi  j) thì F[i, j] bằng giá trị gói thứ i là Vi cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng j - Wi. Tức là về mặt giá trị thu được:

F[i, j] = Vi + F[i - 1, j - Wi]

Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max trong 2 giá trị thu

được ở trên.

3.2.2. Cơ sở quy hoạch động:

Dễ thấy F[0, j] = giá trị lớn nhất có thể bằng cách chọn trong số 0 gói = 0.

3.2.3. Tính bảng phương án:

Bảng phương án F gồm n + 1 dòng, M + 1 cột, trước tiên được điền cơ sở quy hoạch động: Dòng 0 gồm toàn số 0. Sử dụng công thức truy hồi, dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2, v.v… đến khi tính hết dòng n.

F	0	1	2	......	M
0	0	0	0	...0...	0
1
2
...	...	...	...	...	...
n

3.2.4. Truy vết:

Tính xong bảng phương án thì ta quan tâm đến F[n, M] đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F[n, M] = F[n - 1, M] thì tức là không chọn gói thứ n, ta truy tiếp F[n - 1, M]. Còn nếu F[n, M]  F[n - 1, M] thì ta thông báo rằng phép chọn tối ưu có chọn gói thứ n và truy tiếp F[n - 1, M - Wn]. Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.

P_3_03_3.PAS * Bài toán cái túi

program The_Bag; const

InputFile = 'BAG.INP'; OutputFile = 'BAG.OUT'; max = 100;

var

W, V: Array[1..max] of Integer;

F: array[0..max, 0..max] of Integer; n, M: Integer;

procedure Enter; var

i: Integer; fi: Text;

begin

Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, M);

for i := 1 to n do ReadLn(fi, W[i], V[i]); Close(fi);

end;

procedure Optimize; {Tính bảng phương án bằng công thức truy hồi}

var

i, j: Integer; begin

FillChar(F[0], SizeOf(F[0]), 0); {Điền cơ sở quy hoạch động}

for i := 1 to n do for j := 0 to M do

begin {Tính F[i, j]}

F[i, j] := F[i - 1, j]; {Giả sử không chọn gói thứ i thì F[i, j] = F[i - 1, j]}

{Sau đó đánh giá: nếu chọn gói thứ i sẽ được lợi hơn thì đặt lại F[i, j]}

if (j >= W[i]) and

(F[i, j] < F[i - 1, j - W[i]] + V[i]) then

F[i, j] := F[i - 1, j - W[i]] + V[i];

end;

procedure Trace; {Truy vết tìm nghiệm tối ưu}

var

fo: Text; begin

Assign(fo, OutputFile); Rewrite(fo);

WriteLn(fo, F[n, M]); {In ra giá trị lớn nhất có thể kiếm được}

while n <> 0 do {Truy vết trên bảng phương án từ hàng n lên hàng 0}

begin

if F[n, M] <> F[n - 1, M] then {Nếu có chọn gói thứ n}

begin

Write(fo, n, ' ');

M := M - W[n]; {Đã chọn gói thứ n rồi thì chỉ có thể mang thêm được trọng lượng M - Wn nữa thôi}

end;

Dec(n);

end;

Close(fo);

end;

begin

Enter;

Optimize;

Trace;

end.

3.3. BIẾN ĐỔI XÂU

Cho xâu ký tự X, xét 3 phép biến đổi:

a) Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X.

b) Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C.

c) Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X.

Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu X thành xâu Y.

Input: file văn bản STR.INP

Dòng 1: Chứa xâu X (độ dài  100) Dòng 2: Chứa xâu Y (độ dài  100)

Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại mỗi phép biến đổi.

Xem toàn bộ nội dung bài viết ᛨ