Bài viết sưu tầm trên mạng.
Cho dãy . 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:
For duyệt qua các phần tử 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ị.Đặ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.
Hàm mục tiêu: : độ 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 là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ đến và phần tử cuối cùng là .
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 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 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 như sau:
Tính : phần tử đang được xét là . Ta tìm đến phần tử có lớn nhất. Khi đó nếu bổ sung vào sau dãy con ta sẽ được dãy con tăng dần dài nhất xét từ .
Bảng phương án là một mảng một chiều để lưu trữ các giá trị của hàm QHĐ . Đoạn chương trình tính các giá trị của mảng 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à , độ phức tạp thời gian là .
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à , một trong những cách đó là dùng Segment Tree.
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ài toán:
Có cuộc họp, cuộc họp thứ bắt đầu vào thời điểm và kết thúc ở thời điểm . 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 . Thế thì cuộc họp sẽ bố trí được sau cuộc họp khi và chỉ khi và . 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ài toán:
Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của khách hàng. Khách hàng muốn sử dụng máy trong khoảng thời gian từ đến và trả tiền thuê là . 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 bố trí phòng họp, 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 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;
Bài toán:
Cho tam giác trên mặt phẳng. Tam giác bao tam giác nếu 3 đỉnh của tam giác đều nằm trong tam giác (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 sẽ bao tam giác nếu và 3 đỉnh của nằm trong . Từ đó có thể đưa về bài toán tìm dãy “tăng” dài nhất.
Bài toán có một số biến thể khác như tìm dãy hình tam giác, hình chữ nhật… bao nhau có tổng diện tích lớn nhất.
Việc kiểm tra điểm có nằm trong tam giác không có thể dựa trên phương pháp tính diện tích: điểm nằm trong nếu .
Bài toán:
Cho dãy . Hãy tìm dãy con đổi dấu dài nhất của dãy đó. Dãy con đổi dấu phải thoả mãn các điều kiện sau:
Hướng dẫn:
Gọi là số phần tử của dãy con đổi dấu có phần tử cuối cùng là và phần tử cuối cùng lớn hơn phần tử đứng trước. Tương tự, là số phần tử của dãy con đổi dấu có phần tử cuối cùng là và phần tử cuối cùng nhỏ hơn phần tử đứng trước.
Ta dễ dàng suy ra:
Bài toán:
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 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:
là mảng ghi độ dài lớn nhất của 1 dãy con tăng dần trích ra từ dãy phần tử kể từ phần tử 1 đến phần tử .
: mảng ghi độ dài lớn nhất của dãy con giảm dần trích ra từ dãy phần tử kể từ phần tử đến . Ta tìm phần tử trong 2 mảng , thỏa mãn lớn nhất.
Bài toán:
Cho khối đá .
Các khối đá đều có dạng hình hộp chữ nhật và được đặc trưng bới 3 kích thước: dài, rộng, cao. Một cách xây dựng tháp là một cách đặt một số các khối đá trong các khối đá đã cho chồng lên nhau theo quy tắc:
Hãy chỉ ra cách để xây dựng được một cái tháp sao cho số khối đá được dùng là nhiều nhất.
Có đồ vật, vật thứ có trọng lượng và giá trị . 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 sao cho tổng giá trị của vali là lớn nhất.
Hàm mục tiêu: : 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:
- : tổng giá trị lớn nhất của vali khi xét từ vật 1 .. vật và trọng lượng của vali chưa vượt quá . Chú ý rằng khi xét đến thì các giá trị trên bảng phương án đều đã được tối ưu.
Tính : vật đang xét là với trọng lượng của vali không được quá . Có 2 khả năng xảy ra:
Tóm lại ta có .
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];
Bài toán:
Cho dãy . Tìm một dãy con của dãy đó có tổng bằng .
Hướng dẫn:
Đặt nếu có thể tạo ra tổng từ một dãy con của dãy gồm các phần tử . Ngược lại thì . Nếu thì đáp án của bài toán trên là “có”.
Ta có thể tính theo công thức: nếu hoặc .
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ứ , ta chỉ cần dòng . Bảng phương án khi đó chỉ cần 1 mảng 1 chiều 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;
Dễ thấy độ phức tạp bộ nhớ của cách cài đặt trên là , độ phức tạp thời gian là , với là tổng của số. Hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to.
Bài toán:
Cho gói kẹo, gói thứ có viên. Hãy chia các gói thành 2 phần sao cho chênh lệch giữa 2 phần là ít nhất.
Hướng dẫn:
Gọi là tổng số kẹo của gói. Chúng ta cần tìm số lớn nhất thoả mãn:
Khi đó sẽ có cách chia với chênh lệch 2 phần là là nhỏ nhất và dãy con có tổng bằng ở trên gồm các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo còn lại.
Bài toán:
Người đánh cá Clement bắt được con cá, khối lượng mỗi con là , đem bán ngoài chợ. Ở chợ cá, người ta không mua cá theo từng con mà mua theo một lượng nào đó. Chẳng hạn 3 kg, 5kg...
Ví dụ: có 3 con cá, khối lượng lần lượt là: 3, 2, 4. Mua lượng 6kg sẽ phải lấy con cá thứ 2 và và thứ 3. Mua lượng 3 kg thì lấy con thứ nhất. Không thể mua lượng 8 kg. Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn?
Hướng dẫn
Thực chất bài toán là tìm các số mà có một dãy con của dãy có tổng bằng . Ta có thể dùng phương pháp đánh dấu của bài chia kẹo ở trên rồi đếm các giá trị mà .
Bài toán:
Cho số tự nhiên . Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu "?": A1 ? A2 ? ... ? AN. Cho trước số nguyên , có cách nào thay các dấu ? bằng dấu + hay dấu − để được một biểu thức số học cho giá trị là không?
Hướng dẫn:
Đặt nếu có thể điền dấu vào số đầu tiên và cho kết quả bằng . Ta có công thức sau để tính :
L[1, a[1]] = 1L[i, t] = 1 nếu L[i - 1, t + a[i]] = 1 hoặc L[i - 1, t - a[i]] = 1.Nếu L[n, S] = 1 thì câu trả lời của bài toán là có.
Khi cài đặt, có thể dùng một mảng 2 chiều (lưu toàn bộ bảng phương án) hoặc 2 mảng một chiều (để lưu dòng và dòng ). Chú ý là chỉ số theo của các mảng phải có cả phần âm (tức là từ đến , với là tổng của số), vì trong bài này chúng ta dùng cả dấu - nên có thể tạo ra các tổng âm.
Bài này có một biến thể là đặt dấu sao cho kết quả là một số chia hết cho . Ta có thuật giải tương tự bài toán trên bằng cách thay các phép cộng, trừ bằng các phép cộng và trừ theo modulo và dùng mảng đánh dấu với các giá trị từ 0 đến (là các số dư có thể có khi chia cho ). Đáp số của bài toán là .
Bài toán:
Cho số nguyên. Hãy chia chúng thành 2 nhóm sao cho tích của tổng 2 nhóm là lớn nhất.
Hướng dẫn:
Gọi là tổng số nguyên đó. Giả sử ta chia dãy thành 2 nhóm, gọi là tổng của một nhóm, tổng nhóm còn lại là và tích của tổng 2 nhóm là . Bằng phương pháp đánh dấu ta xác định được mọi số là tổng của một nhóm (như bài Market) và tìm số sao cho đạt max.
Bài toán
Một người có mảnh đất và dải đất. Các mảnh đất có thể coi là một tứ giác và các dải đất thì coi như một đường thẳng. Dọc theo các dải đất ông ta trồng các cây bách, dải đất thứ có cây bách. Ông ta cũng trồng các cây bách trên viền của các mảnh đất, mảnh đất thứ có cây bách. Cả ở trên các mảnh đất và dải đất, xen giữa 2 cây bách ông ta trồng một cây ôliu. Ông ta cho con trai được chọn các mảnh đất và dải đất tuỳ ý với điều kiện tổng số cây bách không vượt quá . Người con trai phải chọn thế nào để có nhiều cây ôliu (loài cây mà anh ta thích) nhất.
Hướng dẫn
Dễ thấy mảnh đất thứ có cây ôliu và dải đất thứ có cây ôliu. Coi các mảnh đất và dải đất là các “đồ vật”, đồ vật thứ có khối lượng và giá trị (nếu là mảnh đất thì , nếu là dải đất thì , ). Ta cần chọn các “đồ vật”, sao cho tổng “khối lượng” của chúng không vượt và tổng “giá trị” là lớn nhất. Đây chính là bài toán xếp balô đã trình bày ở trên.
Cho 2 xâu , . Xâu gốc có kí tự , xâu đích có kí tự . Có 3 phép biến đổi:
I i CR i CD iHãy tìm số ít nhất các phép biến đổi để biến xâu thành xâu .
Hàm mục tiêu: : số phép biến đổi.
Dễ thấy số phép biến đổi phụ thuộc vào vị trí đang xét của xâu và vị trí đang xét của xâu . Do vậy để cài đặt cho bảng phương án ta sẽ dùng mảng 2 chiều.
Gọi là số phép biến đổi ít nhất để biến xâu gồm kí tự phần đầu của () thành xâu gồm kí tự phần đầu của ().
Dễ thấy và .
Có 2 trường hợp xảy ra:
Tổng kết lại, ta có công thức QHĐ:
L[0,j]=jL[i,0]=iL[i,j] =L[i−1,j−1] nếu .L[i,j] = min(L[i−1,j], L[i,j−1], L[i−1,j−1]) + 1 nếu .Bài này ta có thể tiết kiệm biến hơn bằng cách dùng 2 mảng 1 chiều tính lẫn nhau và một mảng đánh dấu 2 chiều để truy vết.
Bài toán:
Cho 2 xâu , . Hãy tìm xâu con của và của có độ dài lớn nhất. Biết xâu con của một xâu thu được khi xóa một số kí tự thuộc xâu đó (hoặc không xóa kí tự nào).
Công thức QHĐ:
Gọi là độ dài xâu con chung dài nhất của xâu gồm kí tự phần đầu của () và xâu gồm kí tự phần đầu của (). Ta có công thức quy hoạch động như sau:
L[0,j] = L[i,0] = 0L[i,j] = L[i−1,j−1] + 1 nếu L[i,j] = max(L[i−1,j], L[i,j−1]) nếu .Cài đặt:
Bảng phương án là một mảng 2 chiều L[0..m,0..n] để lưu các giá trị của hàm QHĐ .
Đoạn chương trình cài đặt công thức QHĐ trên như sau:
for i:=0 to m do L[i,0]:=0;
for j:=0 to n do L[0,j]:=0;
for i:=1 to m do
for j:=1 to n do
if X[i]=Y[j] then L[i,j]:=L[i-1,j-1]+1
else L[i,j]:=max(L[i-1,j],L[i,j-1]]);
Như vậy độ phức tạp bộ nhớ của bài toán là , độ phức tạp thời gian là .
Có một phương pháp cài đặt tốt hơn, chỉ với độ phức tạp bộ nhớ dựa trên nhận xét sau: để tính ô của bảng phương án, ta chỉ cần 3 ô , và . Tức là để tính dòng thì chỉ cần dòng . Do đó ta chỉ cần 2 mảng 1 chiều để lưu dòng vừa tính (P) và dòng đang tính (L) mà thôi. Cách cài đặt mới như sau:
for j:=0 to n do P[j]:=0;
for i:=1 to m do
begin
L[0] := 0;
for j:=1 to n do
if X[i]=Y[j] then L[i,j]:=P[j-1]+1
else L[i,j]:=max(P[j], L[j-1]);
P := L;
end;
Bài toán:
Hai nước Alpha và Beta nằm ở hai bên bờ sông Omega, Alpha nằm ở bờ bắc và có thành phố được đánh số từ 1 đến , Beta nằm ở bờ nam và có thành phố được đánh số từ 1 đến (theo vị trí từ đông sang tây). Mỗi thành phố của nước này thường có quan hệ kết nghĩa với một số thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây các cây cầu bắc qua sông, mỗi cây cầu sẽ là nhịp cầu nối 2 thành phố kết nghĩa. Với yêu cầu là các cây 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 Alpha lần lượt là ; các thành phố của Beta là . Nếu thành phố và kết nghĩa với nhau thì coi "bằng” . Để các cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố để xây cầu thì cặp tiếp theo phải là cặp sao cho và . 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 và .
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.
Bài toán:
Một xâu gọi là xâu đối xứng (palindrome) 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 , hãy tìm số kí tự ít nhất cần thêm vào để 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:
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 đó độ phức tạp bộ nhớ là . Có một phương pháp cài đặt tiết kiệm hơn, có thể tham khảo ở bài viết của Nguyễn Hoành Tiến
Ta có thuật toán đơn giản hơn như sau:
S=edbabcd, xâu đảo của là P=dcbabde. Xâu con chung dài nhất của và là T=dbabd. Như vậy cần thêm 2 kí tự là e và c vào để trở thành xâu đối xứng.Cho vật, vật nặng và có giá trị . 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á 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.
Gọi là tổng giá trị lớn nhất khi được chọn vật từ 1 đến cho vào balô với tổng khối lượng không vượt quá . sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn vật và tổng khối lượng không vượt quá ).
Công thức tính như sau:
Trong đó: là giá trị có được nếu không đưa vật vào balô, là giá trị có được nếu chọn vật .
Ta có thể dùng một mảng 2 chiều để lưu bảng phương án, tuy nhiên dựa trên nhận xét rằng để tính dòng của bảng phương án chỉ cần dòng , ta chỉ cần dùng 2 mảng một chiều và có chỉ số từ 0 đến để lưu 2 dòng đó. Đoạn chương trình con tính bảng phương án như sau.
L[t] := 0; {với mọi t}
for i := 1 to n do
begin
P:=L;
for t := 0 to m do
if t<a[i] then L[t]:=P[t]
else L[t] := max(P[t],L[t-a[i]]+b[i]);
end;
Nếu để ý kĩ bạn sẽ thấy rằng đoạn trình trên chỉ viết giống công thức QHĐ chứ chưa tối ưu. Chẳng hạn đã có lệnh gán P:=L, sau đó lại có gán L[t]:=P[t] với các giá trị t<a[i] là không cần thiết. Bạn đọc có thể tự cải tiến để chương trình tối ưu hơn.
Độ phức tạp bộ nhớ là và độ phức tạp thời gian là .
Bài toán
Ở đất nước Omega người ta chỉ tiêu tiền xu. Có loại tiền xu, loại thứ có mệnh giá là đồng. Một người khách du lịch đến Omega du lịch với số tiền đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.
Hướng dẫn
Bài toán này khá giống bài toán xếp balô (“khối lượng” là mệnh giá, “giá trị” là 1), chỉ có một thay đổi nhỏ: tổng giá trị yêu cầu là nhỏ nhất.
Do đó ta cũng xây dựng hàm QHĐ một cách tương tự: Gọi là số đồng xu ít nhất nếu đổi đồng ra loại tiền xu (từ 1 đến ). Công thức tính như sau:
Công thức này khác công thức của bài xếp balô ở chỗ: dùng hàm min chứ không phải hàm max (vì cần tìm cách chọn ít hơn).
Nhân một ma trận kích thước với một ma trận , số phép nhân phải thực hiện là . Mặt khác phép nhân các ma trận có tính kết hợp, tức là:
Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau, mỗi trình tự tính sẽ quyết định số phép nhân cần thực hiện.
Cho ma trận , ma trận có kích thước là . Hãy xác định trình tự nhân ma trận sao cho số phép nhân cần thực hiện là ít nhất.
Gọi là số phép nhân để tính tích các ma trận từ đến .
Công thức hơi phức tạp nên tôi xin giải thích như sau:
Ma trận kết quả của phép nhân có kích thước , ma trận kết quả của phép nhân có kích thước . Với cách đặt đó ta sẽ mất phép nhân để có kết quả trong dấu ngoặc thứ nhất, mất thêm phép nhân để có kết quả trong dấu ngoặc thứ hai, và cuối cùng mất để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt đó là: .
Ta chọn vị trí cho số phép nhân ít nhất.
Bảng phương án là một mảng 2 chiều để lưu . Chú ý khi cài đặt là để tính được , ta phải tính và trước. Phương pháp đơn giản để làm điều đó là phương pháp đệ quy có nhớ.
Tuy nhiên dựa vào nhận xét là trong công thức QHĐ: lớn hơn và , ta có thể tính theo trình tự khác: tính các phần tử với từ nhỏ đến lớn (không phải là tính các giá trị với , từ nhỏ đến lớn như vẫn làm). Với cách đó, khi tính đến thì ta đã có và .
Đoạn chương trình tính bảng phương án như sau:
for i:=1 to n do
F[i,i]:=0;
for i:=1 to n-1 do
F[i,i+1] := d[i-1]*d[i]*d[i+1];
for m:=2 to n-1 do
begin
for i:=1 to n-m do
begin
j:=i+m;
F[i,j]:=oo;
for k:=i+1 to j-1 do
F[i,j]:=min(F[i,j], F[i,k]+F[k+1,j]+d[i-1]*d[k]*d[j]);
end;
end;
Với cách cài đặt trên, độ phức tạp bộ nhớ là , độ phức tạp thời gian là .
Bài toán
Cho một đa giác lồi đỉnh. Bằng các đường chéo không cắt nhau, ta có thể chia đa giác thành tam giác. Hãy xác định cách chia có tổng các đường chéo ngắn nhất.
Hướng dẫn
Để đơn giản ta coi mọi đoạn thẳng nối 2 đỉnh đều là “đường chéo” (nếu nối 2 đỉnh trùng nhau hoặc 2 đỉnh liên tiếp thì có độ dài bằng 0).
Gọi là tổng độ dài các đường chéo khi chia đa giác gồm các đỉnh từ đến thành các tam giác. Nếu thì đa giác đó có ít hơn 4 đỉnh, không cần phải chia nên . Ngược lại ta xét cách chia đa giác đó bằng cách chọn một đỉnh nằm giữa , và nối , với . Khi đó với là độ dài đường chéo .
Tóm lại công thức QHĐ như sau:
Bài toán
Cho biểu thức , trong đó là các số thực không âm và là một phép toán + hoặc * cho trước. Hãy đặt các dấu ngoặc để biểu thức thu được có kết quả lớn nhất.
Hướng dẫn
Gọi là giá trị lớn nhất có thể có của biểu thức . Dễ thấy nếu thì , nếu thì . Nếu thì có thể tính biểu thức bằng cách chia thành 2 nhóm: , Khi đó .
Tóm lại, công thức QHĐ là:
(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 và đạt max thì cũng đạt max).
Có lọ hoa sắp thẳng hàng và bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cắm bó hoa trên vào 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 vào lọ thứ là . 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.
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: : 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.
: tổng giá trị thẩm mỹ lớn nhất khi xét đến hoa và lọ . Khi tính hoa đang xét sẽ là hoa và lọ .
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]);
Bài toán
Có phòng học chuyên đề và nhóm học được đánh số thứ tự từ nhỏ đến lớn. Cần xếp nhóm trên vào 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 có ghế, nhóm có học sinh. Hãy chọn 1 phương án bố trí sao cho tổng số lần chuyển ghế ra và vào là ít nhất.
Hướng dẫn
Khi xếp nhóm vào phòng thì số lần chuyển ghế chính là độ chênh lệch giữa số ghế trong phòng và số học sinh trong nhóm. Đặt
Bài toán
Trong hiệu có đôi giày, đôi giày có kích thước . Có người cần mua giày, người cần mua đôi giày kích thước . Khi người chọn mua đôi giày thì độ lệch sẽ là . Hãy tìm cách chọn mua giày cho người trên sao cho tổng độ lệch là ít nhất. Biết rằng mỗi người chỉ mua 1 đôi giày và 1 đôi giày cũng chỉ có một người mua.
Hướng dẫn
Lập công thức giải như bài Câu lạc bộ. Chú ý chứng minh tính đúng đắn của bổ đề heuristic sau: Cho 2 dãy tăng dần các số dương , . Gọi là một hoán vị bất kỳ của dãy . Khi đó:
Cho bảng gồm ô. Từ ô có thể di chuyển sang 3 ô , và . Hãy xác định một lộ trình đi từ hàng 1 đến hàng sao cho tổng các ô đi qua là lớn nhất.
Gọi là giá trị lớn nhất có được khi di chuyển đến ô . Có 3 ô có thể đi đến ô là , và . Do đó ta có công thức QHĐ như sau:
Bảng phương án là bảng 2 chiều . (Tất cả các ô trên biên đều cho giá trị bằng 0).
Quá trình tính như sau:
for i:=1 to m do
for j := 1 to n do
F[i,j]=max(F[i-1,j],F[i-1,j-1],F[i-1,j+1]]+A[i,j]);
Cách cài đặt này cho độ phức tạp bộ nhớ và thời gian đều là . Ta có thể tiết kiệm không gian nhớ bằng cách tính trực tiếp trên mảng .
Bài toán
Cho một tam giác gồm các số nguyên không âm. Hãy tính tổng lớn nhất các số trên đường đi từ đỉnh tam giác xuống một điểm nào đó ở đáy tam giác nào đó. Tại mỗi ô ta chỉ có đi thẳng xuống, sang ô bên trái hoặc bên phải.
Hướng dẫn
Mô tả các phần tử của tam giác số như một ma trận, là phần tử thứ trên dòng (với và ). Có 2 ô có thể di chưyển đến ô là ô và ô . Gọi là tổng lớn nhất có thể có khi đi đến ô ta có: